Jak sprawdzić, czy wykres skierowany jest acykliczny? A jak nazywa się ten algorytm? Byłbym wdzięczny za odniesienie.

Spróbowałbym posortować wykres topologicznie , a jeśli nie możesz, to ma cykle.

Wykonanie prostego przeszukiwania w głąb nie wystarczy, aby znaleźć cykl. Możliwe jest wielokrotne odwiedzanie węzła w DFS bez istniejącego cyklu. W zależności od tego, gdzie zaczynasz, możesz również nie przeglądać całego wykresu.

Możesz sprawdzić cykle w połączonym elemencie wykresu w następujący sposób. Znajdź węzeł, który ma tylko wychodzące krawędzie. Jeśli nie ma takiego węzła, istnieje cykl. Uruchom DFS w tym węźle. Podczas przechodzenia przez każdą krawędź sprawdź, czy krawędź wskazuje z powrotem do węzła już na stosie. Wskazuje to na istnienie cyklu. Jeśli nie znajdziesz takiej krawędzi, nie ma cykli w tym połączonym elemencie.

Jak zauważa Rutger Prins, jeśli twój wykres nie jest połączony, musisz powtórzyć wyszukiwanie na każdym podłączonym komponencie.

Jako odniesienie, silnie powiązany algorytm komponentów Tarjana jest ściśle powiązany. Pomoże Ci również znaleźć cykle, a nie tylko zgłosić, czy istnieją.

Lemat 22.11 dotyczący książki Introduction to Algorithms(wydanie drugie) stwierdza, że:

Graf skierowany G jest acykliczny wtedy i tylko wtedy, gdy przeszukiwanie G w głąb nie daje tylnych krawędzi

Rozwiązanie 1：Algorytm Kahna do sprawdzania cyklu . Główny pomysł: utrzymuj kolejkę, w której węzeł o zerowym stopniu zostanie dodany do kolejki. Następnie oddzielaj węzeł jeden po drugim, aż kolejka będzie pusta. Sprawdź, czy istnieją wewnętrzne krawędzie węzła.

Rozwiązanie 2 : Algorytm Tarjan do sprawdzania silnie połączonego komponentu.

Rozwiązanie 3 : DFS . Użyj tablicy liczb całkowitych do oznaczenia aktualnego stanu węzła: np. 0 - oznacza, że ​​ten węzeł nie był wcześniej odwiedzany. -1 - oznacza, że ​​ten węzeł był odwiedzany i jego węzły podrzędne są odwiedzane. 1 - oznacza, że ​​ten węzeł został odwiedzony i gotowe. Więc jeśli status węzła wynosi -1 podczas wykonywania DFS, oznacza to, że musi istnieć cykl.

Rozwiązanie podane przez ShuggyCoUk jest niekompletne, ponieważ może nie sprawdzić wszystkich węzłów.

def isDAG(nodes V):
    while there is an unvisited node v in V:
        bool cycleFound = dfs(v)
        if cyclefound:
            return false
    return true

Ma to złożoność czasową O (n + m) lub O (n ^ 2)

Wiem, że to stary temat, ale dla przyszłych poszukiwaczy tutaj jest implementacja C #, którą stworzyłem (bez twierdzenia, że ​​jest najbardziej wydajna!). Ma to na celu użycie prostej liczby całkowitej do identyfikacji każdego węzła. Możesz to udekorować w dowolny sposób, pod warunkiem, że obiekt węzła odpowiednio hashuje i jest równy.

W przypadku bardzo głębokich wykresów może to wiązać się z dużym narzutem, ponieważ tworzy hashset w każdym węźle na głębokości (są one niszczone na szerokość).

Wprowadzasz węzeł, z którego chcesz przeszukiwać, i ścieżkę do tego węzła.

• W przypadku wykresu z pojedynczym węzłem głównym wysyłasz ten węzeł i pusty hashset
• W przypadku wykresu z wieloma węzłami głównymi zawijasz to w foreach nad tymi węzłami i przekazujesz nowy pusty hashset dla każdej iteracji

• Podczas sprawdzania cykli poniżej dowolnego podanego węzła, po prostu przekaż ten węzeł wraz z pustym hashsetem

  private bool FindCycle(int node, HashSet<int> path)
  {
  
      if (path.Contains(node))
          return true;
  
      var extendedPath = new HashSet<int>(path) {node};
  
      foreach (var child in GetChildren(node))
      {
          if (FindCycle(child, extendedPath))
              return true;
      }
  
      return false;
  }
  

