C# Traversal đồ thị

Question

Thuật toán này thực hiện công việc tuyệt vời để duyệt qua các nút trong biểu đồ.

Dictionary<Node, bool> visited = new Dictionary<Node, bool>(); 

Queue<Node> worklist = new Queue<Node>(); 

visited.Add(this, false); 

worklist.Enqueue(this); 

while (worklist.Count != 0) 
{ 
    Node node = worklist.Dequeue(); 

    foreach (Node neighbor in node.Neighbors) 
    { 
     if (!visited.ContainsKey(neighbor)) 
     { 
      visited.Add(neighbor, false); 
      worklist.Enqueue(neighbor); 
     } 
    } 
} 

Tôi có thể sử dụng nút này để tìm nút đích trong biểu đồ. Các danh sách công việc (hoặc bật) các mục khi danh sách công việc được xử lý. Khi tôi tìm thấy mục tiêu làm thế nào tôi có thể trả về đường dẫn đầy đủ đến nút?

Cập nhật Tôi đang cố gắng tìm ra cách đảo ngược đường dẫn đến thư mục gốc. Phương thức này được gọi trên nút gốc, sau đó, trẻ em có thể có hai cha mẹ, do đó, nó không đơn giản như gọi thuộc tính cha mẹ trên mỗi nút và duyệt qua sao lưu.

Mục tiêu của phương pháp là tìm đường dẫn, không lặp lại tất cả các nút hoặc để kiểm tra xem nút có tồn tại hay không.

Answer 1

Theo dõi các nút tiền thân.Trong việc thực hiện đơn giản nhất, đây là một cuốn từ điển, và thường ký hiệu là π trong giả mã:

Dictionary<Node, bool> visited = new Dictionary<Node, bool>(); 
Dictionary<Node, Node> π = new Dictionary<Node, Node>(); 

Queue<Node> worklist = new Queue<Node>(); 

visited.Add(this, false); 

worklist.Enqueue(this); 

while (worklist.Count != 0) 
{ 
    Node node = worklist.Dequeue(); 

    foreach (Node neighbor in node.Neighbors) 
    { 
     if (!visited.ContainsKey(neighbor)) 
     { 
      visited.Add(neighbor, false); 
      π.Add(neighbor, node); 
      worklist.Enqueue(neighbor); 
     } 
    } 
} 

Sau đó, bạn có thể lặp qua những người tiền nhiệm để quay lại con đường từ bất kỳ nút, nói e:

while (π[e] != null) { 
    Console.WriteLine(e); 
    e = π[e]; 
} 

Answer 2

Đây có phải là "trường hợp" của biểu đồ, nếu có một thứ như vậy không?

Biểu đồ có tuần hoàn hoặc tuần hoàn không? Tôi sợ tôi không biết tất cả các thuật ngữ cho lý thuyết đồ thị.

Đây là những gì tôi thực sự băn khoăn về:

A -> B -> C ------> F 
    B -> D -> E -> F 

Dưới đây là những câu hỏi của tôi:

• Liệu điều này xảy ra?
• Có thể "điều này" trong mã của bạn bắt đầu từ B không?
• Đường dẫn đến F là gì?

Nếu biểu đồ không bao giờ nối lại với nhau khi nó chia nhỏ, không chứa chu kỳ và "this" sẽ luôn là gốc/bắt đầu của biểu đồ, từ điển đơn giản sẽ xử lý đường dẫn.

Dictionary<Node, Node> PreNodes = new Dictionary<Node, Node>(); 

cho mỗi nút bạn truy cập, thêm nút lân cận làm khóa và nút đó là hàng xóm làm giá trị. Điều này sẽ cho phép bạn, khi bạn đã tìm thấy nút đích, để quay trở lại để có được đường dẫn đảo ngược.

Nói cách khác, các từ điển cho đồ thị trên, sau khi một traversal đầy đủ sẽ là:

B: A 
C: B 
D: B 
E: D 
F: C (or E, or both?) 

