Vorbestellung des Baumspaziergangs eines minimalen Spannbaums, der von Prims Algorithmus generiert wurde

Question

Ich versuche, einen ungefähren Algorithmus zur Lösung des Travelling Salesman Problems (TSP) zu implementieren, der verwendet werden kann, wenn die Dreiecksungleichung für die Kantengewichte gilt. . Wie in Cormen et al, Einführung (. 3. 3d) auf Algorithmen, die Pseudo-Code ist:

und hier ist ein Beispiel:

Was ich Ich kämpfe mit, wie man den Preorder-Tree-Walk auf dem Baum implementiert, der von Prims Algorithmus erzeugt wird. Da dies kein binärer Suchbaum ist, scheint der unter https://en.wikipedia.org/wiki/Tree_traversal#Pre-order_2 angegebene Pseudocode nicht zu gelten.

Statt left und right Attribute haben die Knoten key und parent Attribute. Hier ist, wie sie in meiner Implementierung von Prim-Algorithmus (mit einem kleinen Testfall) erzeugt:

import math 
import copy 
import pytest 
import pandas as pd 
from cached_property import cached_property 


class Node(object): 
    def __init__(self, key=math.inf, parent=None): 
     self.key = key 
     self.parent = parent 

    def __lt__(self, other): 
     return self.key < other.key 


class Graph(object): 
    def __init__(self, edges): 
     self.edges = edges 

    @cached_property 
    def nodes(self): 
     _nodes = set() 
     for edge in self.edges: 
      _nodes.add(edge[0]) 
      _nodes.add(edge[1]) 
     return {node: Node() for node in list(_nodes)} 

    @cached_property 
    def adj(self): 
     A = {node: [] for node in self.nodes} 
     for edge in self.edges: 
      u, v, _ = edge 
      A[u].append(v) 
      A[v].append(u) 
     return A 

    @cached_property 
    def w(self): 
     N = len(self.nodes) 
     none_array = [[None for _ in range(N)] for _ in range(N)] 
     df = pd.DataFrame(none_array, index=sorted(self.nodes), columns=sorted(self.nodes)) 
     for edge in self.edges: 
      u, v, weight = edge 
      df.set_value(u, v, weight) 
      df.set_value(v, u, weight) 
     return df 

    def mst_prim(self, root): 
     r = self.nodes[root] 
     r.key = 0 
     Q = copy.copy(self.nodes) 
     while Q: 
      u = min(Q, key=Q.get) 
      u_node = Q.pop(u) 
      for v in self.adj[u]: 
       if v in Q and self.w[u][v] < self.nodes[v].key: 
        self.nodes[v].parent = u 
        self.nodes[v].key = self.w[u][v] 


@pytest.fixture 
def edges_simple(): 
    return [('a', 'b', 4), 
      ('a', 'h', 8), 
      ('b', 'h', 11), 
      ('h', 'i', 7), 
      ('b', 'c', 8), 
      ('h', 'g', 1), 
      ('i', 'c', 2), 
      ('i', 'g', 6), 
      ('c', 'd', 7), 
      ('g', 'f', 2), 
      ('c', 'f', 4), 
      ('d', 'f', 14), 
      ('d', 'e', 9), 
      ('f', 'e', 10) 
      ] 

def test_mst_prim(edges_simple): 
    graph = Graph(edges_simple) 
    graph.mst_prim(root='a') 
    # print("\n") 
    # for u, node in graph.nodes.items(): 
    # print(u, node.__dict__) 
    assert graph.nodes['a'].parent is None 
    assert graph.nodes['i'].parent == 'c' 
    assert graph.nodes['d'].parent == 'c' 



if __name__ == "__main__": 
    # pytest.main([__file__+"::test_mst_prim", "-s"]) 
    pytest.main([__file__, "-s"]) 

Wie kann ich Preorder Baumdurchlauf auf dieser Grafik durchführen? (Beachten Sie, dass diese Frage ähnlich ist wie pre-order traversal of a Minimum spanning tree, aber ich fand die Antwort dort eher hochrangig).

Answer 1

Ich empfehle Ihnen, eine neue Liste in Ihrer Node Klasse mit dem Namen children zum Beispiel hinzuzufügen.

Nach Ihrem Prim's Algorithmus können Sie Ihre erhaltenen Knoten durchlaufen und sie zu deren Eltern children hinzufügen. Die Komplexität ist O(n), also keine große Sache. Danach wird die DFS Traversal einfach sein.

Aber wieder, wie in der post Sie erwähnt, müssen Sie eine Bestellung für Ihre Kinder für eine preorder Traversal auswählen. In Ihrem Fall, wenn Sie nur Bezug auf Ihre parent haben, gibt es keine Möglichkeit zu wissen, was das left-most Kind zum Beispiel ist.

Answer 2

Ich bin ein wenig verwirrt, warum der Algorithmus in Cormens Buch eine Preorder-Traversal erwähnt, da es keine Ordnung unter den "Kindern" eines Knotens im minimalen Spannbaum MST gibt.

Wie ich Sie verstehe, müssen Sie einfach eine Tiefensuche zuerst (DFS) auf dem MST wie erwähnt here und here durchführen. Das heißt, wenn Sie an einem Knoten u sind, besuchen Sie einen seiner Nachbarn oder "Kinder" in keiner bestimmten Reihenfolge.

Sie können das DFS implementieren, indem Sie die Adjazenzlisten-Darstellung eines Graphen verwenden, der in Ihrer Klasse als adj bezeichnet wird.