如何判断一个图是否有环

如何判断一个图是否有环2015-02-15对于无向图

算法1

我们知道对于环1-2-3-4-1，每个节点的度都是2，基于此我们有如下算法（这是类似于有向图的拓扑排序）：

求出图中所有顶点的度，

删除图中所有度<=1的顶点以及与该顶点相关的边，把与这些边相关的顶点的度减一

如果还有度<=1的顶点重复步骤2

最后如果还存在未被删除的顶点，则表示有环；否则没有环

时间复杂度为O（E+V），其中E、V分别为图中边和顶点的数目，这个算法我们稍后分析算法3的时候再分析。

算法2

深度优先遍历该图，如果在遍历的过程中，发现某个节点有一条边指向已经访问过的节点，并且这个已访问过的节点不是当前节点的父节点（这里的父节点表示dfs遍历顺序中的父节点），则表示存在环。但是我们不能仅仅使用一个bool数组来标志节点是否访问过。如下图

从节点1开始遍历-接着遍历2-接着遍历3，然后发现3有一条边指向遍历过的1，则存在环。但是回到1节点时，它的另一条边指向已访问过的3，又把这个环重复计算了一次。

我们按照算法导论22.3节深度优先搜索中，对每个节点分为三种状态，白、灰、黑。开始时所有节点都是白色，当开始访问某个节点时该节点变为灰色，当该节点的所有邻接点都访问完，该节点颜色变为黑色。那么我们的算法则为：如果遍历的过程中发现某个节点有一条边指向颜色为灰的节点，那么存在环。则在上面的例子中，回溯到1节点时，虽然有一条边指向已经访问过的3，但是3已经是黑色，所以环不会被重复计算。

下面的代码中visit数组的值分为0 1 2三种状态分别代表白色、灰色、黑色，调用函数dfs可以输出图中存在的所有环，图用邻接矩阵表示，如果两个节点之间没有边则对应的值为INT_MAX

void dfsVisit（vector<vector<int> >&graph, int node, vector<int>&visit, vector<int>&father）{int n = graph.size（）;visit[node] = 1;//cout<<node<<"-
";for（int i = 0; i < n; i++）if（i ！= node && graph[node][i] ！= INT_MAX）{if（visit[i] == 1 && i ！= father[node]）//找到一个环{int tmp = node;cout<<"cycle: ";while（tmp ！= i）{cout<<tmp<<"->";tmp = father[tmp];}cout<<tmp<<endl;}else if（visit[i] == 0）{father[i] = node;dfsVisit（graph, i, visit, father）;}}visit[node] = 2;} void dfs（vector<vector<int> >&graph）{int n = graph.size（）;vector<int> visit（n, 0）; //visit按照算法导论22.3节分为三种状态vector<int> father（n, -1）;// father[i] 记录遍历过程中i的父节点for（int i = 0; i < n; i++）if（visit[i] == 0）dfsVisit（graph, i, visit, father）;}

算法时间复杂度也是O（E+V）