杭州高瑞网站建设/网络营销服务企业有哪些
方法一：拓扑排序
时间复杂度O(n^2)
比较常用的是用拓扑排序来判断有向图中是否存在环。
什么是拓扑排序呢？
我们先定义一条u到v的边e=,u
生成拓扑序列的算法就叫拓扑排序啦~
算法流程描述
while(节点个数次(N)循环)
1.找出入度为0的节点u(节点个数次(N)循环)
2.删去这个节点u和从这个节点出发相连的边(,....,)，更新这些边连的点(v1,v2,v3....vn)的入度信息。
3.直到找不到入度为0的点(要是图里节点删完了(循环了N次)就是没环，还剩节点就有环)。
代码
#include
#include
using namespace std;
#define MAXN 1000
int n, m;
vector G[MAXN];
vector topo;//存拓扑排序的序列
void read_graph()
{
cin >> n >> m;;
int u, v;//不带边权的图
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的点退出循环
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个点都存入拓扑排序里，是无环的
}
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;
}
}
上面这个复杂度要O(n^2)
看到用栈可以简化到O(n+e); //链接
其实就是在找入度为0点的步骤那里做优化:
把入度为0的点入栈；
当栈不为空时，更新栈顶节点连接顶点的入度信息，如果为0入栈
个人理解：和BFS的模板格式有点像，一层一层的搜索，这里用栈替代了上面代码的visit数组，因为只对栈里的元素做操作，自然是未访问过的
DFS
时间复杂度O(V+E)
用两个bool数组visited[]和recStack[]来记录对节点 的访问和入栈
- isCyclicUnit(int v) ----以v起点是否有环
- isCycle(int n) ----遍历n 个节点，调用isCyclicUnit(i)