图遍历(DFS, BFS) python实现

一 摘要

图遍历方法包括深度遍历(DFS)和广度遍历(BFS)。图一般用邻接矩阵或者邻接表来储存，本实现代码中 采用词典来存储,相比于邻接矩阵，词典方式来存储会导致访问并没有那么快，因为需要遍历key对应的list才可以找到想要的边。 另外，无论是dfs还是bfs其实跟树遍历(因为树也是一种图，无环图)一样，用到的辅助数据结构都是queue(BFS)或者stack(DFS)

二 实现代码

import networkx as nx
import matplotlib.pyplot as plt


class GraphTraverser(object):
    """图遍历器，基于networks展示图
    """
    def __init__(self):
        return

    def gen_graph(self, node_list=[], edge_list=[()]):
        """生成图, 返回一个图词典，用来存储图
        :param node_list:
        :param edge_list:
        :return:
        """
        graph = nx.MultiDiGraph()
        graph.add_nodes_from(node_list)
        graph.add_edges_from(edge_list)
        nx.draw(graph, with_labels=True)
        plt.show()
        graph_dict = {}
        for node in node_list:
            graph_dict[node] = [next_node[1] for next_node in edge_list if next_node[0] == node]
        return graph_dict

    def bfs_traverse(self, graph, start_node):
        """广度优先遍历, 队列实现 fifo
        :param graph:
        :param start_node:
        :return:
        """
        queue = [start_node]
        visited = set()  # 看是否访问过该结点
        visited.add(start_node)
        while len(queue) > 0:
            vertex = queue.pop(0)  # 保存第一结点，并弹出，方便把他下面的子节点接入
            nodes = graph[vertex]  # 子节点的数组
            for next_node in nodes:
                if next_node not in visited:  # 判断是否访问过
                    queue.append(next_node)
                    visited.add(next_node)
            print(vertex)

    def dfs_traverse(self, graph, start_node):
        """深度优先访问 栈实现 filo, 回溯
        :param graph:
        :param start_node:
        :return:
        """
        stack = [start_node]
        visited = set()  # 看是否访问过
        visited.add(start_node)
        while len(stack) > 0:
            # 拿出邻接点
            vertex = stack.pop()  # 这里pop参数没有0了，最后一个元素
            nodes = graph[vertex]
            for next_node in nodes:
                if next_node not in visited:  # 如何判断是否访问过，使用一个数组
                    stack.append(next_node)
                    visited.add(next_node)
            print(vertex)


if __name__ == "__main__":
    graph = GraphTraverser()
    graph_dict = graph.gen_graph([1, 2, 3, 4, 5], [(1, 2), (1, 3), (1, 4), (2, 3), (3, 5)])
    print(graph_dict)
    graph.bfs_traverse(graph_dict, 1)
    print()
    graph.dfs_traverse(graph_dict, 1)

结果 有图如下 bfs与dfs结果：

1
2
3
4
5

1
4
3
5
2