#Cycle Detection

问题

给定这样一个问题,怎么解? > Directed cycle detection. Does a given digraph have a directed cycle? If so, find the vertices on some such cycle, in order from some vertex back to itself.

问题是给定一个有向图,请问图中是否有环?如果有,请打印路径。假定给出下图中左边有向图,求解此图是否有圈。当然下图太简单,一看就能看出来一个有圈。但如果换成右图,就不是那么直接了。

10 个 vertexs 的有向图

略复杂的有向图[1]

解题思路

一旦涉及到图的问题,不是上 DFS (深度优先搜索) 就是 BFS (广度优先搜索)。这里的问题明显的深度优先处理,对每一条可能的路径做有无圈的检测。

总结以上分析,检测算法需要如下数据结构和变量:

实现

下面是 C 的实现。首先是 main 函数。其中 graph 的创建省略。

1
2
3
4
int main(){
  Graph* graph = creatGraph();
  detectCycle(graph);
}

然后到 detectCycle 方法。

1
2
3
4
5
6
7
8
9
10
void detectCycle(Graph* graph){
  // createBooleanArray 创建 V 个元素的 boolean 数组,V = 图中点个数
  bool* marked = createBooleanArray(graph->V);
  int* edgeTo = malloc(graph->V*(sizeof(int)));
  bool* onStack = createBooleanArray(graph->V);
  Stack* cycle = NULL;
  // 从 0 开始作为原点,遍历
  for(int pivot =0; pivot< graph->V; pivot++)
    dfs(graph, pivot, marked, edgeTo, onStack, cycle);
};

dfs 方法的关键点在于循环中的检测。如果检测到该临点点已经访问过(marked[point] = true),则不处理。如果检测到临点已经在路线中,则认为检测到圈(onStack[point] = true),生成圈(cycle)。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
void dfs(Graph* graph, int pivot, bool* marked, int* edgeTo, 
  bool* onStack, Stack* cycle){
  marked[pivot] = true;
  onStack[pivot] = true;
  AdjListNode* adjListNode = graph->array[pivot].head;
  while(adjListNode){
    if(cycle){
      return;
    }else if(!marked[adjListNode->dest]){
      // 如果当前的邻居是第一次到达,则建立 pivot 和 邻居之间的关联, 同时对邻居开始做 recursive
      edgeTo[adjListNode->dest] = pivot;
      dfs(graph, adjListNode->dest, marked, edgeTo, onStack);
    }else if(onStack[adjListNode->dest]){
      // 当前邻居已经到过了,那么就去判断这个邻居是不是在 stack 上,如果在,则说明形成了环路
      printf("--- cycle detected. ---\n");
      cycle = StackCreate();
      for(int x = pivot; x != adjListNode->dest; x=edgeTo[x])
        StackPush(cycle, x);
      StackPush(cycle, adjListNode->dest);
      StackPush(cycle, pivot);
      while(!IsEmpty(cycle)){
        printf("->%i ", StackTop(cycle));
        StackPop(cycle);
      }
      printf("\n");
    }
    adjListNode = adjListNode->next; // 指向下一个邻居
  }
  // 所有的邻居都处理完了,则也就是这个节点开始的对邻居的遍历也结束了,那么这个点就不在 stack 上了
  onStack[pivot] = false;
};

下面这张图[2]是演示递归的过程。这里发现的圈是 3 -> 5 -> 4 ->3。

再看实现

其实以上的实现会把图中所有的圈都找出来。但如果希望检测到圈就停止,该怎么办?

<未完>