文件名称:ApplicationsOfDepth-FirstTraversal
- 所属分类:
- 图形图像处理(光照,映射..)
- 资源属性:
- [C/C++] [源码]
- 上传时间:
- 2012-11-26
- 文件大小:
- 10kb
- 下载次数:
- 0次
- 提 供 者:
- 卢**
- 相关连接:
- 无
- 下载说明:
- 别用迅雷下载,失败请重下,重下不扣分!
介绍说明--下载内容均来自于网络,请自行研究使用
1. 用DFS判断一个无向图是否是连通图;
2. 为有向图的边分类,将它们的边分为前向边、后向边和交叉边;
3. 用DFS和点消除求有向图的拓扑排序;
4. 判断有向图是不是强连通图,若不是,求强连通分量;
5. 判断有向图是不是半连同图;
6. 判断有向图是不是单连通图;
7. 判断无向图是不是双连通图。
通过以上编程对DFS的应用,进一步了解DFS的算法及它所代表的算法思想。
-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
2. 为有向图的边分类,将它们的边分为前向边、后向边和交叉边;
3. 用DFS和点消除求有向图的拓扑排序;
4. 判断有向图是不是强连通图,若不是,求强连通分量;
5. 判断有向图是不是半连同图;
6. 判断有向图是不是单连通图;
7. 判断无向图是不是双连通图。
通过以上编程对DFS的应用,进一步了解DFS的算法及它所代表的算法思想。
-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
(系统自动生成,下载前可以参看下载内容)
下载文件列表
源程序\有向图强连通分量.h
......\Applications of Depth-First Traversal.cpp
......\DFS拓扑排序.h
......\点消除拓扑排序.h
......\两种方法求有向图的拓扑排序.h
......\判定图的半连通性.h
......\判断图的单连通.h
......\判断图的双连通.h
......\无向图的连通性.h
......\有向图边分类.h
源程序
......\Applications of Depth-First Traversal.cpp
......\DFS拓扑排序.h
......\点消除拓扑排序.h
......\两种方法求有向图的拓扑排序.h
......\判定图的半连通性.h
......\判断图的单连通.h
......\判断图的双连通.h
......\无向图的连通性.h
......\有向图边分类.h
源程序