判断无向图和有向图是否有回路

一、无向图回路的判断

    对于无向图，判断其是否有回路有四种方法，如下所示：

    1、利用深度优先搜索DFS，在搜索过程中判断是否会出现后向边（DFS中，连接顶点u到它的某一祖先顶点v的边），即在DFS对顶点进行着色过程中，若出现所指向的顶点为黑色，则此顶点是一个已经遍历过的顶点（祖先），出现了后向边，若完成DFS后，则图中有回路；

    2、在图的邻接表表示中，首先统计每个顶点的度，然后重复寻找一个度为1的顶点，将度为1和0的顶点从图中删除，并将与该顶点相关联的顶点的度减1，然后继续反复寻找度为1的，在寻找过程中若出现若干顶点的度都为2，则这些顶点组成了一个回路；否则，图中不存在回路。

    3、利用BFS，在遍历过程中，为每个节点标记一个深度deep，如果存在某个节点为v，除了其父节点u外，还存在与v相邻的节点w使得deep[v]<=deep[w]的，那么该图一定存在回路；
    4、用BFS或DFS遍历，最后判断对于每一个连通分量当中，如果边数m>=节点个数n，那么改图一定存在回路。因此在DFS或BFS中，我们可以统计每一个连通分量的顶点数目n和边数m，如果m>=n则return false；直到访问完所有的节点，return true。

二、有向图回路的判断

    对于有向图，判断其是否有回路的方法也有两种，如下所示：

    1、与无向图类似，若在DFS中出现后向边，即存在某一顶点被第二次访问到，则有回路出现；

    2、同样，利用拓扑排序的思想，通过这一步骤来执行拓扑排序，即重复寻找一个入度为0的顶点，将该顶点从图中删除，并将该顶点及其所有的出边从图中删除（即与该点相应的顶点的入度减1），最终若途中全为入度为1的点，则这些点至少组成一个回路。

    对于有向图，具体点就可得到如下分析：

    问题分析：如果图中存在回路，则必包含一个子图为回路。即该子图中所有顶点入度不为0且至少有边指向另外的顶点。
    算法：
    步骤1：按邻接表方式存储图。遍历与每个节点关联的边并统计每个节点的入度。需要O(n+m)次的运算。
    步骤2：删除所有入度为零的顶点及其相发出的边。并将被删除边所指向的顶点的入度减1。
    重复步骤2直到：
    （1）所有顶点被删除（则没有回路）或；
    （2）还有顶顶点但没有入度为零的顶点可删除（则存在回路）。
    算法复杂度分析：
    由于步骤二中的删除边的操作运算复杂度为O(m),删除节点的操作为O(n) 判断节点入度是否为0需要O(n+m)次运算。其中O(n)次为初始入度为零的节点,O(m)次为删除边后导致的入度为零的节点。于是整个算法复杂度为O(m+n)。