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

赞 (0)

相关推荐

  • 深度剖析使用python抓取网页正文的源码

    本方法是基于文本密度的方法,最初的想法来源于哈工大的<基于行块分布函数的通用网页正文抽取算法>,本文基于此进行一些小修改. 约定:       本文基于网页的不同行来进行统计,因此,假设网页内容是没有经过压缩的,就是网页有正常的换行的. 有些新闻网页,可能新闻的文本内容比较短,但其中嵌入一个视频文件,因此,我会给予视频较高的权重:这同样适用于图片,这里有一个不足,应该是要根据图片显示的大小来决定权重的,但本文的方法未能实现这一点. 由于广告,导航这些非正文内容通常以超链接的方式出现,因此文本将

  • 13个最常用的Python深度学习库介绍

    如果你对深度学习和卷积神经网络感兴趣,但是并不知道从哪里开始,也不知道使用哪种库,那么这里就为你提供了许多帮助. 在这篇文章里,我详细解读了9个我最喜欢的Python深度学习库. 这个名单并不详尽,它只是我在计算机视觉的职业生涯中使用并在某个时间段发现特别有用的一个库的列表. 这其中的一些库我比别人用的多很多,尤其是Keras.mxnet和sklearn-theano. 其他的一些我是间接的使用,比如Theano和TensorFlow(库包括Keras.deepy和Blocks等). 另外的我只

  • 深度定制Python的Flask框架开发环境的一些技巧总结

    Flask 环境配置 你的应用程序可能需要大量的软件包才能正常的工作.如果都不需要 Flask 包的话,你有可能读错了教程.当应用程序运行的时候,你的应用程序的 环境 基本上是所有一切事情的根基.我们是幸运的,因为有许多方式使得我们能够轻松地管理我们的环境. 使用 virtualenv 管理你的环境 virtualenv是用于在所谓 虚拟环境 中隔离你的应用程序的一个工具.一个虚拟环境是包含了你的应用依赖的软件的一个目录.一个虚拟环境也能够改变你的环境变量以维持你的开发环境包含的环境变量.不用下

  • Python 类与元类的深度挖掘 I【经验】

    上一篇介绍了 Python 枚举类型的标准库,除了考虑到其实用性,还有一个重要的原因是其实现过程是一个非常好的学习.理解 Python 类与元类的例子.因此接下来两篇就以此为例,深入挖掘 Python 中类与元类背后的机制. 翻开任何一本 Python 教程,你一定可以在某个位置看到下面这两句话: Python 中一切皆为对象(Everything in Python is an object); Python 是一种面向对象编程(Object Oriented Programming, OOP

  • Python 类与元类的深度挖掘 II【经验】

    上一篇解决了通过调用类对象生成实例对象过程中可能遇到的命名空间相关的一些问题,这次我们向上回溯一层,看看类对象本身是如何产生的. 我们知道 type() 方法可以查看一个对象的类型,或者说判断这个对象是由那个类产生的: print(type(12)) print(type('python')) class A: pass print(type(A)) 通过这段代码可以看出,类对象 A 是由type() 产生的,也就是说 type 也可以用来产生新的对象,而且产生的是类对象,因此它是所有类对象的类

  • python数据结构之图深度优先和广度优先实例详解

    本文实例讲述了python数据结构之图深度优先和广度优先用法.分享给大家供大家参考.具体如下: 首先有一个概念:回溯 回溯法(探索与回溯法)是一种选优搜索法,按选优条件向前搜索,以达到目标.但当探索到某一步时,发现原先选择并不优或达不到目标,就退回一步重新选择,这种走不通就退回再走的技术为回溯法,而满足回溯条件的某个状态的点称为"回溯点". 深度优先算法: (1)访问初始顶点v并标记顶点v已访问. (2)查找顶点v的第一个邻接顶点w. (3)若顶点v的邻接顶点w存在,则继续执行:否则回

  • Python疫情确诊折线图实现数据可视化实例详解

    Python疫情确诊折线图实现数据可视化实例详解

    目录 案例描述 实现步骤 一.导入模块 二.读取文件内容 三.json转换python 四.获取需要用到的数据 五.生成图表 六.关闭文件 案例描述 根据可参考数据,实现对疫情确诊人数数据的可视化. 利用json转换工具,将数据格式化,需要取出下面两部分的内容. 可视化效果图: 实现步骤 一.导入模块 导入可能用到的模块 import json from pyecharts.charts import Line 二.读取文件内容 打开相应的文件,使用变量us_data保存文件的内容 f_us =

  • Java数据结构之图的两种搜索算法详解

    Java数据结构之图的两种搜索算法详解

    目录 前言 深度优先搜索算法 API设计 代码实现 广度优先搜素算法 API设计 代码实现 案例应用 前言 在很多情况下,我们需要遍历图,得到图的一些性质,例如,找出图中与指定的顶点相连的所有顶点,或者判定某个顶点与指定顶点是否相通,是非常常见的需求. 有关图的搜索,最经典的算法有深度优先搜索和广度优先搜索,接下来我们分别讲解这两种搜索算法. 学习本文前请先阅读这篇文章 [数据结构与算法]图的基础概念和数据模型. 深度优先搜索算法 所谓的深度优先搜索,指的是在搜索时,如果遇到一个结点既有子结点,

  • 基于python 二维数组及画图的实例详解

    1.二维数组取值 注:不管是二维数组,还是一维数组,数组里的数据类型要一模一样,即若是数值型,全为数值型 #二维数组 import numpy as np list1=[[1.73,1.68,1.71,1.89,1.78], [54.4,59.2,63.6,88.4,68.7]] list3=[1.73,1.68,1.71,1.89,1.78] list4=[54.4,59.2,63.6,88.4,68.7] list5=np.array([1.73,1.68,1.71,1.89,1.78])

  • 对python判断是否回文数的实例详解

    设n是一任意自然数.若将n的各位数字反向排列所得自然数n1与n相等,则称n为一回文数.例如,若n=1234321,则称n为一回文数:但若n=1234567,则n不是回文数. 上面的解释就是说回文数和逆序后的结果是相等的.这就是判断一个数值是否是回文数的标准. 代码也是根据这个思路来实现的. # -*- coding: utf-8 -*- """ Created on Sun Aug 5 09:01:38 2018 @author: FanXiaoLei ""

  • Java数据结构之图的路径查找算法详解

    Java数据结构之图的路径查找算法详解

    目录 前言 算法详解 实现 API设计 代码实现 前言 在实际生活中,地图是我们经常使用的一种工具,通常我们会用它进行导航,输入一个出发城市,输入一个目的地 城市,就可以把路线规划好,而在规划好的这个路线上,会路过很多中间的城市.这类问题翻译成专业问题就是: 从s顶点到v顶点是否存在一条路径?如果存在,请找出这条路径. 例如在上图上查找顶点0到顶点4的路径用红色标识出来,那么我们可以把该路径表示为 0-2-3-4. 如果对图的前置知识不了解,请查看系列文章: [数据结构与算法]图的基础概念和数据

  • python里使用正则表达式的组嵌套实例详解

    python里使用正则表达式的组嵌套实例详解 由于组本身是一个完整的正则表达式,所以可以将组嵌套在其他组中,以构建更复杂的表达式.下面的例子,就是进行组嵌套的例子: #python 3.6 #蔡军生 #http://blog.csdn.net/caimouse/article/details/51749579 # import re def test_patterns(text, patterns): """Given source text and a list of pa

  • python 读取excel文件生成sql文件实例详解

    python 读取excel文件生成sql文件实例详解 学了python这么久,总算是在工作中用到一次.这次是为了从excel文件中读取数据然后写入到数据库中.这个逻辑用java来写的话就太重了,所以这次考虑通过python脚本来实现. 在此之前需要给python添加一个xlrd模块,这个模块是专门用来操作excel文件的. 在mac中可以通过easy_install xlrd命令实现自动安装模块 import xdrlib ,sys import xlrd def open_excel(fil

  • python文件特定行插入和替换实例详解

    python文件特定行插入和替换实例详解 python提供了read,write,但和很多语言类似似乎没有提供insert.当然真要提供的话,肯定是可以实现的,但可能引入insert会带来很多其他问题,比如在插入过程中crash掉可能会导致后面的内容没来得及写回. 不过用fileinput可以简单实现在特定行插入的需求: Python代码 import os import fileinput def file_insert(fname,linenos=[],strings=[]): ""

  • Python字符串和字典相关操作的实例详解

    Python字符串和字典相关操作的实例详解 字符串操作: 字符串的 % 格式化操作: str = "Hello,%s.%s enough for ya ?" values = ('world','hot') print str % values 输出结果: Hello,world.hot enough for ya ? 模板字符串: #coding=utf-8 from string import Template ## 单个变量替换 s1 = Template('$x, glorio

随机推荐