Directed graphs anhtt-fit@mail.hut.edu.vn dungct@it-hut.edu.vn http://www.4shared.com/file/43395119/3907952d/lect08. html Terminology Connected graph A graph is connected if and only if there exists a path between every pair of distinct vertices Sub-graph A graph with the vertex and edge set being subsets of the original graph Connected Components A connected component of a graph is a maximally connected subgraph of a graph Cycle A path in a graph that starts and ends at the same vertex Tree A graph G is a tree if and only if it is connected and acyclic Directed Graph A graph whose the edges (arcs) are directional Directed Acyclic Graph A directed graph with no directed cycles 1 Directed Graphs A directed graph can be represented by an adjacency matrix/list the same way as in undirected graph, except: An arc (u, v) only contributes to 1 entry in the adj. matrix or 1 node in the adj. list Paths/Cycles A directed graph can also contain paths and cycles (“directed paths” and “directed cycles”) b a Graph on top has directed paths and directed cycle Graph on bottom has directed paths but NO directed cycle (acyclic) c b a c 2 Graph traversal BFS and DFS can be used to traverse a directed graph, the same way as in undirected graph To check for connectivity of a graph run BFS or DFS using an arbitrary vertex as the source. If all vertices have been visited, then the graph is connected; otherwise, the graph is disconnected Finding Connected Components Run DFS or BFS from a vertex the set of visited vertices form a connected component Find another vertex i which has not been visited before, run DFS or BFS from it we have another connected component Repeat the steps until all vertices are visited Running time is O(ni + mi ) = O ( i mi ) = O( n

Lire le document entier