CSED233: Data Structures (2014F) Lecture18: Graph II Bohyung Han CSE, POSTECH [email protected] Graph ADT Data Vertices and edges Methods endVertices(e): an array of the two endvertices of e opposite(v,e): the vertex opposite of v on e areAdjacent(v,w): true iff v and w are adjacent getAdjacent(v): return a list of the vertices adjacent to vertex v insertVertex(o): insert a vertex storing element o insertEdge(v,w,o): insert an edge (v,w) storing element o removeVertex(v): remove vertex v (and its incident edges) removeEdge(e): remove edge e incidentEdges(v): edges incident to v getDegree(v): Returns the degree of vertex v 2 CSED233: Data Structures by Prof. Bohyung Han, Fall 2014 Representation of Graphs Graphs should be able to be represented by a logical method. Information to be stored

Vertices: number and labels Edges: connectivity and weights Methods Adjacency matrix Adjacency list 3 CSED233: Data Structures by Prof. Bohyung Han, Fall 2014 Adjacency Matrix Representation by matrix Uses a matrix of size Unweighted graph: Each entry is true if there is an edge from vertex to vertex , otherwise false. Weighted graph: Each entry stores weights. Characteristics Very simple, but large space requirement: Appropriate if the graph is dense 4 CSED233: Data Structures by Prof. Bohyung Han, Fall 2014 Adjacency Matrix Undirected and unweighted graph 1 2 3 1 2 3

4 5 1 0 1 0 0 1 2 1 0 1 1 0 3 0 1 0 1 0 4

0 1 1 0 1 5 1 0 0 1 0 5 4 5 CSED233: Data Structures by Prof. Bohyung Han, Fall 2014 Adjacency Matrix Directed and unweighted graph 1 2 3 1 2

3 4 5 1 0 1 0 0 0 2 0 0 0 1 0 3 0 1 0 0 0

4 0 0 1 0 1 5 1 0 0 1 0 5 4 6 CSED233: Data Structures by Prof. Bohyung Han, Fall 2014 Adjacency Matrix Directed and weighted graph 1 2 2 2

3 4 5 1 0 2 0 0 0 2 0 0 0 6 0 3 0 7 0 0 0

4 0 0 3 0 2 5 8 0 0 5 0 5 6 7 3 1 8 3 5 2 4

7 CSED233: Data Structures by Prof. Bohyung Han, Fall 2014 Adjacency List Representation by a vector of lists Motivation: Maintaining adjacent matrix is inefficient if graph is sparse. A vector of lists of vertices The th element of the vector is a list of vertices adjacent to . Complexity If graph is sparse: If graph is dense: 8 CSED233: Data Structures by Prof. Bohyung Han, Fall 2014 Adjacency List Undirected graph 1 2 3 5 4 1 2 5 2 1

3 3 2 4 4 2 3 5 1 4 9 4 5 CSED233: Data Structures by Prof. Bohyung Han, Fall 2014 Adjacency List Undirected graph 1 2 3 5 4

1 2 2 4 3 2 4 3 5 5 3 5 10 CSED233: Data Structures by Prof. Bohyung Han, Fall 2014 Performance Adjacency List Adjacency Matirx Space incidentEdges(v) areAdjacent(v,w) areAdjacent(v,w) insertVertex(o) insertVertex(o) insertEdge(v,w,o) insertEdge(v,w,o)

removeVertex(v) removeVertex(v) (undirected) (directed) removeEdge(e) removeEdge(e) vertices, edges No multiple edges and no self-loops 11 CSED233: Data Structures by Prof. Bohyung Han, Fall 2014 Graph Traversal The most common operation is to visit all the vertices in a systematic way. A traversal starts at a vertex v and visits all the vertices u such that a path exists from v to u. Similar to tree traversal Unlike trees, we need to specifically guard against repeating a path from a cycle and considering the same vertices multiple times Methods Depth First Search (DFS): based on stack Breadth First Search (BFS): based on queue 12 CSED233: Data Structures by Prof. Bohyung Han, Fall 2014 DepthFirst SearchFirst Search DFS traversal of a graph Searches all the way down a path before backing up to explore alternatives Recursive StackFirst Searchbased A Time complexity: Back edge

