python图的深度优先和广度优先算法实例分析
本文实例讲述了python图的深度优先和广度优先算法。分享给大家供大家参考，具体如下：
首先有一个概念：回溯
回溯法(探索与回溯法)是一种选优搜索法，按选优条件向前搜索，以达到目标。但当探索到某一步时，发现原先选择并不优或达不到目标，就退回一步重新选择，这种走不通就退回再走的技术为回溯法，而满足回溯条件的某个状态的点称为“回溯点”。
深度优先算法：
（1）访问初始顶点v并标记顶点v已访问。
（2）查找顶点v的第一个邻接顶点w。
（3）若顶点v的邻接顶点w存在，则继续执行；否则回溯到v，再找v的另外一个未访问过的邻接点。
（4）若顶点w尚未被访问，则访问顶点w并标记顶点w为已访问。
（5）继续查找顶点w的下一个邻接顶点wi，如果v取值wi转到步骤（3）。直到连通图中所有顶点全部访问过为止。
广度优先算法：
（1）顶点v入队列。
（2）当队列非空时则继续执行，否则算法结束。
（3）出队列取得队头顶点v；访问顶点v并标记顶点v已被访问。
（4）查找顶点v的第一个邻接顶点col。
（5）若v的邻接顶点col未被访问过的，则col入队列。
（6）继续查找顶点v的另一个新的邻接顶点col，转到步骤（5）。直到顶点v的所有未被访问过的邻接点处理完。转到步骤（2）。
代码：
#!/usr/bin/python
# -*- coding: utf-8 -*-
class Graph(object):
def __init__(self,*args,**kwargs):
self.node_neighbors = {}
self.visited = {}
def add_nodes(self,nodelist):
for node in nodelist:
self.add_node(node)
def add_node(self,node):
if not node in self.nodes():
self.node_neighbors[node] = []
def add_edge(self,edge):
u,v = edge
if(v not in self.node_neighbors[u]) and ( u not in self.node_neighbors[v]):
self.node_neighbors[u].append(v)
if(u!=v):
self.node_neighbors[v].append(u)
def nodes(self):
return self.node_neighbors.keys()
def depth_first_search(self,root=None):
order = []
def dfs(node):
self.visited[node] = True
order.append(node)
for n in self.node_neighbors[node]:
if not n in self.visited:
dfs(n)
if root:
dfs(root)
for node in self.nodes():
if not node in self.visited:
dfs(node)
print order
return order
def breadth_first_search(self,root=None):
queue = []
order = []
def bfs():
while len(queue)> 0:
node = queue.pop(0)
self.visited[node] = True
for n in self.node_neighbors[node]:
if (not n in self.visited) and (not n in queue):
queue.append(n)
order.append(n)
if root:
queue.append(root)
order.append(root)
bfs()
for node in self.nodes():
if not node in self.visited:
queue.append(node)
order.append(node)
bfs()
print order
return order
if __name__ == '__main__':
g = Graph()
g.add_nodes([i+1 for i in range(8)])
g.add_edge((1, 2))
g.add_edge((1, 3))
g.add_edge((2, 4))
g.add_edge((2, 5))
g.add_edge((4, 8))
g.add_edge((5, 8))
g.add_edge((3, 6))
g.add_edge((3, 7))
g.add_edge((6, 7))
print "nodes:", g.nodes()
order = g.breadth_first_search(1)
order = g.depth_first_search(1)
结果：
nodes: [1, 2, 3, 4, 5, 6, 7, 8]
广度优先：
[1, 2, 3, 4, 5, 6, 7, 8]深度优先：
[1, 2, 4, 8, 5, 3, 6, 7]
更多关于Python相关内容感兴趣的读者可查看本站专题：《Python数据结构与算法教程》、《Python加密解密算法与技巧总结》、《Python编码操作技巧总结》、《Python函数使用技巧总结》、《Python字符串操作技巧汇总》及《Python入门与进阶经典教程》
希望本文所述对大家Python程序设计有所帮助。
相关推荐
-
python数据结构之图深度优先和广度优先实例详解
本文实例讲述了python数据结构之图深度优先和广度优先用法.分享给大家供大家参考.具体如下: 首先有一个概念:回溯 回溯法(探索与回溯法)是一种选优搜索法,按选优条件向前搜索,以达到目标.但当探索到某一步时,发现原先选择并不优或达不到目标,就退回一步重新选择,这种走不通就退回再走的技术为回溯法,而满足回溯条件的某个状态的点称为"回溯点". 深度优先算法: (1)访问初始顶点v并标记顶点v已访问. (2)查找顶点v的第一个邻接顶点w. (3)若顶点v的邻接顶点w存在,则继续执行:否则回
-
Python深度优先算法生成迷宫
本文实例为大家分享了Python深度优先算法生成迷宫,供大家参考,具体内容如下 import random #warning: x and y confusing sx = 10 sy = 10 dfs = [[0 for col in range(sx)] for row in range(sy)] maze = [[' ' for col in range(2*sx+1)] for row in range(2*sy+1)] #1:up 2:down 3:left 4:right opera
-
python实现树的深度优先遍历与广度优先遍历详解
本文实例讲述了python实现树的深度优先遍历与广度优先遍历.分享给大家供大家参考,具体如下: 广度优先(层次遍历) 从树的root开始,从上到下从左到右遍历整个树的节点 数和二叉树的区别就是,二叉树只有左右两个节点 广度优先 顺序:A - B - C - D - E - F - G - H - I 代码实现 def breadth_travel(self, root): """利用队列实现树的层次遍历""" if root == None: r
-
Python数据结构与算法之图的广度优先与深度优先搜索算法示例
本文实例讲述了Python数据结构与算法之图的广度优先与深度优先搜索算法.分享给大家供大家参考,具体如下: 根据维基百科的伪代码实现: 广度优先BFS: 使用队列,集合 标记初始结点已被发现,放入队列 每次循环从队列弹出一个结点 将该节点的所有相连结点放入队列,并标记已被发现 通过队列,将迷宫路口所有的门打开,从一个门进去继续打开里面的门,然后返回前一个门处 """ procedure BFS(G,v) is let Q be a queue Q.enqueue(v) lab
-
python实现广度优先搜索过程解析
广度优先搜索 适用范围: 无权重的图,与深度优先搜索相比,深度优先搜索法占内存少但速度较慢,广度优先搜索算法占内存多但速度较快 复杂度: 时间复杂度为O(V+E),V为顶点数,E为边数 思路 广度优先搜索是以层为顺序,将某一层上的所有节点都搜索到了之后才向下一层搜索: 代码 from collections import deque #解决从你的人际关系网中找到芒果销售商的问题 #使用字典表示映射关系 graph = {} graph["you"] = ["alice&quo
-
python深度优先搜索和广度优先搜索
1. 深度优先搜索介绍 图的深度优先搜索(Depth First Search),和树的先序遍历比较类似. 它的思想:假设初始状态是图中所有顶点均未被访问,则从某个顶点v出发,首先访问该顶点,然后依次从它的各个未被访问的邻接点出发深度优先搜索遍历图,直至图中所有和v有路径相通的顶点都被访问到. 若此时尚有其他顶点未被访问到,则另选一个未被访问的顶点作起始点,重复上述过程,直至图中所有顶点都被访问到为止. 显然,深度优先搜索是一个递归的过程. 2. 广度优先搜索介绍 广度优先搜索算法(Breadt
-
python广度优先搜索得到两点间最短路径
前言 之前一直写不出来,这周周日花了一下午终于弄懂了, 顺便放博客里,方便以后忘记了再看看. 要实现的是输入一张 图,起点,终点,输出起点和终点之间的最短路径. 广度优先搜索 适用范围: 无权重的图,与深度优先搜索相比,深度优先搜索法占内存少但速度较慢,广度优先搜索算法占内存多但速度较快 复杂度: 时间复杂度为O(V+E),V为顶点数,E为边数 思路 广度优先搜索是以层为顺序,将某一层上的所有节点都搜索到了之后才向下一层搜索: 比如下图: 从0结点开始搜索的话,一开始是0.将0加入队列中: 然后
-
python 递归深度优先搜索与广度优先搜索算法模拟实现
一.递归原理小案例分析 (1)# 概述 递归:即一个函数调用了自身,即实现了递归 凡是循环能做到的事,递归一般都能做到! (2)# 写递归的过程 1.写出临界条件 2.找出这一次和上一次关系 3.假设当前函数已经能用,调用自身计算上一次的结果,再求出本次的结果 (3)案例分析:求1+2+3+...+n的数和 # 概述 ''' 递归:即一个函数调用了自身,即实现了递归 凡是循环能做到的事,递归一般都能做到! ''' # 写递归的过程 ''' 1.写出临界条件 2.找出这一次和上一次关系 3.假设
-
10分钟教你用python动画演示深度优先算法搜寻逃出迷宫的路径
深度优先算法(DFS 算法)是什么? 寻找起始节点与目标节点之间路径的算法,常用于搜索逃出迷宫的路径.主要思想是,从入口开始,依次搜寻周围可能的节点坐标,但不会重复经过同一个节点,且不能通过障碍节点.如果走到某个节点发现无路可走,那么就会回退到上一个节点,重新选择其他路径.直到找到出口,或者退到起点再也无路可走,游戏结束.当然,深度优先算法,只要查找到一条行得通的路径,就会停止搜索:也就是说只要有路可走,深度优先算法就不会回退到上一步. 如果你依然在编程的世界里迷茫,可以加入我们的Python学
-
python图的深度优先和广度优先算法实例分析
本文实例讲述了python图的深度优先和广度优先算法.分享给大家供大家参考,具体如下: 首先有一个概念:回溯 回溯法(探索与回溯法)是一种选优搜索法,按选优条件向前搜索,以达到目标.但当探索到某一步时,发现原先选择并不优或达不到目标,就退回一步重新选择,这种走不通就退回再走的技术为回溯法,而满足回溯条件的某个状态的点称为"回溯点". 深度优先算法: (1)访问初始顶点v并标记顶点v已访问. (2)查找顶点v的第一个邻接顶点w. (3)若顶点v的邻接顶点w存在,则继续执行:否则回溯到v,
-
Python迷宫生成和迷宫破解算法实例
迷宫生成 1.随机PRIM 思路:先让迷宫中全都是墙,不断从列表(最初只含有一个启始单元格)中选取一个单元格标记为通路,将其周围(上下左右)未访问过的单元格放入列表并标记为已访问,再随机选取该单元格与周围通路单元格(若有的话)之间的一面墙打通.重复以上步骤直到列表为空,迷宫生成完毕.这种方式生成的迷宫难度高,岔口多. 效果: 代码: import random import numpy as np from matplotlib import pyplot as plt def build_tw
-
PHP折半（二分）查找算法实例分析
本文实例讲述了PHP折半(二分)查找算法.分享给大家供大家参考,具体如下: 折半查询只适用于已经按照正序或者逆序排序的数组,字符串等: 算法: 先取数组的中间位置,无中间位置,则向下取整: 从中间进行折半,大小判断,进入前半段或者后半段: 再对前半段或者后半段进行同样的折半查询, 直到查询到匹配的字符,才停止(本例用break,如果置于函数中,return即可) php实现的代码如下: <?php $arr = array(1,2,3,4,5,6,7,8,9,10);//数组 $key = 4;
-
python中scrapy处理项目数据的实例分析
在我们处理完数据后,习惯把它放在原有的位置,但是这样也会出现一定的隐患.如果因为新数据的加入或者其他种种原因,当我们再次想要启用这个文件的时候,小伙伴们就会开始着急却怎么也翻不出来,似乎也没有其他更好的搜集办法,而重新进行数据整理显然是不现实的.下面我们就一起看看python爬虫中scrapy处理项目数据的方法吧. 1.拉取项目 $ git clone https://github.com/jonbakerfish/TweetScraper.git $ cd TweetScraper/ $ pi
-
python爬虫用scrapy获取影片的实例分析
我们平时生活的娱乐中,看电影是大部分小伙伴都喜欢的事情.周围的人总会有意无意的在谈论,有什么影片上映,好不好看之类的话题,没事的时候谈论电影是非常不错的话题.那么,一些好看的影片如果不去电影院的话,在其他地方看都会有大大小小的限制,今天小编就教大家用python中的scrapy获取影片的办法吧. 1. 创建项目 运行命令: scrapy startproject myfrist(your_project_name) 文件说明: 名称 | 作用 --|-- scrapy.cfg | 项目的配置信息
-
python爬取抖音视频的实例分析
现在抖音的火爆程度,大家都是有目共睹的吧,之前小编在网络上发现好玩的事情,就是去爬取一些网站,因此,也考虑能否进行抖音上的破案去,在实际操作以后,真的实现出来了,利用自动化工具,就可以轻松实现了,后有小伙伴提出把appium去掉瘦身之后也是可以实现的,那么看下详细操作内容吧. 1.mitmproxy/mitmdump抓包 import requests path = 'D:/video/' num = 1788 def response(flow): global num target_urls
-
python中使用asyncio实现异步IO实例分析
1.说明 Python实现异步IO非常简单,asyncio是Python 3.4版本引入的标准库,直接内置了对异步IO的支持. asyncio的编程模型就是一个消息循环.我们从asyncio模块中直接获取一个EventLoop的引用,然后把需要执行的协程扔到EventLoop中执行,就实现了异步IO. 2.实例 import asyncio @asyncio.coroutine def wget(host): print('wget %s...' % host) connect = asynci
-
python一绘制元二次方程曲线的实例分析
说明 1.Matplotlib函数可以绘制图形,使用plot函数绘制曲线. 2.需要将200个点的x坐标和Y坐标分别以序列的形式输入plot函数,然后调用show函数来显示图形. 实例 import matplotlib.pyplot as plt #200个点的x坐标 x=range(-100,100) #生成y点的坐标 y=[i**2 for i in x ] #绘制一元二次曲线 plt.plot(x,y) #调用savefig将一元二次曲线保存为result.jpg plt.savefig
-
Java的Arrays.sort()方法排序算法实例分析
暂时网上看过很多JDK8中Arrays.sort的底层原理,有些说是插入排序,有些说是归并排序,也有说大于域值用计数排序法,否则就使用插入排序...其实不全对.让我们分析个究竟: // Use Quicksort on small arrays if (right - left < QUICKSORT_THRESHOLD) { //QUICKSORT_THRESHOLD = 286 sort(a, left, right, true); return; } 数组一进来,会碰到第一个阀值QUICK
-
Python pkg_resources模块动态加载插件实例分析
使用标准库importlib的import_module()函数.django的import_string(),它们都可以动态加载指定的 Python 模块. 举两个动态加载例子: 举例一: 在你项目中有个test函数,位于your_project/demo/test.py中,那么你可以使用import_module来动态加载并调用这个函数而不需要在使用的地方通过import导入. module_path = 'your_project/demo' module = import_module(