python3.x - 关于Python图遍历的操作

问题描述

就是创建了一个图 想要进行深度遍历 和 广度遍历 但是第二个遍历的时候只会出现一个data 感觉是因为自己之前的那个遍历把 self.visited[node] = True 的缘故 但是又不知道怎么进行修改，求各位指教

以下是代码：

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 = edgeif(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] = Truefor 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 orderif __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)

然后遍历出来的结果是

nodes: dict_keys([1, 2, 3, 4, 5, 6, 7, 8, 9, 10])[1, 2, 3, 4, 5, 6, 7, 8, 9, 10][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 = {} # 添加此行...