DFS can be further extended to solve other graph problems: Find and report a path between two given vertices Find a cycle in the graph 13 B D C E Discovery edge CSED233: Data Structures by Prof. Bohyung Han, Fall 2014 Example A B A D E B B A C A A unexplored vertex A

visited vertex D E D E C A unexplored edge C B A discovery edge back edge 14 B C CSED233: Data Structures by Prof. Bohyung Han, Fall 2014 Example A C B A B A D

C B A E C B B E D E C A D C B A D A D E C B A E C 15 B

C CSED233: Data Structures by Prof. Bohyung Han, Fall 2014 Properties of DFS Properties DFS(G,v) visits all the vertices and edges in the connected component of v. The discovery edges labeled by DFS(G,v) form a spanning tree of th e connected component of v. A Back edge B D E Discovery edge C 16 CSED233: Data Structures by Prof. Bohyung Han, Fall 2014 DFS Algorithm Algorithm DFS(G) Input graph G Output labeling of the edges of G as discovery edges and back edges for all u G.vertices() setLabel(u, UNEXPLORED) for all e G.edges() setLabel(e, UNEXPLORED) for all v G.vertices()

if getLabel(v) = UNEXPLORED DFS(G, v) Algorithm DFS(G, v) Input graph G and a start vertex v of G Output labeling of the edges of G in the connected component of v as discovery edges and back edges setLabel(v, VISITED) for all e G.incidentEdges(v) if getLabel(e) = UNEXPLORED w opposite(v,e) if getLabel(w) = UNEXPLORED setLabel(e, DISCOVERY) DFS(G, w) else setLabel(e, BACK) 17 CSED233: Data Structures by Prof. Bohyung Han, Fall 2014 Analysis of DFS Methods setLabel() for a vertex and edge time Each vertex is labeled twice: UNEXPLORED and VISITED Each edge is labeled twice: UNEXPLORED and (DISCOVERY or BACK) getLabel() for a vertex and edge time The label of each vertex and edge is checked a constant number of time. incidentEdges() time for all vertices Called once for each vertex Time complexity of DFS

provided the graph is represented by the adjacency list Recall that 18 CSED233: Data Structures by Prof. Bohyung Han, Fall 2014 Path Finding Algorithm Recursive method We use a stack S to keep track of the path between the start vertex and the current vertex. As soon as destination vertex z is encountered, we return the path as the contents of the stack. It finds all paths from v to z. 19 Algorithm pathDFS(G, v, z) setLabel(v, VISITED) S.push(v) if v = z return S.elements() for all e G.incidentEdges(v) if getLabel(e) = UNEXPLORED w opposite(v,e) if getLabel(w) = UNEXPLORED setLabel(e, DISCOVERY) S.push(e) pathDFS(G, w, z) S.pop(e) else setLabel(e, BACK) S.pop(v) CSED233: Data Structures by Prof. Bohyung Han, Fall 2014

Cycle Finding Algorithm We use a stack S to keep track of the path between the start vertex and the current vertex. As soon as a back edge (v,w) is encountered, we return the cycle as the portion of the stack from the top to vertex w. 20 Algorithm cycleDFS(G, v, z) setLabel(v, VISITED) S.push(v) for all e G.incidentEdges(v) if getLabel(e) = UNEXPLORED w opposite(v,e) S.push(e) if getLabel(w) = UNEXPLORED setLabel(e, DISCOVERY) cycleDFS(G, w, z) S.pop(e) else T new empty stack repeat o S.pop() T.push(o) until o = w return T.elements() S.pop(v) CSED233: Data Structures by Prof. Bohyung Han, Fall 2014 BreadthFirst SearchFirst Search BFS traversal of a graph Traverse the graph level by level

