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

时间：2018-06-28 21:52:27 阅读：317 评论：0 收藏：0 [点我收藏+]

小书匠 Graph 图论

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

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

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

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

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

#构建一个长度为10的路径 
G = nx.path_graph(10) 
 
#显示graph 
nx.draw_spring(G,with_labels=True) 
plt.axis(‘on‘) 
plt.xticks([]) 
plt.yticks([]) 
plt.show() 
 
#以4为顶点,广度遍历 
print(list(nx.bfs_tree(G,4).edges())) 

广度优先搜索算法示例

输出:

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

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

#构建一个长度为10的路径 
G = nx.path_graph(10) 
 
#显示graph 
nx.draw_spring(G,with_labels=True) 
plt.axis(‘on‘) 
plt.xticks([]) 
plt.yticks([]) 
plt.show() 
 
#以5为顶点,深度遍历,限定深度为3 
T = nx.dfs_tree(G, source=5, depth_limit=3) 
list(T.edges()) 

深度优先搜索算法示例

输出:

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

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

原文：https://www.cnblogs.com/wushaogui/p/9240857.html

踩

(0)

评论一句话评论（0）

分享档案

更多>

2021年09月23日 (328)
2021年09月24日 (313)
2021年09月17日 (191)
2021年09月15日 (369)
2021年09月16日 (411)
2021年09月13日 (439)
2021年09月11日 (398)
2021年09月12日 (393)
2021年09月10日 (160)
2021年09月08日 (222)