python3.x - À propos des opérations de parcours de graphes Python

Question

Je viens de créer un graphique et je voulais effectuer un parcours en profondeur et en largeur, mais une seule donnée apparaîtra lors du deuxième parcours. Je pense que c'est parce que j'ai défini self.visited[node] = True dans le parcours précédent, mais je l'ai fait. je ne sais pas pourquoi. Faites des modifications, merci de me donner vos conseils

Voici le 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)

Alors le résultat du parcours est

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

Propriétaire, il s'agit d'un problème avec self.visited. Lors de l'appel de self.visted pour la première recherche en profondeur, tous les nœuds ont été remplacés par true. La deuxième recherche en profondeur utilise les résultats de la première recherche en profondeur.

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 = {}    # 添加此行
        ...