UW CSE 326 - Graphs (123 pages)

Previewing pages 1, 2, 3, 4, 5, 6, 7, 8, 57, 58, 59, 60, 61, 62, 63, 64, 65, 116, 117, 118, 119, 120, 121, 122, 123 of 123 page document View the full content.
View Full Document

Graphs



Previewing pages 1, 2, 3, 4, 5, 6, 7, 8, 57, 58, 59, 60, 61, 62, 63, 64, 65, 116, 117, 118, 119, 120, 121, 122, 123 of actual document.

View the full content.
View Full Document
View Full Document

Graphs

22 views

Other


Pages:
123
School:
University of Washington
Course:
Cse 326 - Data Structures

Unformatted text preview:

CSE 326 Data Structures Part 8 Graphs Henry Kautz Autumn Quarter 2002 Outline Graphs TO DO READ WEISS CH 9 Graph Data Structures Graph Properties Topological Sort Graph Traversals Depth First Search Breadth First Search Iterative Deepening Depth First Shortest Path Problem Dijkstra s Algorithm Graph ADT Graphs are a formalism for representing relationships between objects a graph G is represented as G V E V is a set of vertices E is a set of edges operations include Han Luke Leia V Han Leia Luke E Luke Leia Han Leia Leia Han iterating over vertices iterating over edges iterating over vertices adjacent to a specific vertex asking whether an edge exists connected two vertices What Graph is THIS ReferralWeb co authorship in scientific papers Biological Function Semantic Network Graph Representation 1 Adjacency Matrix A V x V array in which an element u v is true if and only if there is an edge from u to v Han Han Luke Leia Runtime iterate over vertices iterate ever edges iterate edges adj to vertex edge exists Luke Han Luke Leia Space requirements Leia Graph Representation 2 Adjacency List A V ary list array in which each entry stores a list linked list of all adjacent vertices Han Luke Leia Runtime iterate over vertices iterate ever edges iterate edges adj to vertex edge exists Han Luke Leia space requirements Directed vs Undirected Graphs In directed graphs edges have a specific direction Han Luke Leia In undirected graphs they don t edges are two way Han Luke Leia Vertices u and v are adjacent if u v E Graph Density A sparse graph has O V edges A dense graph has V 2 edges Anything in between is either sparsish or densy depending on the context Weighted Graphs Each edge has an associated weight or cost Clinton 20 Mukilteo Kingston 30 Bainbridge 35 Edmonds Seattle 60 Bremerton There may be more information in the graph as well Paths and Cycles A path is a list of vertices v1 v2 vn such that vi vi 1 E for all 0 i n A cycle is a path that begins and ends at the same



View Full Document

Access the best Study Guides, Lecture Notes and Practice Exams

Loading Unlocking...
Login

Join to view Graphs and access 3M+ class-specific study document.

or
We will never post anything without your permission.
Don't have an account?
Sign Up

Join to view Graphs and access 3M+ class-specific study document.

or

By creating an account you agree to our Privacy Policy and Terms Of Use

Already a member?