Directed graphs Connected graph A graph is connected if and only if there exists a path between every pair of distinct vertices; A graph with the vertex and edge set being subsets of the original graph; A connected component of a graph is a maximally connected subgraph of a graph. | Directed graphs anhtt-fit@ dungct@ . 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 ( n + m ) = O (∑ n + ∑ m ) = O ( n + m ) i i i i i i i 3 A complete graph API In the current graph API, only the edges are managed. Therefore we can not know how many vertices there are in the graph. Each vertex need also a name .
