python3.x - About Python graph traversal operations
三叔
三叔 2017-06-15 09:22:00
0
1
883

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]
三叔
三叔

reply all(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:

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 = {}    # 添加此行
        ...
    
Latest Downloads
More>
Web Effects
Website Source Code
Website Materials
Front End Template