Để tìm đường dẫn đến E-nút, chỉ cần quay lại:

E -> D -> B -> A 

nào cung cấp cho bạn đường dẫn:

A -> B -> D -> E 

Answer 3

Vì bạn không theo dõi đường dẫn đến nút "hiện tại" bất cứ lúc nào bạn sẽ phải xây dựng điều đó khi bạn đã tìm thấy mục tiêu. Nếu lớp Node của bạn có thuộc tính Parent bạn có thể dễ dàng backtrack lên cây để xây dựng đường dẫn đầy đủ.

Answer 4

Peter gần như chính xác. Tôi không nghĩ rằng bạn có thể lưu trữ một liên kết đến đỉnh mẹ trong lớp nút, bởi vì nó thay đổi tùy thuộc vào đỉnh mà tại đó bạn bắt đầu tìm kiếm đầu tiên của bạn. Bạn cần tạo một Parent Dictionary với các khóa là các nút và các giá trị là các nút cha. Khi bạn truy cập mỗi đỉnh (nhưng trước khi xử lý), bạn thêm cha mẹ vào từ điển. Sau đó, bạn có thể đi lên đường dẫn cha trở lại đỉnh gốc.

Answer 5

tôi đã cố gắng sử dụng đoạn mã này để có được những con đường thay thế từ đến đỉnh (đỉnh trong mã của tôi), sử dụng nguồn và số phận, nhưng chỉ đơn giản là không làm việc ...

public String EncontrarMenorCaminho(Vertice o, Vertice d) 
     { 
      Dictionary<Vertice, bool> visited = new Dictionary<Vertice, bool>(); 
      Dictionary<Vertice, Vertice> previous = new Dictionary<Vertice, Vertice>(); 
      Queue<Vertice> worklist = new Queue<Vertice>(); 
      String operacao = "Registro de operações realizadas:\r\n\r\n"; 

      visited.Add(o, false); 
      worklist.Enqueue(o); 
      while (worklist.Count != 0) 
      { 
       Vertice v = worklist.Dequeue(); 
       foreach (Vertice neighbor in EncontrarVizinhos(v)) 
       { 
        if (!visited.ContainsKey(neighbor)) 
        { 
         visited.Add(neighbor, false); 
         previous.Add(neighbor, v); 
         worklist.Enqueue(neighbor); 
        } 
       } 
      } 

      if (previous.Count > 0) 
      { 
       for (int p = 0; p < previous.Count; p++) 
       { 
        Vertice v1 = previous.ElementAt(p).Key; 
        Vertice v2 = previous.ElementAt(p).Value; 
        EncontrarAresta(v1, v2).Selecionado = true; 
        EncontrarAresta(v2, v1).Selecionado = true; 
        operacao += v1.Info.ToString() + "x" + v2.Info.ToString() + "\r\n"; 
       } 
      } 

      List<Vertice> grupos = new List<Vertice>(); 

      foreach (Aresta a in ArestasSelecionadas()) 
      { 
       if (!grupos.Contains(a.Origem)) grupos.Add(a.Origem); 
      } 

      foreach (Vertice v in grupos) 
      { 
       int menorpeso = this.infinito; 
       foreach(Vertice vz in EncontrarVizinhos(v)) 
       { 
        Aresta tmp = EncontrarAresta(v,vz); 
        if (tmp.Selecionado == true && tmp.Peso < menorpeso) 
        { 
         menorpeso = tmp.Peso; 
        } 
        else 
        { 
         tmp.Selecionado = false; 
        } 
       } 

      } 




      DesenharMapa(); 

      return operacao; 

Về cơ bản hoạt động là được tất cả đánh dấu cạnh (Selecionado = true) và xác minh một lần nữa nếu cần thiết tiếp tục được lựa chọn ...

Trong ví dụ này, tôi muốn có được con đường ngắn nhất từ ​​vertext 'N' để đỉnh 'Q':

Xem hình ảnh xem trước tại đây: