方法一：拓撲排序
時間復(fù)雜度O(n^2)
比較常用的是用拓撲排序來判斷有向圖中是否存在環(huán)膘侮。
- 什么是拓撲排序呢？
我們先定義一條u到v的邊e=<u,v>,u<v;滿足這樣要求的序列稱為拓撲序列拓售，即前面節(jié)點小于后面節(jié)點签孔。所以瑰艘，拓撲序列可以有很多條。
生成拓撲序列的算法就叫拓撲排序啦~ - 算法流程描述
while(節(jié)點個數(shù)次（N）循環(huán)）
1.找出入度為0的節(jié)點u（節(jié)點個數(shù)次（N）循環(huán)）
2.刪去這個節(jié)點u和從這個節(jié)點出發(fā)相連的邊（<u,v1>,<u,v2>....,<u,vn>）僧须，更新這些邊連的點（v1,v2,v3....vn）的入度信息纲刀。
3.直到找不到入度為0的點（要是圖里節(jié)點刪完了（循環(huán)了N次）就是沒環(huán)，還剩節(jié)點就有環(huán)）担平。 - 代碼
#include<iostream>
#include<vector>
using namespace std;
#define MAXN 1000
int n, m;
vector<int> G[MAXN];
vector<int> topo;//存拓撲排序的序列
void read_graph()
{
cin >> n >> m;;
int u, v;//不帶邊權(quán)的圖
for (int e = 0; e < m; e++) {//有多少條邊
cin >> u >> v;
G[u].push_back(v);//有向圖
}
}
bool topoSort()
{
int indgree[MAXN] = { 0 };//入度信息
int visit[MAXN] = { 0 };
for (int i = 0; i < n; i++) {//初始化入度信息
for (int j = 0; j < G[i].size(); j++) {
indgree[G[i][j]]++;
}
}
int control=0;
while (control < n) {
int u = 0,i;
//找到入度為0的點
for (i=0; i < n; i++) {
if (!visit[i] && indgree[i] == 0) {
u = i;
break;
}
}
if (i == n) {//找不到入度為0的點退出循環(huán)
return false;
}
visit[u] = 1;//標記訪問過
topo.push_back(u);
for (int j = 0; j < G[u].size(); j++) {//更新入度信息
indgree[G[u][j]]--;
}
control++;
}
return true;//control=n 說明n個點都存入拓撲排序里示绊，是無環(huán)的
}
int main()
{
read_graph();
for (int i = 0; i < n; i++) {
cout << i<<":";
for (int j = 0; j < G[i].size(); j++) {
cout << G[i][j] << " ";
}
cout << endl;
}
if (topoSort()) {
for (int i = 0; i < topo.size(); i++) {
cout << topo[i] << " ";
}
}
else {
cout << "there exist circle" << endl;
}
}
上面這個復(fù)雜度要O(n^2)
看到用棧可以簡化到O(n+e); //鏈接
其實就是在找入度為0點的步驟那里做優(yōu)化:
把入度為0的點入棧暂论；
當棧不為空時面褐，更新棧頂節(jié)點連接頂點的入度信息，如果為0入棧
個人理解：和BFS的模板格式有點像取胎，一層一層的搜索展哭，這里用棧替代了上面代碼的visit數(shù)組，因為只對棧里的元素做操作闻蛀，自然是未訪問過的
DFS
時間復(fù)雜度O(V+E)
用兩個bool數(shù)組visited[]和recStack[]來記錄對節(jié)點 的訪問和入棧
- isCyclicUnit(int v) ----以v起點是否有環(huán)
- isCycle(int n) ----遍歷n 個節(jié)點匪傍，調(diào)用isCyclicUnit(i)