Podczas wykonywania DFS nie powinno być żadnej tylnej krawędzi. Śledź już odwiedzone węzły podczas wykonywania DFS, jeśli napotkasz krawędź między bieżącym węzłem a istniejącym węzłem, to wykres ma cykl.

oto szybki kod, aby sprawdzić, czy wykres ma cykle:

func isCyclic(G : Dictionary<Int,Array<Int>>,root : Int , var visited : Array<Bool>,var breadCrumb : Array<Bool>)-> Bool
{

    if(breadCrumb[root] == true)
    {
        return true;
    }

    if(visited[root] == true)
    {
        return false;
    }

    visited[root] = true;

    breadCrumb[root] = true;

    if(G[root] != nil)
    {
        for child : Int in G[root]!
        {
            if(isCyclic(G,root : child,visited : visited,breadCrumb : breadCrumb))
            {
                return true;
            }
        }
    }

    breadCrumb[root] = false;
    return false;
}


let G = [0:[1,2,3],1:[4,5,6],2:[3,7,6],3:[5,7,8],5:[2]];

var visited = [false,false,false,false,false,false,false,false,false];
var breadCrumb = [false,false,false,false,false,false,false,false,false];




var isthereCycles = isCyclic(G,root : 0, visited : visited, breadCrumb : breadCrumb)

Pomysł jest taki: normalny algorytm dfs z tablicą do śledzenia odwiedzanych węzłów i dodatkową tablicą, która służy jako znacznik dla węzłów, które prowadziły do ​​bieżącego węzła, dzięki czemu kiedykolwiek wykonamy dfs dla węzła ustawiamy odpowiadający jej element w tablicy znaczników jako prawdziwy, aby kiedykolwiek napotkany już odwiedzony węzeł sprawdzał, czy odpowiadający mu element w tablicy znaczników jest prawdziwy, jeśli jest prawdziwy, to jest to jeden z węzłów, które sobie wpuszczają (stąd cycle), a sztuczka polega na tym, że za każdym razem, gdy dfs węzła zwraca, ustawiamy odpowiadający mu znacznik z powrotem na false, więc jeśli odwiedzimy go ponownie z innej trasy, nie damy się zwieść.

Właśnie miałem to pytanie w wywiadzie dla Google.

Sortowanie topologiczne

Możesz spróbować posortować topologicznie, czyli O (V + E), gdzie V to liczba wierzchołków, a E to liczba krawędzi. Graf skierowany jest acykliczny wtedy i tylko wtedy, gdy można to zrobić.

Rekurencyjne usuwanie liści

Rekurencyjnie usuwają węzły liści, dopóki ich nie ma, a jeśli pozostał więcej niż jeden węzeł, masz cykl. O ile się nie mylę, to jest O (V ^ 2 + VE).

W stylu DFS ~ O (n + m)

Jednak skuteczny algorytm DFS w najgorszym przypadku O (V + E) to:

function isAcyclic (root) {
    const previous = new Set();

    function DFS (node) {
        previous.add(node);

        let isAcyclic = true;
        for (let child of children) {
            if (previous.has(node) || DFS(child)) {
                isAcyclic = false;
                break;
            }
        }

        previous.delete(node);

        return isAcyclic;
    }

    return DFS(root);
}

Oto moja implementacja algorytmu węzła peel off leaf w Ruby .

def detect_cycles(initial_graph, number_of_iterations=-1)
    # If we keep peeling off leaf nodes, one of two things will happen
    # A) We will eventually peel off all nodes: The graph is acyclic.
    # B) We will get to a point where there is no leaf, yet the graph is not empty: The graph is cyclic.
    graph = initial_graph
    iteration = 0
    loop do
        iteration += 1
        if number_of_iterations > 0 && iteration > number_of_iterations
            raise "prevented infinite loop"
        end

        if graph.nodes.empty?
            #puts "the graph is without cycles"
            return false
        end

        leaf_nodes = graph.nodes.select { |node| node.leaving_edges.empty? }

        if leaf_nodes.empty?
            #puts "the graph contain cycles"
            return true
        end

        nodes2 = graph.nodes.reject { |node| leaf_nodes.member?(node) }
        edges2 = graph.edges.reject { |edge| leaf_nodes.member?(edge.destination) }
        graph = Graph.new(nodes2, edges2)
    end
    raise "should not happen"
end

Możesz użyć odwrócenia cyklu znajdowania z mojej odpowiedzi tutaj https://stackoverflow.com/a/60196714/1763149

def is_acyclic(graph):
    return not has_cycle(graph)