Title:
ApplicationsOfDepth-FirstTraversal
Download
Description: 1. Using DFS to test if a given undirected graph is connected or not.
2. Classify the edges of a directed graph into tree edges, back edges, forward edges or cross edges by a depth-first traversal of the graph. If the given graph is undirected, classify the edges into tree edges and back edges. And verify if a directed or undirected graph has a cycle.
3. Compute the topological order of a directed graph using both DFS algorithm and source removal algorithm.
4. A strongly connected graph is a directed graph with every pair of vertices reachable from each other. A strongly connected component C of a directed graph G is a subset of maximal vertices such that every pair of vertices in the subset are reachable from each other. A strongly connected component graph GSCC of a graph G is a directed graph that each component C of G is considered as a single vertex in GSCC and there is an edge between components C1 and C2 if there exist an edge (u, v) in the graph G with u belongs to C1 and v
To Search:
File list (Check if you may need any files):
源程序\有向图强连通分量.h
......\Applications of Depth-First Traversal.cpp
......\DFS拓扑排序.h
......\点消除拓扑排序.h
......\两种方法求有向图的拓扑排序.h
......\判定图的半连通性.h
......\判断图的单连通.h
......\判断图的双连通.h
......\无向图的连通性.h
......\有向图边分类.h
源程序
