Python数据结构与算法之图的广度优先与深度优先搜索算法示例
作者:hanahimi 时间:2022-05-05 07:34:53
本文实例讲述了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程序设计有所帮助。
来源:http://www.cnblogs.com/hanahimi/p/4692601.html
标签:Python,数据结构,算法,广度优先,深度优先
0
投稿
猜你喜欢
404错误伪静态类封装class RewriteBase
2009-06-29 16:19:00
Python calendar模块详情
2023-08-20 23:04:59
交互设计实用指南系列(11)—减少记忆负担
2010-03-29 13:12:00
ASP在线转flv+缩略图
2007-08-27 16:18:00
Python tkinter实现计算器功能
2023-06-29 15:41:29
js版sliderBar(滑动条)控件
2008-10-18 15:59:00
JavaScript Date()在页面内显示日期
2008-02-05 10:18:00
asp开发中textarea常见问题
2008-04-13 06:34:00
asp 删除数据并同时删除图片的代码
2011-02-28 10:39:00
Python网络编程之TCP与UDP协议套接字用法示例
2023-12-07 06:34:45
商业价值与用户价值的平衡
2008-12-10 18:42:00
各种鼠标经过图片边框加粗效果整理
2007-09-29 21:43:00
网马解密大讲堂——网马解密中级篇(Eval篇)
2009-09-16 16:04:00
sublime text配置node.js调试(图文教程)
2023-07-04 14:07:57
大家都来设计创意XP黑屏!
2008-10-25 14:59:00
MySQL数据库磁盘优化
2008-11-24 17:29:00
深入解析Go语言编程中的递归使用
2023-10-09 09:24:36
Go中的应用配置管理详解
2023-06-21 00:40:55
详解如何利用Python制作24点小游戏
2022-02-04 17:22:42
JS中实现JAVA的hashCode算法
2008-08-03 17:00:00