Python数据结构与算法之图的广度优先与深度优先搜索算法示例
作者:hanahimi 发布时间:2022-05-05 07:34:53
标签: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程序设计有所帮助。
来源:http://www.cnblogs.com/hanahimi/p/4692601.html
0
投稿
猜你喜欢
- php数组中元素的存在方式是以键值对的方式('key'=>'value'),有时候我们需要根据键删除数
- 假设要生成一千万个随机数,常规的做法如下:var numbers = [];for (var&nbs
- 今天我升级MYSQL到5.1的时候遇到的。写出来共享以下。1、[root@localhost mysql]# scripts/mysql_i
- 用途:将UTF-8编码汉字转换为GB2312码,兼容英文和数字版权:虽说是原创,其实也参考了別人的部分算法asp源代码:<% 
- 在IE浏览器调试代码,我们可以选择使用 IE WebDeveloper但是我个人用惯了ff浏览器下的firebug,所以在网上搜了一下,如果
- 本文实例讲述了JS Object.preventExtensions(),Object.seal()与Object.freeze()用法。分
- 一、get//get请求function getUrl($url, $header = []){ $ch = cu
- 效果展示数据集展示数据集来源:使用了开源数据集FaceMask_CelebAgithub地址:https://github.com/seve
- 本文实例为大家分享了python实现五子棋游戏的具体代码,供大家参考,具体内容如下checkerboard.pyfrom collectio
- 有时候难免需要直接调用Shell命令来完成一些比较简单的操作,比如mount一个文件系统之类的。那么我们使用Python如何调用Linux的
- GoLang之使goroutine停止的5种方法1.goroutine停止介绍goroutine是Go语言实现并发编程的利器,简单的一个指令
- 如何远程注册DLL?试试下面的代码:<% Response.Buffer = True %&g
- 之前一直在windows环境使用pycharm加上virtualenv方式开发,最近由于本地多个virtualenv比较混乱,所以尝试切换a
- 英文原文:http://www.myinkblog.com/2009/03/21/4-principles-of-good-design-f
- 栅格就是你对页面版式的规划你日常所见的许多页面都有栅格存在。你可能注意不到,但它确实存在,并且支撑着设计内容,建立整体的架构,引导着页面的元
- 在数据科学和机器学习中,我们通常会处理大量的数据,这些数据可能会超过计算机的内存限制,因此我们需要一种方法来读取大型数据文件。在 Pytho
- css可以处理16,777,216颜色,可以使用名字、rgb值或十六进制代码。red红色等同于 rgb(255,0,0) &nbs
- 笔者在网站开发中,采用PHP4.0+MySQL3.23.38建立了多种应用。下面,以一个简单的聊天室设计为例,介绍PHP+MySQL在网页开
- 之前在网上看到有人提问,如何在页面上同步显示服务器的时间,其实实现方法有几种,可能 一般人立马就想到可以使用Ajax每隔一秒去请求服务器,然
- 在进行WEB标准网页设计时,必不可少的是写入大量的CSS语法,一般情况下我们可以通过Dreamweaver软件的“CSS样式”面板自动生成相