1.描述
设计算法,判断一个以邻接表为存储结构的有向图是否存在环。
2.分析
使用DFS的拓扑排序进行判断环是否存在。
算法设计步骤:
- 1. 通过极端特里法进行手算研究
- 2. 发现特例的规律
- 3. 算法思想
- 4. 代码
通过DFS+清除访问标记visited的方法能求出所有从src到dst的所有路径(src到每个顶点的所有路径)。增加了新的限定,规定路径的长度为d(过滤出来)。
3.算法思想
- 顶点v在递归函数执行状态中(递归函数没执行完),通过某个顶点w的DFS又被重复访问,则有向图存在从顶点v出发再回到顶点v的环路。
- 将访问标记区分:未访问的、正在访问的、已访问过的;
- 使用枚举{白色,红色,黑色}分别表示{未访问的、正在访问的、已访问过的};
- 如果在搜索过程中,遇到标记为红色的顶点,则说明图中存在环;
4.手算示例
从4号顶点(src)到6号顶点(dst),长度为d的路径

5.代码
全局变量
// 访问标记数组,防止顶点重复出现在路径中 typedef enum { WHITE = 0, // 未访问的结点 RED = 1, // 正在访问的结点 BLACK = 2, // 已访问的结点 }COLOR; COLOR colorVisited[MAX_VERTEX] = { WHITE };
核心代码
注意限制条件,第16行和22行
/** * 使用DFS获得从某一顶点开始遍历,是否存在环 * * @param alG - 邻接表存储的图 * @param vertex - 起始顶点 * * @return @c bool */ bool getRing(ALGraph alG, VertexType vertex) { if (colorVisited[vertex] == RED) return true; colorVisited[vertex] = RED; // vertex顶点正在被访问 path[pathLength++] = vertex; ArcNode* pNextArcNode = alG.vertices[vertex].first; int neighborVertex = 0; bool ret = false; while (pNextArcNode != NULL) { neighborVertex = pNextArcNode->adjvex; // 从顶点 vertex 开始DFS搜索环 if(colorVisited[vertex] != BLACK) ret = getRing(alG, neighborVertex); if (ret == true) return true; pNextArcNode = pNextArcNode->next; } colorVisited[vertex] = BLACK; pathLength--; return false; } /** * 使用DFS判断图中是否存在环 * * @param alG - 邻接表存储的图 * * @return @c bool */ bool isExistRing(ALGraph alG) { bool ret = false; // 从0开始深度优先遍历 for (int v = 1; v <= alG.vexnum; v++) { if (colorVisited[v] == WHITE) ret = getRing(alG, v); } return ret; }
6.运行
注意:图的类型为有向不带权图
数据准备
顶点数据:
vSet.txt
1 2 3 4 5 6 7
弧数据:
arcSet.txt
2 1 3 1 3 2 4 5 5 7 6 5 7 6
读取顶点信息
读取弧信息
创建图
调用DFS判环
printf("isExitRing: %d\n", isExistRing(alG));
运行结果
