用NetworkX对比深度优先和广度优先搜索
文章目录
- 简介
- 可视化实例
简介
广度优先搜索(breadth-first search, BFS)和深度优先搜索(depth-first search, DFS)是算法导论中最先介绍的两个图论算法，也是最简单的两种图搜索算法。所谓图搜索算法，其目的是有序地沿着图的边，访问其所有顶点。
NetworkX围绕BFS和DFS构建了许多函数，如下标所示
| BFS | DFS | 返回值 |
|---|---|---|
| bfs_edges | dfs_edges | 边列表 |
| bfs_tree | dfs_tree | 有向树 |
| bfs_predecessors | dfs_predecessors | 字典：{节点:前驱节点} |
| bfs_successors | dfs_successors | 字典：{节点:后继节点} |
| bfs_preorder_nodes | dfs_preorder_nodes | 前序遍历节点的生成器 |
| bfs_postorder_nodes | dfs_postorder_nodes | 后序遍历节点的生成器 |
| bfs_labeled_edges | dfs_labeled_edges | 边的生成器 |
可视化实例
NetworkX提供的这些函数，其生成的BFS或DFS是一致的，区别主要是返回值的形式。下面对bfs_tree和dfs_tree进行测试，对比这两种搜索方法的差异，效果如下
其中，红色数字为搜索顺序。在BFS中，从【0】节点开始，先搜索与【0】相连的【1】和【2】，然后搜索与【1】【2】相连的【3】【4】【5】【6】；在DFS中，同样从【1】节点开始，但顺着【1】【3】【7】先搜索完，然后再回头搜索。
测试代码如下
importnetworkxasnximportmatplotlib.pyplotasplt plt.rcParams['font.sans-serif']='Times New Roman'G=nx.Graph()edges=[(0,1),(0,2),(1,3),(1,4),(2,5),(2,6),(3,7)]G.add_edges_from(edges)# 固定节点坐标，让两张图的布局完全一致pos={0:(0,3),1:(-2,2),2:(2,2),3:(-3,1),4:(-1,1),5:(1,1),6:(3,1),7:(-3,0)}trees={"BFS":nx.bfs_tree(G,0),"DFS":nx.dfs_tree(G,0)}fig,axes=plt.subplots(1,2,figsize=(10,4))forax,(title,T)inzip(axes,trees.items()):order=list(T.nodes())seq={n:str(i+1)fori,ninenumerate(order)}nx.draw(T,pos,ax=ax,with_labels=True,node_size=800,arrows=True)forn,(x,y)inpos.items():ax.text(x+0.5,y+0.22,seq[n],color="red",fontweight="bold")ax.set_title(title)ax.axis("off")ax.margins(0.25)plt.tight_layout()plt.show()