Обнаружение циклических ссылок в направленном ациклическом графе

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

Вместо массива boolean visited[] можно использовать массив int state[], где 0 означает «еще не посещен», 1 означает «выполняется», а 2 означает «выполнено».Затем, когда текущий узел зависит от того, который находится «в процессе», вы знаете, что нашли цикл.

Я предпочитаю выполнять топологическую сортировку с помощью алгоритма Кана (см. https://en.wikipedia.org/wiki/Topological_sorting#Kahn's_algorithm),, который использует меньше стекапробел и автоматически определяет циклы (это добавит меньше, чем все узлы к результату).

Алгоритм Кана на вашем графике будет выглядеть так:

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