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程序设计有所帮助。

赞 (0)

相关推荐

  • Python数据结构与算法之完全树与最小堆实例

    本文实例讲述了Python数据结构与算法之完全树与最小堆.分享给大家供大家参考,具体如下: # 完全树 最小堆 class CompleteTree(list): def siftdown(self,i): """ 对一颗完全树进行向下调整,传入需要向下调整的节点编号i 当删除了最小的元素后,当新增加一个数被放置到堆顶时, 如果此时不符合最小堆的特性,则需要将这个数向下调整,直到找到合适的位置为止""" n = len(self) # 当 i 节

  • Python语言描述KNN算法与Kd树

    Python语言描述KNN算法与Kd树

    最近邻法和k-近邻法 下面图片中只有三种豆,有三个豆是未知的种类,如何判定他们的种类? 提供一种思路,即:未知的豆离哪种豆最近就认为未知豆和该豆是同一种类.由此,我们引出最近邻算法的定义:为了判定未知样本的类别,以全部训练样本作为代表点,计算未知样本与所有训练样本的距离,并以最近邻者的类别作为决策未知样本类别的唯一依据.但是,最近邻算法明显是存在缺陷的,比如下面的例子:有一个未知形状(图中绿色的圆点),如何判断它是什么形状? 显然,最近邻算法的缺陷--对噪声数据过于敏感,为了解决这个问题,我们可

  • Python语言描述机器学习之Logistic回归算法

    Python语言描述机器学习之Logistic回归算法

    本文介绍机器学习中的Logistic回归算法,我们使用这个算法来给数据进行分类.Logistic回归算法同样是需要通过样本空间学习的监督学习算法,并且适用于数值型和标称型数据,例如,我们需要根据输入数据的特征值(数值型)的大小来判断数据是某种分类或者不是某种分类. 一.样本数据 在我们的例子中,我们有这样一些样本数据: 样本数据有3个特征值:X0X0,X1X1,X2X2 我们通过这3个特征值中的X1X1和X2X2来判断数据是否符合要求,即符合要求的为1,不符合要求的为0. 样本数据分类存放在一个

  • python实现协同过滤推荐算法完整代码示例

    python实现协同过滤推荐算法完整代码示例

    测试数据 http://grouplens.org/datasets/movielens/ 协同过滤推荐算法主要分为: 1.基于用户.根据相邻用户,预测当前用户没有偏好的未涉及物品,计算得到一个排序的物品列表进行推荐 2.基于物品.如喜欢物品A的用户都喜欢物品C,那么可以知道物品A与物品C的相似度很高,而用户C喜欢物品A,那么可以推断出用户C也可能喜欢物品C. 不同的数据.不同的程序猿写出的协同过滤推荐算法不同,但其核心是一致的: 1.收集用户的偏好 1)不同行为分组 2)不同分组进行加权计算用

  • 浅谈Python实现贪心算法与活动安排问题

    浅谈Python实现贪心算法与活动安排问题

    贪心算法 原理:在对问题求解时,总是做出在当前看来是最好的选择.也就是说,不从整体最优上加以考虑,他所做出的仅是在某种意义上的局部最优解.贪心算法不是对所有问题都能得到整体最优解,但对范围相当广泛的许多问题他能产生整体最优解或者是整体最优解的近似解. 特性:贪心算法采用自顶向下,以迭代的方法做出相继的贪心选择,每做一次贪心选择就将所求问题简化为一个规模更小的子问题,通过每一步贪心选择,可得到问题的一个最优解,虽然每一步上都要保证能获得局部最优解,但由此产生的全局解有时不一定是最优的,所以贪婪法不

  • Python数据结构与算法之字典树实现方法示例

    本文实例讲述了Python数据结构与算法之字典树实现方法.分享给大家供大家参考,具体如下: class TrieTree(): def __init__(self): self.root = {} def addNode(self,str): # 树中每个结点(除根节点),包含到该结点的单词数,以及该结点后面出现字母的键 nowdict = self.root for i in range(len(str)): if str[i] not in nowdict: # 发现新的组合方式 nowdi

  • Python数据结构与算法之常见的分配排序法示例【桶排序与基数排序】

    本文实例讲述了Python数据结构与算法之常见的分配排序法.分享给大家供大家参考,具体如下: 箱排序(桶排序) 箱排序是根据关键字的取值范围1~m,预先建立m个箱子,箱排序要求关键字类型为有限类型,可能会有无限个箱子,实用价值不大,一般用于基数排序的中间过程. 桶排序是箱排序的实用化变种,其对数据集的范围,如[0,1) 进行划分为n个大小相同的子区间,每一个子区间为一个桶,然后将n非记录分配到各桶中.因为关键字序列是均匀分布在[0,1)上的,所以一般不会有很多记录落入同一个桶中. 以下的桶排序方

  • Python使用三种方法实现PCA算法

    Python使用三种方法实现PCA算法

    主成分分析,即Principal Component Analysis(PCA),是多元统计中的重要内容,也广泛应用于机器学习和其它领域.它的主要作用是对高维数据进行降维.PCA把原先的n个特征用数目更少的k个特征取代,新特征是旧特征的线性组合,这些线性组合最大化样本方差,尽量使新的k个特征互不相关.关于PCA的更多介绍,请参考:https://en.wikipedia.org/wiki/Principal_component_analysis. 主成分分析(PCA) vs 多元判别式分析(MD

  • python实现感知器算法详解

    python实现感知器算法详解

    在1943年,沃伦麦卡洛可与沃尔特皮茨提出了第一个脑神经元的抽象模型,简称麦卡洛可-皮茨神经元(McCullock-Pitts neuron)简称MCP,大脑神经元的结构如下图.麦卡洛可和皮茨将神经细胞描述为一个具备二进制输出的逻辑门.树突接收多个输入信号,当输入信号累加超过一定的值(阈值),就会产生一个输出信号.弗兰克罗森布拉特基于MCP神经元提出了第一个感知器学习算法,同时它还提出了一个自学习算法,此算法可以通过对输入信号和输出信号的学习,自动的获取到权重系数,通过输入信号与权重系数的乘积来

  • Python数据结构与算法之图的广度优先与深度优先搜索算法示例

    本文实例讲述了Python数据结构与算法之图的广度优先与深度优先搜索算法.分享给大家供大家参考,具体如下: 根据维基百科的伪代码实现: 广度优先BFS: 使用队列,集合 标记初始结点已被发现,放入队列 每次循环从队列弹出一个结点 将该节点的所有相连结点放入队列,并标记已被发现 通过队列,将迷宫路口所有的门打开,从一个门进去继续打开里面的门,然后返回前一个门处 """ procedure BFS(G,v) is let Q be a queue Q.enqueue(v) lab

  • Python数据结构与算法之图结构（Graph）实例分析

    Python数据结构与算法之图结构（Graph）实例分析

    本文实例讲述了Python数据结构与算法之图结构(Graph).分享给大家供大家参考,具体如下: 图结构(Graph)--算法学中最强大的框架之一.树结构只是图的一种特殊情况. 如果我们可将自己的工作诠释成一个图问题的话,那么该问题至少已经接近解决方案了.而我们我们的问题实例可以用树结构(tree)来诠释,那么我们基本上已经拥有了一个真正有效的解决方案了. 邻接表及加权邻接字典 对于图结构的实现来说,最直观的方式之一就是使用邻接列表.基本上就是针对每个节点设置一个邻接列表.下面我们来实现一个最简

  • Python数据结构与算法之图的基本实现及迭代器实例详解

    Python数据结构与算法之图的基本实现及迭代器实例详解

    本文实例讲述了Python数据结构与算法之图的基本实现及迭代器.分享给大家供大家参考,具体如下: 这篇文章参考自<复杂性思考>一书的第二章,并给出这一章节里我的习题解答. (这书不到120页纸,要卖50块!!,一开始以为很厚的样子,拿回来一看,尼玛.....代码很少,给点提示,然后让读者自己思考怎么实现) 先定义顶点和边 class Vertex(object): def __init__(self, label=''): self.label = label def __repr__(sel

  • Python数据结构与算法之图的最短路径(Dijkstra算法)完整实例

    本文实例讲述了Python数据结构与算法之图的最短路径(Dijkstra算法).分享给大家供大家参考,具体如下: # coding:utf-8 # Dijkstra算法--通过边实现松弛 # 指定一个点到其他各顶点的路径--单源最短路径 # 初始化图参数 G = {1:{1:0, 2:1, 3:12}, 2:{2:0, 3:9, 4:3}, 3:{3:0, 5:5}, 4:{3:4, 4:0, 5:13, 6:15}, 5:{5:0, 6:4}, 6:{6:0}} # 每次找到离源点最近的一个顶

  • C语言数据结构与算法之图的遍历(二)

    C语言数据结构与算法之图的遍历(二)

    目录 前言  广度优先搜索过程 主要思想  代码实现   前言  在上一章的内容中我们使用了深度优先搜索来进行遍历,这一章我们选择使用广度优先搜索来完成这个图的遍历 --> 结果如下: 广度优先搜索过程 使用广度优先搜索来遍历这个图的过程如下. 首先以一个未被访问过的顶点作为起始顶点,比如以1号点作为起始顶点. 将1号点放到队列中,然后将与1号点相邻的未访问过的顶点 即 2,3,5号顶点依次放入队列中,如下图: 接下来将2号顶点相邻的未访问过的顶点4号放入到队列中.到此所有的顶点都访问过了,遍历

  • C语言数据结构与算法之图的遍历

    C语言数据结构与算法之图的遍历

    目录 引入  深度优先搜索 代码实现  完整代码   引入  在数据结构中常见的有深度优先搜索和广度优先搜索.为什么叫深度和广度呢?其实是针对图的遍历而言的,请看下面这个图: 图是由一些小圆点(称为顶点) 和 连接这些点的直线 (称为边)组成的. 例如上图就是由5个顶点(编号为 1,2,3,4,5) 和5条边(1-2,1-3,1-4,2-4)组成. 现在我们从1号顶点开始遍历这个图,遍历就是把图的每一个顶点都访问一次.使用深度优先搜索将会得到如下的结果. 图中每个顶点旁边的数表示这个顶点是第几个

  • C语言数据结构与算法之图的遍历(一)

    C语言数据结构与算法之图的遍历(一)

    目录 引入  深度优先搜索 代码实现  完整代码   引入  在数据结构中常见的有深度优先搜索和广度优先搜索.为什么叫深度和广度呢?其实是针对图的遍历而言的,请看下面这个图: 图是由一些小圆点(称为顶点) 和 连接这些点的直线 (称为边)组成的. 例如上图就是由5个顶点(编号为 1,2,3,4,5) 和5条边(1-2,1-3,1-4,2-4)组成. 现在我们从1号顶点开始遍历这个图,遍历就是把图的每一个顶点都访问一次.使用深度优先搜索将会得到如下的结果. 图中每个顶点旁边的数表示这个顶点是第几个

  • Python数据结构与算法之列表（链表，linked list）简单实现

    Python 中的 list 并不是我们传统(计算机科学)意义上的列表,这也是其 append 操作会比 insert 操作效率高的原因.传统列表--通常也叫作链表(linked list)--通常是由一系列节点(node)来实现的,其每一个节点(尾节点除外)都持有一个指向下一个节点的引用. 其简单实现: class Node: def __init__(value, next=None): self.value = value self.next = next 接下来,我们就可使用链表的结构来

  • Python数据结构与算法之链表定义与用法实例详解【单链表、循环链表】

    本文实例讲述了Python数据结构与算法之链表定义与用法.分享给大家供大家参考,具体如下: 本文将为大家讲解: (1)从链表节点的定义开始,以类的方式,面向对象的思想进行链表的设计 (2)链表类插入和删除等成员函数实现时需要考虑的边界条件, prepend(头部插入).pop(头部删除).append(尾部插入).pop_last(尾部删除) 2.1 插入: 空链表 链表长度为1 插入到末尾 2.2 删除 空链表 链表长度为1 删除末尾元素 (3)从单链表到单链表的一众变体: 带尾节点的单链表

  • Python数据结构与算法之二叉树结构定义与遍历方法详解

    本文实例讲述了Python数据结构与算法之二叉树结构定义与遍历方法.分享给大家供大家参考,具体如下: 先序遍历,中序遍历,后序遍历 ,区别在于三条核心语句的位置 层序遍历  采用队列的遍历操作第一次访问根,在访问根的左孩子,接着访问根的有孩子,然后下一层 自左向右一一访问同层的结点 # 先序遍历 # 访问结点,遍历左子树,如果左子树为空,则遍历右子树, # 如果右子树为空,则向上走到一个可以向右走的结点,继续该过程 preorder(t): if t: print t.value preorde

随机推荐