QueueFirst Searchbased Iterative Time complexity: BFS can be further extended to solve other graph problems Find and report a path with the minimum number of edges between two given vertices Find a simple cycle, if there is one A B 21 Discovery edge C D Cross edge E F CSED233: Data Structures by Prof. Bohyung Han, Fall 2014 Example B B C E

A A A A D C B F B visited vertex D C B discovery edge cross edge 22 C D E unexplored vertex unexplored edge A

A F A A B C E D F CSED233: Data Structures by Prof. Bohyung Han, Fall 2014 Example B D C E D C C B C

E E D F A B D E B A D E D F 23 B C E

A B C A D F C C E D F CSED233: Data Structures by Prof. Bohyung Han, Fall 2014 Example E D F E D B C

E A B C A F E F B C E D F C C E D

D A D F 24 CSED233: Data Structures by Prof. Bohyung Han, Fall 2014 Properties Properties BFS(G,s) visits all the vertices and edges of G. The discovery edges labeled by BFS(G,s) form a spanning tree. Level represents the number of edges to reach the node in the level from the initial node. A B C E D B F 25 A C E

D F CSED233: Data Structures by Prof. Bohyung Han, Fall 2014 BFS Algorithm Algorithm BFS(G) Input graph G Output labeling of the edges and partition of the vertices of G for all u G.vertices() setLabel(u, UNEXPLORED) for all e G.edges() setLabel(e, UNEXPLORED) for all v G.vertices() if getLabel(v) = UNEXPLORED BFS(G, v) Algorithm BFS(G, s) L0 new empty sequence L0.addLast(s) setLabel(s, VISITED) i0 while Li.isEmpty() Li +1 new empty sequence for all v Li.elements() for all e G.incidentEdges(v) if getLabel(e) = UNEXPLORED w opposite(v,e) if getLabel(w) = UNEXPLORED setLabel(e, DISCOVERY) setLabel(w, VISITED) Li +1.addLast(w) CSED233: Data Structures

26 else by Prof. Bohyung Han, Fall 2014 BFS Algorithm Algorithm BFS(G) Input graph G Output labeling of the edges and partition of the vertices of G for all u G.vertices() setLabel(u, UNEXPLORED) for all e G.edges() setLabel(e, UNEXPLORED) for all v G.vertices() if getLabel(v) = UNEXPLORED BFS(G, v) Algorithm BFS(G, s) Q.enqueue(s) setLabel(s, VISITED) while Q.isEmpty() for all v Q.dequeue () for all e G.incidentEdges(v) if getLabel(e) = UNEXPLORED w opposite(v,e) if getLabel(w) = UNEXPLORED setLabel(e, DISCOVERY) setLabel(w, VISITED) Q.enqueue(w) else setLabel(e, CROSS) 27 CSED233: Data Structures by Prof. Bohyung Han, Fall 2014

Analysis of BFS Methods setLabel() for a vertex and edge time Each vertex is labeled twice: UNEXPLORED and VISITED Each edge is labeled twice: UNEXPLORED and (DISCOVERY or BACK) getLabel() for a vertex and edge time The label of each vertex and edge is checked a constant number of time. incidentEdges() time for all vertices Called once for each vertex Time complexity of BFS provided the graph is represented by the adjacency list Recall that 28 CSED233: Data Structures by Prof. Bohyung Han, Fall 2014 Applications Find the connected components Find a spanning forest Find a simple cycle in G, or report that G is a tree or forest Given two vertices, find a path in G between them with the minimum number of edges, or report that no such path exists Time complexity: 29 CSED233: Data Structures by Prof. Bohyung Han, Fall 2014

DFS vs. BFS Applications DFS BFS Spanning forest, connected components, paths, cycles Shortest paths Biconnected components A B C E D B F DFS A C

E D F BFS 30 CSED233: Data Structures by Prof. Bohyung Han, Fall 2014 DFS vs. BFS Back edge (v,w) Cross edge (v,w) w is an ancestor of v in the tree of discovery edges w is in the same level as w or in the next level A B C E D B F DFS A

C E D F BFS 31 CSED233: Data Structures by Prof. Bohyung Han, Fall 2014 32