文章目录简介可视化实例简介广度优先搜索(breadth-first search, BFS)和深度优先搜索(depth-first search, DFS)是算法导论中最先介绍的两个图论算法也是最简单的两种图搜索算法。所谓图搜索算法其目的是有序地沿着图的边访问其所有顶点。NetworkX围绕BFS和DFS构建了许多函数如下标所示BFSDFS返回值bfs_edgesdfs_edges边列表bfs_treedfs_tree有向树bfs_predecessorsdfs_predecessors字典{节点:前驱节点}bfs_successorsdfs_successors字典{节点:后继节点}bfs_preorder_nodesdfs_preorder_nodes前序遍历节点的生成器bfs_postorder_nodesdfs_postorder_nodes后序遍历节点的生成器bfs_labeled_edgesdfs_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 RomanGnx.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,axesplt.subplots(1,2,figsize(10,4))forax,(title,T)inzip(axes,trees.items()):orderlist(T.nodes())seq{n:str(i1)fori,ninenumerate(order)}nx.draw(T,pos,axax,with_labelsTrue,node_size800,arrowsTrue)forn,(x,y)inpos.items():ax.text(x0.5,y0.22,seq[n],colorred,fontweightbold)ax.set_title(title)ax.axis(off)ax.margins(0.25)plt.tight_layout()plt.show() 用NetworkX对比深度优先和广度优先搜索
文章目录简介可视化实例简介广度优先搜索(breadth-first search, BFS)和深度优先搜索(depth-first search, DFS)是算法导论中最先介绍的两个图论算法也是最简单的两种图搜索算法。所谓图搜索算法其目的是有序地沿着图的边访问其所有顶点。NetworkX围绕BFS和DFS构建了许多函数如下标所示BFSDFS返回值bfs_edgesdfs_edges边列表bfs_treedfs_tree有向树bfs_predecessorsdfs_predecessors字典{节点:前驱节点}bfs_successorsdfs_successors字典{节点:后继节点}bfs_preorder_nodesdfs_preorder_nodes前序遍历节点的生成器bfs_postorder_nodesdfs_postorder_nodes后序遍历节点的生成器bfs_labeled_edgesdfs_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 RomanGnx.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,axesplt.subplots(1,2,figsize(10,4))forax,(title,T)inzip(axes,trees.items()):orderlist(T.nodes())seq{n:str(i1)fori,ninenumerate(order)}nx.draw(T,pos,axax,with_labelsTrue,node_size800,arrowsTrue)forn,(x,y)inpos.items():ax.text(x0.5,y0.22,seq[n],colorred,fontweightbold)ax.set_title(title)ax.axis(off)ax.margins(0.25)plt.tight_layout()plt.show()