Topolojik arama ve Genişlik ilk arama

Question

DAG'nin topolojik bir türünü yapmak için Breadth ilk arama mantığını kullanmak mümkün mü? Cormen'deki çözüm, ilk önce Derin Arama'yı kullanıyor ancak BFS'yi kullanmak daha kolay olmaz mı?

Sebep: BFS, bir sonraki derinlik değerine sahip düğümleri ziyaret etmeden önce tüm düğümleri belirli bir derinlikte ziyaret eder. Doğal olarak, BFS yaparsak ebeveynlerin çocuklardan önce listeleneceği anlamına gelir. Topolojik sıralama için tam olarak ihtiyacımız olan şey bu değil mi?

Answer 1

Bir BFS'de, aslında yürüdüğünüz tüm kenarlar doğru yönde sonuçlanır. Ancak, çizmediğiniz tüm kenarlar (aynı derinlikte düğümler arasındaki veya daha derin düğümlerden daha önceki düğümlere kadar olanlar), grafiği BFS düzeninde düzenlerseniz yanlış yöne gider.

Evet, bunu yapmak için gerçekten DFS'ye ihtiyacınız var.

Answer 2

Ayrıca, describes an algorithm based on BFS wikipedia da mümkündür.

Temel olarak, tüm düğümleri gelen kenarları girmeyeceğiniz bir sıra kullanın. Daha sonra, bir düğümü ayıkladığınızda, tüm giden kenarlarını kaldırın ve diğer gelen kenarları olmayan ondan erişilebilen düğümleri yerleştirin.

B → C → D 
     ↗ 
    A 

: (ormanına) ağaçlar, in-derece bu durumda bakmak, Şimdi en fazla 1. çünkü

Answer 3

Saf bir BFS

, sadece bir ağaç için yeterli (veya ağaçların orman) 'dir

Sıranın A B (başlangıç ​​derecesi sıfır olan) olarak başlatıldığı bir BFS, topolojik olarak sıralanmamış olan A B D C döndürecektir. Bu yüzden, derece sayımını korumalı ve sadece sayısı sıfıra düşmüş olan düğümleri seçmelisin. (*)

BTW, bu sizin 'mantığınızın' kusurudur: BFS, yalnızca bir ebeveynin daha önce ziyaret edilmesini garanti eder, hepsi değil.

Düzenleme: (*) Başka bir deyişle, olan-derece sıfır bitişik düğümlerin yönlendirme (A işlendikten sonra, exemple de, D atlanan olacaktır). Yani, hala bir sıra kullanıyorsunuz ve sadece genel algoritmaya bir filtreleme adımı eklediniz. Demek ki, BFS olarak adlandırmaya devam etmek tartışmalıdır.

Answer 4

Evet, BFS kullanarak topolojik sıralama yapabilirsiniz. Aslında, bir keresinde öğretmenimin bana sorunun BFS tarafından çözülebileceğini söylemesi durumunda, bunu asla DFS ile çözmeyi seçmediğimi hatırlıyorum. Çünkü BFS mantığı DFS'dan daha basit olduğundan, çoğu zaman bir problem için basit bir çözüm isteyeceksiniz. YvesgereY ve IVlad değindiği gibi

, başka hiçbir düğümleri kendilerine doğrudan anlam alıcılık olduğu düğümlerle başlamak gerekir. Bu düğümleri önce sonuca eklediğinizden emin olun. Her düğümü kendi mutluluğu ile eşleştirmek için bir HashMap'i ve geçişinize yardımcı olmak için BFS'de sıkça görülen bir sıra kullanabilirsiniz. Kuyruktan bir düğümü sorguladığınızda, komşularının bağımsızlığı 1 tarafından azaltılmalı, bu, düğümü grafikten silmek ve düğüm ile komşuları arasındaki kenarı silmek gibidir. Her defasında düğümleri 0 bağımsızlığıyla karşılaştığınızda, komşularını daha sonra kontrol etmek için sıraya sunun ve sonuçlara ekleyin.

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; 
}