Grafikte 2 düğüm arasındaki tüm yollar

Question

İki düğüm alıp aralarındaki tüm yolları döndüren, hatalı bir arama (Genişlemiş İlk Arama) programı yapmam gerekiyor.

public void BFS(Nod start, Nod end) { 
      Queue<Nod> queue = new Queue<Nod>(); 
      queue.Enqueue(start); 
      while (queue.Count != 0) 
      { 
       Nod u = queue.Dequeue(); 
       if (u == end) break; 
       else 
       { 
        u.data = "Visited"; 
        foreach (Edge edge in u.getChildren()) 
        { 
         if (edge.getEnd().data == "") 
         { 
          edge.getEnd().data = "Visited"; 
          if (edge.getEnd() != end) 
          { 
           edge.getEnd().setParent(u); 
          } 
          else 
          { 
           edge.getEnd().setParent(u); 
           cost = 0; 
           PrintPath(edge.getEnd(), true); 
           edge.getEnd().data = ""; 
           //return; 
          } 
         } 
         queue.Enqueue(edge.getEnd()); 
        } 
       } 
      } 
     } 

Sorunum ben yerine sadece tüm iki yol almak ve ben hepsini almak için benim kodda düzenlemek için bilmiyorum olmasıdır. Sorunumun girdisi şu haritaya dayanmaktadır:

Answer 1

BFS algoritmasında bir çözüm bulduktan sonra durmamalısınız. Bir fikir, birincisi hariç ziyaret ettiğiniz tüm şehirler için verileri null olarak ayarlamak ve fonksiyonun biraz daha uzun süre çalışmasına izin vermektir. Size bir pasaj yazmak için zamanım yok ama eğer alamayacaksa en azından bir sahte kod yazacağım. Eğer fikrimi anlamadıysanız, sorunuzla bir yorum gönderin ve daha iyi açıklamaya çalışacağım.

Answer 2

Ödevler gibi geliyor. Ama eğlenceli bir tür.

sonra yalancı kod olan yerine, ilk (böylece bir sıra tipi algoritması dönüştürülmesi gerekir nefes birinci derinliği ve hatalar içerebilir ancak genel Jist açık olmalıdır

class Node{ 
    Vector[Link] connections; 
    String name; 
} 

class Link{ 
    Node destination; 
    int distance; 
} 

Vector[Vector[Node]] paths(Node source, Node end_dest, Vector[Vector[Node]] routes){ 
    for each route in routes{ 
    bool has_next = false; 
    for each connection in source.connections{ 
     if !connection.destination in route { 
     has_next = true; 
     route.push(destination); 
     if (!connection.destination == end_dest){ 
      paths(destination, end_dest, routes); 
     } 
     } 
    } 
    if !has_next { 
     routes.remove(route) //watch out here, might mess up the iteration 
    } 
    } 
    return routes; 
} 

Düzenleme:. Mi Bu aslında aradığınız sorunun cevabı mı? Veya aslında en kısa yolu bulmak istiyor musunuz? Eğer ikincisi ise, Dijkstra'nın algoritmasını kullanın: http://en.wikipedia.org/wiki/Dijkstra%27s_algorithm

Answer 3

Genişlik ilk arama, tüm olası yolları oluşturmak için garip bir yoldur. Aşağıdaki sebepten dolayı: her bir yolun BFS, hiç bir şekilde geçilmediğinden düğümü kestirmişti.

Biz bulunduğunu Biz gerçeği kaybettik sonra 5. 4. ardından, o zaman, biz 1 sıraya 1'den 5'e kadar 2 ve 3 tüm yolları istiyorum basit bir örnek

1----2 
\ \ 
    3--- 4----5 

atın iki 4 ile 5 arasındaki yollar.

Bunu DFS ile yapmaya çalışmanızı öneririm, ancak bu durum BFS için biraz düşünebilir. Kuyruğa alınan her şey, tek bir düğüm değil, bir yol olacaktır, bu nedenle bu yolun her bir düğümü ziyaret edip etmediğini görebilirsiniz. Bu israfsız hafıza bilge,

Answer 4

Bir köşe noktası, köşe noktasının birden fazla kez tekrarlanmaması gereken bir köşe dizisidir. Bu tanım göz önüne alındığında, aşağıdaki gibi çalışacak bir özyinelemeli algoritma yazabilirsiniz: Işlevine dört parametre geçirin,, u geçerli kaynak (ki biz yinelenen olarak değişecek), hedef, intermediate_list bir hedeftir başlangıçta boş olacak olan köşe noktaları listesi ve her bir köşe noktasını kullandığımızda, yolumuza bir kereden fazla köşe kullanmamak için onu listeye ekleyeceğiz ve no_of_vertices, yapmak istediğimiz yolun uzunluğudur. 2 tarafından sınırlandırılacak alt sınır ve V tarafından sınırlanan üst nokta, köşe sayısıdır. Esas olarak, işlev kaynağı u olan, hedef v olan ve her yolun uzunluğu no_of_vertices olan bir yol listesi döndürmelidir. İlk boş bir liste oluşturun ve F(u, v, {}, 2), F(u, v, {}, 3), ..., F(u, v, {}, V) numaralı telefona çağrı yapın, her defasında F çıktısını tüm yolları saklamak istediğimiz listeyle birleştirin. Bunu uygulamaya çalışın ve hala sorunla karşılaşırsanız, sözde-kodu sizin için yazacağım.

Düzenleme: Yukarıdaki sorunun BFS'yi kullanarak çözülmesi: İlk tarama genişliği, bir grafiğin tüm durumlarını incelemek için kullanılabilecek bir algoritmadır. Verilen grafiğin tüm yollarının grafiğini BFS kullanarak keşfedebilir ve istediğiniz yolları seçebilirsiniz. Her bir v vertex için, aşağıdaki durumları sıraya ekleyin: (v, {v}, {v}), burada her durum şöyle tanımlanır: (current_vertex, list_of_vertices_already_visited, current_path).Şimdi, sıra boş değilken, öğesinin e her kenarında, x kuyruk köşesi zaten yoksa, sıra (x, list_of_vertices_already_visited + {x}, current_path -> x) sırasına yeni duruma getirin ve Kuyruktan çıkarken her yolu işlemek. Bu şekilde, ister yönlendirilmiş isterse de doğrulanmamış bir grafik için tüm yol çizgilerini arayabilirsiniz.