Wyszukiwanie topologiczne i pierwsze wyszukiwanie zakresu

Question

Czy możliwe jest wykorzystanie logiki pierwszego zasięgu do zrobienia topologicznego rodzaju DAG? Rozwiązanie w Cormen korzysta z pierwszego wyszukiwania Głębia, ale czy nie byłoby łatwiej używać BFS?

Powód: BFS odwiedzi wszystkie węzły na określonej głębokości przed odwiedzeniem węzłów z następną wartością głębokości. Oznacza to oczywiście, że rodzice zostaną wymienieni przed dziećmi, jeśli zrobimy BFS. Czy nie jest to dokładnie to, czego potrzebujemy do topologicznego rodzaju?

Answer 1

W BFS wszystkie krawędzie, po których faktycznie chodzisz, znajdą się we właściwym kierunku. Ale wszystkie krawędzie, na których nie chodzisz (między węzłami na tej samej głębokości lub z głębszych węzłów z powrotem do wcześniejszych węzłów) zakończą się niewłaściwym sposobem, jeśli rozmieścisz wykres w kolejności BFS.

Tak, naprawdę potrzebujesz systemu plików DFS, aby to zrobić.

Answer 2

Jest to możliwe, nawet wikipedia describes an algorithm based on BFS.

Zasadniczo używa się kolejki, w której wstawia się wszystkie węzły bez żadnych krawędzi wejściowych. Następnie, po wyodrębnieniu węzła, usuwane są wszystkie jego wychodzące krawędzie i wstawiane z niego węzły, które nie mają innych przychodzących krawędzi.

Answer 3

zwykłego BFS jest wystarczające tylko dla drzewa (lub lasu drzew), ponieważ w (lasu) Drzewa, In-stopnie są co najwyżej 1. Teraz przyjrzeć tym przypadku:

B → C → D 
     ↗ 
    A 

A BFS, gdzie kolejka jest inicjowana na A B (której in-degrees są równe zero) zwróci A B D C, która nie jest sortowana topologicznie. Dlatego musisz utrzymywać liczbę stopni w stopniach i wybierać tylko te węzły, których liczba spadła do zera. (*)

BTW, to jest wadą twojego "powodu": BFS gwarantuje tylko, że jeden rodzic został odwiedzony wcześniej, nie wszystkie.

Edit: (*) Innymi słowy odepchnąć sąsiednie węzły w których wynosi zero stopni (w exemple, po przetworzeniu A, D byłyby pominięte). Nadal używasz kolejki i właśnie dodałeś krok filtrowania do ogólnego algorytmu. To powiedziawszy, nadal nazywa się to BFS jest wątpliwe.

Answer 4

Tak, możesz sortować topologicznie za pomocą BFS. Właściwie to przypomniałem sobie raz, gdy mój nauczyciel powiedział mi, że jeśli problem można rozwiązać przez BFS, nigdy nie rozwiąż go przez DFS. Ponieważ logika dla BFS jest prostsza niż DFS, przez większość czasu zawsze będziesz potrzebować prostego rozwiązania problemu.

Jak YvesgereY i IVlad wspomniał, trzeba zacząć od węzłów którego indegree jest , czyli żadne inne węzły bezpośrednio do nich. Najpierw dodaj te węzły do ​​swojego wyniku. Możesz użyć mapy HashMap do mapowania każdego węzła z jego indegree oraz kolejki, która jest bardzo często spotykana w BFS, aby wspomóc twoje przemierzanie. Podczas odpytywania węzła z kolejki, liczba jego sąsiadów musi zostać zmniejszona o 1, to jest jak usunięcie węzła z wykresu i usunięcie krawędzi między węzłem a jego sąsiadami. Za każdym razem, gdy natkniesz się na węzły o wartości 0, przekaż je do kolejki, aby później sprawdzić ich sąsiadów i dodaj do wyniku.

public ArrayList<DirectedGraphNode> topSort(ArrayList<DirectedGraphNode> graph) { 

    ArrayList<DirectedGraphNode> result = new ArrayList<>(); 
    if (graph == null || graph.size() == 0) { 
     return result; 
    } 
    Map<DirectedGraphNode, Integer> indegree = new HashMap<DirectedGraphNode, Integer>(); 
    Queue<DirectedGraphNode> queue = new LinkedList<DirectedGraphNode>(); 

    //mapping node to its indegree to the HashMap, however these nodes 
    //have to be directed to by one other node, nodes whose indegree == 0 
    //would not be mapped. 
    for (DirectedGraphNode DAGNode : graph){ 
     for (DirectedGraphNode nei : DAGNode.neighbors){ 
      if(indegree.containsKey(nei)){ 
       indegree.put(nei, indegree.get(nei) + 1); 
      } else { 
       indegree.put(nei, 1); 
      } 
     } 
    } 


    //find all nodes with indegree == 0. They should be at starting positon in the result 
    for (DirectedGraphNode GraphNode : graph) { 
     if (!indegree.containsKey(GraphNode)){ 
      queue.offer(GraphNode); 
      result.add(GraphNode); 
     } 
    } 


    //everytime we poll out a node from the queue, it means we delete it from the 
    //graph, we will minus its neighbors indegree by one, this is the same meaning 
    //as we delete the edge from the node to its neighbors. 
    while (!queue.isEmpty()) { 
     DirectedGraphNode temp = queue.poll(); 
     for (DirectedGraphNode neighbor : temp.neighbors){ 
      indegree.put(neighbor, indegree.get(neighbor) - 1); 
      if (indegree.get(neighbor) == 0){ 
       result.add(neighbor); 
       queue.offer(neighbor); 
      } 
     } 
    } 
    return result; 
}