I created a graph and wanted to perform depth traversal and breadth traversal, but only one data will appear during the second traversal. I feel that it is because I set self.visited[node] = True in the previous traversal, but it does not I know how to modify it, please give me some advice
The following is the 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)
Then the result of traversal is
nodes: dict_keys([1, 2, 3, 4, 5, 6, 7, 8, 9, 10])
[1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
[1]
Owner, it’s a problem with self.visited. When calling self.visted for the first depth search, all nodes have been changed to true. The second breadth search uses the results of the first depth search. Change it to the following: