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 node Chicago Seattle Salt Lake City San Francisco Dallas p Seattle Salt Lake City Chicago Dallas San Francisco Seattle Path Length and Cost Path length the number of edges in the path Path cost the sum of the costs of each edge Chicago 3 5 Seattle 2 2 2 Salt Lake City 2 5 2 5 2 5 3 San Francisco Dallas length p 5 cost p 11 5 Connectivity Undirected graphs are connected if there is a path between any two vertices Directed graphs are strongly connected if there is a path from any one vertex to any other Directed graphs are weakly connected if there is a path between any two vertices ignoring direction A complete graph has an edge between every pair of vertices Trees as Graphs Every tree is a graph with some restrictions the tree is directed there are no cycles directed or undirected there is a directed path from the root to every node A B C D E F G BAD I H J Directed Acyclic Graphs DAGs DAGs are directed graphs with no cycles main mult if program call graph is a DAG then all procedure calls can be in lined add access Trees DAGs Graphs read Application of DAGs Representing Partial Orders check in airport reserve flight call taxi pack bags take flight taxi to airport locate gate Topological Sort Given a graph G V E output all the vertices in V such that no vertex is output before any other vertex with an edge to it reserve flight call taxi taxi to airport pack bags check in airport take flight locate gate Topo Sort Take One Label each vertex s in degree of inbound edges While there are vertices remaining Pick a vertex with in degree of zero and output it Reduce the in degree of all vertices adjacent to it Remove it from the list of vertices runtime Topo Sort Take Two Label each vertex s in degree Initialize a queue or stack to contain all in degree zero vertices While there are vertices remaining in the queue Remove a vertex v with in degree of zero and output it Reduce the in degree of all vertices adjacent to v Put any of these with new in degree zero on the queue runtime Recall Tree Traversals a b f c h g e d k abfgkcdhilje i j l Depth First Search Pre Post In order traversals are examples of depth first search Nodes are visited deeply on the left most branches before any nodes are visited on the right most branches Visiting the right branches deeply before the left would still be depth first Crucial idea is go deep first Difference in pre post in order is how some computation e g printing is done at current node relative to the recursive calls In DFS the nodes being worked on are kept on a stack Iterative Version DFS Pre order Traversal Push root on a Stack Repeat until Stack is empty Pop a node Process it Push it s children on the Stack Level Order Tree Traversal Consider task of traversing tree level by level from top to bottom alphabetic order a Is this also DFS b f c h g k e d i j l Breadth First Search No Level order traversal is an example of Breadth First Search BFS characteristics Nodes being worked on maintained in a FIFO Queue not a stack Iterative style procedures often easier to design than recursive procedures Put root in a Queue Repeat until Queue is empty Dequeue a node Process it Add it s children to queue QUEUE a bcde cdefg defg efghij fghij ghij hijk ijk jkl kl l a b f c h g k e d i l j Graph Traversals Depth first search and breadth first search also work for arbitrary directed or undirected graphs Must mark visited vertices so you do not go into an infinite loop Either can be used to determine connectivity Is there a path between two given vertices Is the graph weakly connected Important difference Breadth first search always finds a shortest path from the start vertex to any other for unweighted graphs Depth first search may not Demos on Web Page DFS BFS Is BFS the Hands Down Winner Depth first search Simple to implement implicit or explict stack Does not always find shortest paths Must be careful to mark visited vertices or you could go into an infinite loop if there is a cycle Breadth first search Simple to implement queue Always finds shortest paths Marking visited nodes can improve efficiency but even without doing so search is guaranteed to terminate Space Requirements Consider space required by the stack or queue Suppose G is known to be at distance d from S Each vertex n has k out edges There are no undirected or directed cycles BFS queue will grow to size kd Will simultaneously contain all nodes that are at distance d once last vertex …
View Full Document
Unlocking...