在一个有向图中找环_有向图找环

目录索引:畅游面试中算法题集锦

有向图中边的分类

• 树边（Tree Edge）：从一个顶点指向其未访问过的子节点的边。
• 前向边（Forward Edge）：从一个顶点指向该顶点的一个非子顶点后裔的边，且接受点被访问过。
• 回边（Back Edge）：从一个顶点指向其祖先顶点的边。
• 横跨边（Cross Edge）：从一个顶点指向一个已完全访问过的顶点，且其中接受点既不是发起点的的后裔，也不是其祖先。
  

小规律：树边、前向边，都是往前指，即顺着bfs遍历的顺序；回边是往回指，即逆着bfs遍历的顺序；横跨边横着指，即边的两个端点没有祖先、后裔关系

Apporach:

深度优先遍历(DFS) 可用于检测图中的环。连通图的DFS生成树。只有当图中存在 回边(back edge) 时，图中才存在环。

回边(back edge) 是从一个节点到它自己(自循环)或DFS生成的树中它的一个祖先的边。

在下图中，有3条回边(back edge)，用十字标记。我们可以观察到，这3条后边表示图中存在3个环。

对于非联通的图，获取DFS树作为输出。要检测有没有环，通过检查**回边(back edge)**来检查单个树的有没有环。

为了检测回边(back edge)，跟踪函数递归堆栈中当前的顶点，用于DFS遍历。

如果到达的顶点已经在递归堆栈中，那么树中就存在一个环。

将当前顶点与递归堆栈中的顶点连接的边称为回边(back edge)。

用recStack[]数组来记录递归堆栈中的顶点。

Algorithm:

1. 使用给定数量的边和顶点建图。
2. 创建一个递归函数，初始化当前索引或顶点、visited和recursion stack。
3. 将当前节点标记为已访问，并在recursion stack中标记索引。
4. 找到所有未被访问且与当前节点相邻的顶点。递归地为这些顶点调用函数，如果递归函数返回true，则返回true。
5. 如果相邻的顶点已经在recursion stack中标记，则返回true。
6. 创建一个包装类，为所有顶点调用递归函数，如果任何函数返回true则返回true。否则，如果函数对所有顶点返回false返回false。

Implementation:

   static class Graph {
        public int V; //顶点的数量
        public List<List<Integer>> adj; // 邻接表

        public Graph(int V) {
            this.V = V;
            adj = new ArrayList<>();
            for (int i = 0; i < V; i++) {
                adj.add(new ArrayList<>());
            }
        }


        private void addEdge(int source, int dest) {
            adj.get(source).add(dest);
        }


        private boolean isCyclicUtil(int i, boolean[] visited, boolean[] recStack) {
            if (recStack[i]) return true;
            if (visited[i]) return false;
            visited[i] = true;
            recStack[i] = true;
            for (Integer next : adj.get(i)) {
                if (isCyclicUtil(next, visited, recStack)) return true;
            }
            recStack[i] = false;
            return false;
        }


        private boolean isCyclic() {
            boolean[] visited = new boolean[V];
            boolean[] recStack = new boolean[V];
            for (int i = 0; i < V; i++) {
                if(isCyclicUtil(i,visited,recStack)) return true;
            }
            return false;
        }


        public static void main(String[] args) {
            Graph graph = new Graph(4);
            graph.addEdge(0, 1);
            graph.addEdge(0, 2);
            graph.addEdge(1, 2);
            graph.addEdge(2, 0);
            graph.addEdge(2, 3);
            graph.addEdge(3, 3);

            if (graph.isCyclic())
                System.out.println("Graph contains cycle");
            else
                System.out.println("Graph doesn't contain 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
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56

Reference

• Detect Cycle in a Directed Graph