問題描述

就是創建了一個圖 想要進行深度遍歷 和 廣度遍歷 但是第二個遍歷的時候只會出現一個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 = {} # 添加此行...