方法一：拓扑排序

时间复杂度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)

本文主要针对如何判断有向图/无向图中是否存在环的问题进行简单的论述。

一 无向图

1.利用DFS进行判断

利用DFS判断有向图是否存在环，是最为常用的一种方法，虽然这种方法很常用，但可参考的代码的实现比较少，下面对这种方法及其实现进行详细的阐述。

首先，利用DFS判断无向图中是否换的原理是：若在深度优先搜索的过程中遇到回边(即指向已经访问过的顶点的边)，则必定存在环。

所以说，是否存在环的关键在于是否存在满足条件的“回边”，那么如何判断回边呢？

(1)首先，对图中的所有顶点定义三种状态：顶点未被访问过、顶点刚开始被访问、顶点被访问过并且其所有邻接点也被访问过。这三种状态，在visited数组中分别用0、1、2来表示。那么，存在环的情况可以定义为：在遍历过程中，发现某个顶点的一条边指向状态1的顶点，此时就存在环。状态2可以理解为其生成树上的所有的子孙节点都已经访问完。

(2)此外，我们要定义一个father数组，用以存储在DFS过程中顶点的父顶点(或者说是生成树上的父节点)。其主要作用是为了区分邻接点中环中的顶点和遍历过程中的父节点 (单纯的用visited数组无法区分)。

整个过程的实现代码如下：

#define MAX_NUM 100

#define INF 0x7fffffff

/*DFS判断无向图中是否有环*/

class Graph

{

public:

int vertexNum;//顶点个数

int arcNum;//弧的个数

int vertex[MAX_NUM];//顶点表

int arc[MAX_NUM][MAX_NUM];//弧信息表

};

int visited[MAX_NUM];//顶点访问表

int father[MAX_NUM];//父节点表

void DFS(int v,Graph G)

{

visited[v] = 1;

for(int i = 0 ; i < G.vertexNum; i++)

{

if(i != v && G.arc[v][i] != INF)//邻接矩阵中节点v的邻接点

{

if(visited[i] == 1 && father[v] != i)//vi不是父节点，而且还访问过(而且为状态1，说明不是回溯过来的顶点)，说明存在环(判断i不是v的父节点)

{

cout<

int temp = v;

while(temp != i)

{

cout<

temp = father[temp];

}

cout<

}

else

if(visited[i] == 0)

{

father[i] = v;//更新father数组

DFS(i,G);

}

}

}

visited[v] = 2;//遍历完所有的邻接点才变为状态2

}

void DFSTraverse(Graph G)

{

memset(visited,0,sizeof(visited));

memset(father,-1,sizeof(father));

for(int i = 0 ; i < G.vertexNum; i++)

if(!visited[i])

DFS(i,G);

}

由此可见，visited数组相对于一般的情况，增加了个状态2，主要是为了防止在回溯过程中进行误判。所以才能仅用father数组和状态1判断存在环。

状态2可以理解为其生成树上的所有的子孙节点都已经访问完。

由于使用的是邻接矩阵来存储，所以该算法的时间复杂度为O(n^2),空间复杂度为O(n)。

2.其他方法本文不再详述。

二 有向图

1.拓扑排序

关于拓扑排序，资料很多，本文不再详述其原理，只给出其实现代码，代码如下：

#include

#include

#include

#include

#include

#include

#include

#include

#include

#include

#include

using namespace std;

#define MAX_NUM 100

#define INF 0x7fffffff

/*拓扑排序*/

int indegree[MAX_NUM];//用以表示每个顶点的入度

bool visited[MAX_NUM];//用以表示该顶点是否入栈

class Graph

{

public:

int vertexNum;//顶点个数

int arcNum;//弧的个数

int vertex[MAX_NUM];//顶点表

int arc[MAX_NUM][MAX_NUM]= {{0,1,1},{INF,0,1},{INF,INF,0}}; //弧信息表

};

void Initindegree(Graph G)//初始化入度数组

{

memset(indegree,0,sizeof(indegree));

for(int i = 0; i < G.vertexNum; i++)

for(int j = 0; j < G.vertexNum; j++)

{

if(i != j && G.arc[i][j] != INF)

indegree[j]++;//注意此处增加的是顶点vj的入度

}

memset(visited,0,sizeof(visited));

}

bool TuoPu(Graph G)

{

stack s;

int cnt = 0;//用于记录拓扑序列中节点的个数

for(int i = 0 ; i < G.vertexNum; i++)

if(indegree[i] == 0)

{

s.push(i);

visited[i] = true;//修改入栈顶点的入栈标记数组

}

while(!s.empty())

{

int v = s.top();

cnt++;//顶点出栈得到时候，计数器加1

s.pop();

for(int i = 0; i < G.vertexNum; i++)

{

if(v != i && G.arc[v][i] != INF && visited[i] == false)//将所有顶点v的未入栈的邻接点的入度都减去1

{

indegree[i]--;

if(indegree[i] == 0)//如果减1后入度为0了，此时需要将该邻接点入栈，且修改入栈标记数组

{

visited[i] = true;

s.push(i);

}

}

}

}

return cnt == G.vertexNum ? true : false;

}

int main()

{

Graph G;

G.vertexNum = 3;

Initindegree(G);

cout<

}

2.利用改进的DFS

对于有向图的话，如果直接应用一般的DFS的话，会出现误判的情况，一个典型的例子是：A->B,A->C->B,我们用DFS来处理这个图，我们会得出它有环，但实际上并没有。然而，本文中所说的无向图的DFS判断算法完全可以直接应用到有向图中来，即上述代码可以直接应用到有向图中来。所以说上述的DFS算法(或称为为改进的DFS算法)既适用于无向图，也适用于有向图。其对应的原理适用于这两种图，即只要我们在遍历过程中，只要发现一个顶点不是当前节点的父节点，同时他还被访问过了(状态为1)，那么就可以认为此处存在环。(通常在DFS中一个顶点的未被访问的邻接点，相当于生成树中的该顶点的子孙节点)