python3.x – Informationen zu Python-Graph-Traversal-Operationen

Question

Ich habe gerade ein Diagramm erstellt und wollte einen Tiefendurchlauf und einen Breitendurchlauf durchführen, aber beim zweiten Durchlauf werden nur ein Daten angezeigt. Ich habe das Gefühl, dass das daran liegt, dass ich beim vorherigen Durchlauf self.visited[node] = True gesetzt habe, aber ich Ich weiß nicht warum. Nehmen Sie Änderungen vor, bitte geben Sie mir Ihren Rat

Hier ist der Code:

class Graph(object):
    def __init__(self, *args, **kwargs):
        self.node_neighbors = {}
        self.visited = {}

    def add_nodes(self,nodelist):
        for node in nodelist:
            self.add_node(node)

    def add_node(self,node):
        if node not in self.nodes():
            self.node_neighbors[node] = []

    def add_edge(self,edge):
        u, v = edge
        if(v not in self.node_neighbors[u]) and (u not in self.node_neighbors[v]):
            self.node_neighbors[u].append(u)
            if(u!=v):
                self.node_neighbors[v].append(u)

    def nodes(self):
        return self.node_neighbors.keys()

    def depth_first_search(self, root=None):
        order = []
        def dfs(node):
            self.visited[node] = True
            order.append(node)
            for  n in self.node_neighbors[node]:
                if not n in self.visited:
                    dfs(n)
        if root:
            dfs(root)
        for node in self.nodes():
            if not node in self.visited:
                dfs(node)
        print(order)
        return order

    def breadtg_frist_search(self, root = None):
        queue = []
        order = []
        def bfs():
            while len(queue) >  0:
                node = queue.pop()
                self.visited[node] = True
                for n in self.node_neighbors[node]:
                    if (not n in self.visited) and (not n in queue):
                        queue.append(n)
                        order.append(n)
        if root:
            queue.append(root)
            order.append(root)
            bfs()
        for node in self.nodes():
            if not node in self.visited:
                queue.append(node)
                order.append(node)
                bfs()
        print(order)
        return order


if __name__ == '__main__':
    g = Graph()
g.add_nodes([i+1 for i in range(10)])
g.add_edge((1, 2))
g.add_edge((1, 3))
g.add_edge((2, 4))
g.add_edge((2, 5))
g.add_edge((4, 8))
g.add_edge((5, 8))
g.add_edge((5, 9))
g.add_edge((3, 6))
g.add_edge((3, 7))
g.add_edge((7, 10))
g.add_edge((9, 10))
print('nodes:',  g.nodes())
order = g.depth_first_search(1)
order = g.breadtg_frist_search(1)

Dann ist das Ergebnis der Traversierung

nodes: dict_keys([1, 2, 3, 4, 5, 6, 7, 8, 9, 10])
[1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
[1]

Answer 1

楼主，是self.visited的问题,第一次深度搜索调用self.visted时,已经把所有节点变为true,第二次广度搜索使用第一次深度搜索结果,　改为如下即可:

class Graph(object):
    def __init__(self, *args, **kwargs):
        self.node_neighbors = {}
#        self.visited = {}    #　删除此行
    ...

    def depth_first_search(self, root=None):
        self.visited = {}    # 添加此行
        ...

    def breadtg_frist_search(self, root = None):
        self.visited = {}    # 添加此行
        ...