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

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

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

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[]数组来代替布尔值visited[]数组，其中0表示“尚未访问”，“1表示正在进行中”，2表示“完成”。然后，当当前节点依赖于一个“正在进行”的节点时，您就知道您已经找到了一个周期。

我更喜欢使用Kahn的算法进行拓扑排序，它使用更少的堆栈空间并自动检测周期（它会将少于所有节点添加到结果中）。

卡恩的算法是这样的：

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!");
    }
}