Python数据结构与算法之图的广度优先与深度优先搜索算法示例
2019/7/13 22:32:32
本文主要是介绍Python数据结构与算法之图的广度优先与深度优先搜索算法示例,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!
本文实例讲述了Python数据结构与算法之图的广度优先与深度优先搜索算法。分享给大家供大家参考,具体如下:
根据维基百科的伪代码实现:
广度优先BFS:
使用队列,集合
标记初始结点已被发现,放入队列
每次循环从队列弹出一个结点
将该节点的所有相连结点放入队列,并标记已被发现
通过队列,将迷宫路口所有的门打开,从一个门进去继续打开里面的门,然后返回前一个门处
""" procedure BFS(G,v) is let Q be a queue Q.enqueue(v) label v as discovered while Q is not empty v ← Q.dequeue() procedure(v) for all edges from v to w in G.adjacentEdges(v) do if w is not labeled as discovered Q.enqueue(w) label w as discovered """ def procedure(v): pass def BFS(G,v0): """ 广度优先搜索 """ q, s = [], set() q.extend(v0) s.add(v0) while q: # 当队列q非空 v = q.pop(0) procedure(v) for w in G[v]: # 对图G中顶点v的所有邻近点w if w not in s: # 如果顶点 w 没被发现 q.extend(w) s.add(w) # 记录w已被发现
深度优先DFS
使用 栈,集合
初始结点入栈
每轮循环从栈中弹出一个结点,并标记已被发现
对每个弹出的结点,将其连接的所有结点放到队列中
通过栈的结构,一步步深入挖掘
"""" Pseudocode[edit] Input: A graph G and a vertex v of G Output: All vertices reachable from v labeled as discovered A recursive implementation of DFS:[5] 1 procedure DFS(G,v): 2 label v as discovered 3 for all edges from v to w in G.adjacentEdges(v) do 4 if vertex w is not labeled as discovered then 5 recursively call DFS(G,w) A non-recursive implementation of DFS:[6] 1 procedure DFS-iterative(G,v): 2 let S be a stack 3 S.push(v) 4 while S is not empty 5 v = S.pop() 6 if v is not labeled as discovered: 7 label v as discovered 8 for all edges from v to w in G.adjacentEdges(v) do 9 S.push(w) """ def DFS(G,v0): S = [] S.append(v0) label = set() while S: v = S.pop() if v not in label: label.add(v) procedure(v) for w in G[v]: S.append(w)
更多关于Python相关内容感兴趣的读者可查看本站专题:《Python数据结构与算法教程》、《Python加密解密算法与技巧总结》、《Python编码操作技巧总结》、《Python函数使用技巧总结》、《Python字符串操作技巧汇总》及《Python入门与进阶经典教程》
希望本文所述对大家Python程序设计有所帮助。
这篇关于Python数据结构与算法之图的广度优先与深度优先搜索算法示例的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!
- 2024-05-08有遇到过吗?同样的规则 Excel 中 比Python 结果大
- 2024-03-30开始python成长之路
- 2024-03-29python optparse
- 2024-03-29python map 函数
- 2024-03-20invalid format specifier python
- 2024-03-18pool.map python
- 2024-03-18threads in python
- 2024-03-14python Ai 应用开发基础训练,字符串,字典,文件
- 2024-03-13id3 algorithm python
- 2024-03-13sum array elements python