您的位置: 首页  >  IT文章  >  NetworkX系列教程(10)-算法之五:广度优先与深度优先

NetworkX系列教程(10)-算法之五:广度优先与深度优先

分类: IT文章 • 2022-06-03 15:31:25
小书匠Graph图论

重头戏部分来了,写到这里我感觉得仔细认真点了,可能在NetworkX中,实现某些算法就一句话的事,但是这个算法是做什么的,用在什么地方,原理是怎么样的,不清除,所以,我决定先把图论中常用算法弄个明白在写这部分.

图论常用算法看我的博客:

下面我将使用NetworkX实现上面的算法,建议不清楚的部分打开两篇博客对照理解.
我将图论的经典问题及常用算法的总结写在下面两篇博客中:
图论---问题篇
图论---算法篇

目录:

注意:如果代码出现找不库,请返回第一个教程,把库文件导入.

11.6广度优先搜索算法(BFS)

  1. #构建一个长度为10的路径 
  2. G = nx.path_graph(10) 
  3.  
  4. #显示graph 
  5. nx.draw_spring(G,with_labels=True) 
  6. plt.axis('on') 
  7. plt.xticks([]) 
  8. plt.yticks([]) 
  9. plt.show() 
  10.  
  11. #以4为顶点,广度遍历 
  12. print(list(nx.bfs_tree(G,4))) 

NetworkX系列教程(10)-算法之五:广度优先与深度优先
广度优先搜索算法示例

输出:

[4, 3, 5, 2, 6, 1, 7, 0, 8, 9]

11.7深度优先搜索算法(DFS)

  1. #构建一个长度为10的路径 
  2. G = nx.path_graph(10) 
  3.  
  4. #显示graph 
  5. nx.draw_spring(G,with_labels=True) 
  6. plt.axis('on') 
  7. plt.xticks([]) 
  8. plt.yticks([]) 
  9. plt.show() 
  10.  
  11. #以5为顶点,深度遍历,限定深度为3 
  12. T = nx.dfs_tree(G, source=5, depth_limit=3) 
  13. list(T) 

NetworkX系列教程(10)-算法之五:广度优先与深度优先
深度优先搜索算法示例

输出:

[5, 4, 3, 2, 6, 7, 8]

相关推荐