利用_DFS_来判断无向图是否存在环的条件思路，我看一次_DFS_是否能访问到之前访问到的节点，如果能够访问到，就说明图存在环，那么关键问题就是判断是一次DFS?，追根到_DFS_算法的实现细节，发现我们设置_visited_数组时只有设置0和1两个状态，那么就可以改进以下之前的_DFS_算法，将_visited_各个状态表示成如下状态:
- 0: 没有被访问过
- 1: 刚刚访问，但是邻接点没有被全部访问完
- 2: 所有的邻接点都被访问完了，这里就可以判定_DFS_一定退出了
关键问题就解决了，看下面的简易的测试代码，同时也运用到了并查集的数据结构:
#include<iostream>
#include<stdlib.h>
#define maxsize 100
#define INF 0x3f3f3f3f
using namespace std;
int g[maxsize][maxsize];
int vexnum, arcnum;
int visited[maxsize], father[maxsize];
int flag = 0;
void InitGraph(){
cout << "输入顶点数和边数: ";
cin >> vexnum >> arcnum;
for(int i = 0; i < vexnum; i++){
//初始化visited数组和father数组
visited[i] = 0;
father[i] = -1;
}
for(int i = 0; i < arcnum; i++){
int s, e;
cout << "请输入第" << i << "条边的起点和终点: ";
cin >> s >> e;
g[s][e] = 1;
g[e][s] = 1;
}
}
void DFS(int v){
visited[v] = 1;
for(int i = 0; i < vexnum; i++){
if(i != v && g[v][i] != INF){
//这里的判断是重点！！一次DFS且该节点不是从上一个节点过来的
if(visited[i] == 1 && father[v] != i){
flag = 1;
cout << "图存在环: ";
int tmp = v;
while(tmp != i){
cout << tmp << " ";
tmp = father[tmp];
}
cout << tmp << endl;
}else{
if(visited[i] == 0){
father[i] = v;
DFS(i);
}
}
}
}
visited[v] = 2;
}
int main(){
InitGraph();
for(int i = 0; i < vexnum; i++){
if(!visited[i])
DFS(i);
}
if(!flag)
cout << "图不存在环!" << endl;
return 0;
}
只需要将上述代码的无向图的构造过程改成有向图即可