检测有向无环图中的循环引用

Question

目前我正在使用此样本进行拓扑排序并进行一些修改https://www.geeksforgeeks.org/topological-sorting/

import java.util.ArrayList;
import java.util.Iterator;
import java.util.LinkedList;
import java.util.Stack;

public class CalcGraph {

    private int V; // No. of vertices

    private LinkedList<Integer> adj[]; // Adjacency List

    private ArrayList<Integer> result;

    // Constructor
    public CalcGraph(int v) {
        V = v;
        result = new ArrayList<>();
        adj = new LinkedList[v];
        for (int i = 0; i < v; ++i)
            adj[i] = new LinkedList();
    }

    public ArrayList<Integer> getResult() {
        return result;
    }

    public void setResult(ArrayList<Integer> result) {
        this.result = result;
    }

    // Function to add an edge into the graph
    public void addEdge(int v, int w) {
        adj[v].add(w);
    }

    // A recursive function used by topologicalSort
    public void topologicalSortUtil(int v, boolean visited[], Stack<Integer> stack) {
        // Mark the current node as visited.
        visited[v] = true;
        Integer i;

        // Recur for all the vertices adjacent to this
        // vertex
        Iterator<Integer> it = adj[v].iterator();
        while (it.hasNext()) {
            i = it.next();
            if (!visited[i])
                topologicalSortUtil(i, visited, stack);
        }

        // Push current vertex to stack which stores result
        stack.push(new Integer(v));
    }

    public void topologicalSort() {
        Stack<Integer> stack = new Stack<Integer>();

        // Mark all the vertices as not visited
        boolean visited[] = new boolean[V];
        for (int i = 0; i < V; i++)
            visited[i] = false;

        // Call the recursive helper function to store
        // Topological Sort starting from all vertices
        // one by one
        for (int i = 0; i < V; i++)
            if (visited[i] == false)
                topologicalSortUtil(i, visited, stack);

        // Print contents of stack
        while (stack.empty() == false) {
            int graphId = stack.pop();
            result.add(graphId);
        }
    }
}

我用它来排序要求解的变量的顺序。

示例，

a = b + c
b = c + d
c = 7
d = c + 1

每个变量都有一个唯一的整数分配给它并存储在映射中

{
    "1" : { "id" : "a", "child": [b, c]},
    "2" : { "id" : "b", "child": [c, d]},
    "3" : { "id" : "c", "child": []},
    "4" : { "id" : "d", "child": [c]}
}

创建图形和添加边时，一共有4个顶点所以我的代码将构建这样的图作为结果

CalcGraph g = new CalcGraph(6);
g.addEdge(1, 2);
g.addEdge(1, 3);
g.addEdge(2, 3);
g.addEdge(2, 4);
g.addEdge(4, 3);

排序后倒序得到结果是正确的 c > d > b > a

一切正常，但我需要检测图中的循环引用。假设变量是

a = b + c + d
b = c + d
c = 7
d = c + e
e = a + 1

存在循环引用，"e"需要"a"完成，但"a"需要"b"、"c"、"d" , 并且 "e" 首先完成。

我不确定如何使用有向无环图检查循环引用。

还是使用不同的数据结构来检查循环引用更好？即树

谢谢

Answer 1

您可以使用 int state[] 数组代替 boolean visited[] 数组，其中 0 表示“尚未访问”，1 表示 'in progress'，2 表示 'done' .那么当当前节点依赖的那个是'in progress'，你就知道你找到了一个循环。

我更喜欢使用 Kahn's algorithm 进行拓扑排序，它使用较少的堆栈 space 并自动检测循环（它将少于所有节点添加到结果中）。

卡恩在你的图表上的算法看起来像这样：

public void topologicalSort() {
    result.clear();

    // calculate in-degrees

    int in_degree = new int[V]; //initialized to zeros
    for (int i = 0; i < V; ++i) {
        for(Integer target: adj[i]) {
          ++in_degree[target];
        }
    }

    // add start nodes to result

    for (int i = 0; i < V; ++i) {
        if (in_degree[i]==0) {
            result.add(i);
        }
    }

    // uncount edges from added nodes to find new nodes to add

    for (int scanpos=0; scanpos < result.size(); ++scanpos) {
        for(Integer target: adj[result.get(scanpos)]) {
            if (--in_degree[target] == 0) {
                result.add(target);
            }
        }
    }
    
    //done
    if (result.size() < V) {
        throw new RuntimeException("Ack! a cycle!");
    }
}

检测有向无环图中的循环引用

Detecting circular references in Directed acyclic graph

java

algorithm

graph

directed-acyclic-graphs

circular-reference