时间戳

首页 > 解决方案 > 在有向无环图中检测循环引用

java - 在有向无环图中检测循环引用

问题描述

目前我正在使用此示例进行拓扑排序并进行一些修改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”先完成。

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

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

谢谢

标签： javaalgorithmgraphdirected-acyclic-graphscircular-reference

解决方案

boolean visited[]您可以使用数组代替int state[]数组，其中 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!");
    }
}

推荐阅读