寻找 有向图/无向图 所有环路的DFS暴力求解法(ps:C++代码，复杂度爆炸警告，生产环境慎用)_有向无环图 代码证明

思路：

1、DFS算法可以求解图中从一点到另一点的全部路径。

2、通过枚举所有顶点$V_i$的邻接点$v_i$，然后通过DFS寻找枚举点$v_i$到$V_i$的所有路径来寻找环路。

3、思路很简单，但是算法复杂度确实是太高了。

下面上代码：

#include <iostream>
#include <vector>
#include <algorithm>
 
using namespace std;
 
const int M = 100;
int n, e, G[M][M];
bool vis[M];
 
//初始化图
void initGraph() { 
	cin >> n >> e;
	int ti, tj;
	for (int i = 0; i < e; i++) {
		cin >> ti >> tj;
		G[ti][tj] = 1;
	}
}
 
 
vector<vector<int>> finalResult; //存储最终的所有找到的环
vector<int> path;	//dfs路径栈
 
//判断两个无序的vector内元素是否完全一样
bool isSame(vector<int> v1,vector<int> v2) {
	if (v1.size() != v2.size()) {
		return false;
	} else {
		sort(v1.begin(),v1.end());
		sort(v2.begin(),v2.end());
		return v1==v2;
	}
}
//判断t在finalResult是否已经存在
bool isExist(vector<int> &t) {
	for (int i = 0; i < finalResult.size(); i++) {
		if (isSame(finalResult[i], t)) {
			return true;
		}
	}
	return false;
}
//打印路径
void printPath(int &begin) {
	cout << begin << " ";
	for (int i = 0; i < path.size(); i++) {
		cout << path[i] << " ";
	}
	cout << endl;
}
//dfs寻找起点s到终点d的全部路径
void dfs(int s, int d,int &begin) {
	if (s==d) {
		path.push_back(s);
		if (path.size() > 2 && !isExist(path)) {
			printPath(begin);
			finalResult.push_back(path);
		}
		path.pop_back();
		vis[s] = false;
		return;
	}
	vis[s] = true;
	path.push_back(s);
	for (int i = 0; i < n; i++) {
		if (!vis[i] && G[s][i]==1) {
			dfs(i,d,begin);
		}
	}
	vis[s] = false;
	path.pop_back();
}
//调用dfs函数寻找该图的所有环路
void findAllCircle() {
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n; j++) {
			if (G[i][j]==1) {
				dfs(j, i, i);
				fill(vis, vis + n, false);
				path.clear();
			}
		}
	}
}
int main() {
	initGraph();
	findAllCircle();
	return 0;
}

---测试用例---

格式：

顶点数n [空格] 边数e
边1的出点 [空格] 边1的入点
边2的出点 [空格] 边2的入点
边3的出点 [空格] 边3的入点
...
边e的出点 [空格] 边e的入点

输入：(有向图)

6 7
0 1
0 2
2 3
2 4
3 4
4 0
1 5

输出：

无向图修改一下建图代码即可。