?
当前位置:??编程语言>python

数据结构:图(有向图,无向图),在Python中的表示和实现代码示例

?
????发布时间:2014-11-13??


????本文导语:?数据结构:图(有向图,无向图),在Python中的表示和实现代码示例(本文由www.169it.com搜集整理)一、图的存储结构1.1 邻接矩阵 图的邻接矩阵存储方式是用两个数组来表示图。一个一维数组存储图中顶点信息,一个二维数...

?数据结构:(有向图,无向图),在Python中的表示和实现代码示例

(本文由www.169it.com搜集整理)

一、图的存储结构

1.1 邻接矩阵

? ?图的邻接矩阵存储方式是用两个数组来表示图。一个一维数组存储图中顶点信息,一个二维数组(邻接矩阵)存储图中的边或弧的信息。

无向图的边数组是一个对称矩阵。所谓对称矩阵就是n阶矩阵的元满足aij = aji。即从矩阵的左上角到右下角的主对角线为轴,右上角的元和左下角相对应的元全都是相等的。

? ? 从这个矩阵中,很容易知道图中的信息。

? ? (1)要判断任意两顶点是否有边无边就很容易了;

? ? (2)要知道某个顶点的度,其实就是这个顶点vi在邻接矩阵中第i行或(第i列)的元素之和;

? ? (3)求顶点vi的所有邻接点就是将矩阵中第i行元素扫描一遍,arc[i][j]为1就是邻接点;

? ? 而有向图讲究入度和出度,顶点vi的入度为1,正好是第i列各数之和。顶点vi的出度为2,即第i行的各数之和。

1.2 邻接表

? ? 邻接矩阵是不错的一种图存储结构,但是,对于边数相对顶点较少的图,这种结构存在对存储空间的极大浪费。因此,找到一种数组与链表相结合的存储方法称为邻接表。

? ? 邻接表的处理方法是这样的:

? ? (1)图中顶点用一个一维数组存储,当然,顶点也可以用单链表来存储,不过,数组可以较容易的读取顶点的信息,更加方便。

? ? (2)图中每个顶点vi的所有邻接点构成一个线性表,由于邻接点的个数不定,所以,用单链表存储,无向图称为顶点vi的边表,有向图则称为顶点vi作为弧尾的出边表。

1.3 十字链表

? ? 对于有向图来说,邻接表是有缺陷的。关心了出度问题,想了解入度就必须要遍历整个图才知道,反之,逆邻接表解决了入度却不了解出度情况。十字链表(Orthogonal List)是有向图的一种存储方法,它实际上是邻接表与逆邻接表的结合,即把每一条边的边结点分别组织到以弧尾顶点为头结点的链表和以弧头顶点为头顶点的链表中。

二、图在Python中的表示

? ?几乎没有编程语言把图作为一项直接支持的数据类型,Python也不例外。然而,图很容易通过列表和词典来构造。比如说,这有一张简单的图:

 A?->?B
 A?->?C
 B?->?C
 B?->?D
 C?->?D
 D?->?C
 E?->?F
 F?->?C

这个图有6个节点(A-F)和8个弧。它可以通过下面的Python数据结构来表示:

graph?=?{'A':?['B',?'C'],
?????????????'B':?['C',?'D'],
?????????????'C':?['D'],
?????????????'D':?['C'],
?????????????'E':?['F'],
?????????????'F':?['C']}

? ? 这是一个词典,每个key都是图的节点。每个key都对应一个列表,列表里面存的是直接通过一个弧和这个节点连接的节点。这个图非常简单了,不过更简单的是用数字来代替字母来表示一个节点。不过用名字(字母)来表示很方便,而且也便于扩展,比如可以改成城市的名字等等。

我们来写一个函数来判断两个节点间的路径。它的参数是一个图、一个起始节点和一个终点。它会返回一个列表,列表里面存有组成这条路径的节点(包括起点和终点)。如果两个节点之间没有路径的话,那就返回None。相同的节点不会在返回的路径中出现两次或两次以上(就是说不会包括环)。这个算法用到了一个很重要的技术,叫做回溯:它会去尝试每一种可能,直到找到结果。

def?find_path(graph,?start,?end,?path=[]):
????????path?=?path?+?[start]
????????if?start?==?end:
????????????return?path
????????if?not?graph.has_key(start):
????????????return?None
????????for?node?in?graph[start]:
????????????if?node?not?in?path:
????????????????newpath?=?find_path(graph,?node,?end,?path)
????????????????if?newpath:?return?newpath
????????return?None

运行的结果(上面的那张图):

>>>?find_path(graph,?'A',?'D')
  ['A',?'B',?'C',?'D']
>>>

代码中的第二个if(译者注:是指if not graph.has_key(start):这句)仅仅在遇到一类 特殊的节点的时候才有用,这类节点有其他的节点指向它,但是它没有任何弧指向其他的节点,所以就并不会在图这个词典中作为key被列出来。也可以这样来处 理,即这个节点也作为一个key,但是有一个空的列表来表示其没有指向其他节点的弧,不过不列出来会更好一些。

注意,当我们调用find_graph()的时候,使用了3个参数,但是实际上使用了4个参数:还有一个是当前已经走过的路径。这个参数的默认值是 一个空列表,“[]”,表示还没有节点被访问过。这个参数用来避免路径中存在环(for循环中的第一个if语句)。path这个参数本身不会修改,我们用 “path = path +?[start]”只是创建了一个新的列表。如果我们使用“path.append(start)”的话,那我们就修改了path的值,这样会产生灾难性后 果了。如果使用元组的话,我们可以保证这个是不会发生的。在使用的时候要写“path = path + (start,)”,注意“(start)”并不是一个单体元组,只是一个括号表达式而已。

很容易修改这个函数来实现返回一个节点到另一个节点的所有路径,而不仅仅只查找第一条路径:

def?find_all_paths(graph,?start,?end,?path=[]):
path?=?path?+?[start]
????????if?start?==?end:
????????????return?[path]
????????if?not?graph.has_key(start):
????????????return?[]
????????paths?=?[]
????????for?node?in?graph[start]:
????????????if?node?not?in?path:
????????????????newpaths?=?find_all_paths(graph,?node,?end,?path)
????????????????for?newpath?in?newpaths:
????????????????????paths.append(newpath)
????????return?paths
>>>?find_all_paths(graph,?'A',?'D')
  [['A',?'B',?'C',?'D'],?['A',?'B',?'D'],?['A',?'C',?'D']]
>>>

还可以改成查找最短路径

def?find_shortest_path(graph,?start,?end,?path=[]):
????????path?=?path?+?[start]
????????if?start?==?end:
????????????return?path
????????if?not?graph.has_key(start):
????????????return?None
????????shortest?=?None
????????for?node?in?graph[start]:
????????????if?node?not?in?path:
????????????????newpath?=?find_shortest_path(graph,?node,?end,?path)
????????????????if?newpath:
????????????????????if?not?shortest?or?len(newpath)?

运行结果:

>>>?find_shortest_path(graph,?'A',?'D')
  ['A',?'C',?'D']

这些函数都非常简单,但是却已经接近最优了(用Python写成的代码中)。在另一篇文章中,我将尝试去分析它们的运行速度,并改进它们的性能

另外还可以引入更多的数据抽象:用一个类来表示一个图,并通过各种方法来实现各种算法。如果通过结构化编程来做这个事情的话,其实对代码的效率提升没什么帮助(有时恰恰相反)。很容易把节点或者弧加上一个命名,就可以来解决实际问题了(比如在地图上查找两个城市中的最短路)。

? ? Python的图邻接矩阵法做为存储结构,0表示没有边,1表示有边。具体代码如下:

#邻接矩阵结构:(www.169it.com)
#???????map[][]?=?{
#????-1,1,0,0,1,0,0,0
#????0,-1,0,0,0,0,0,0
#????0,0,-1,0,0,0,0,0
#????0,0,0,-1,0,0,0,0
#????0,0,0,0,-1,0,0,0
#????0,0,0,0,0,-1,0,0
#????0,0,0,0,0,0,-1,0
#????0,0,0,0,0,0,0,-1
#????}
????
class?Graph:
????def?__init__(self,?maps?=?[],?nodenum?=?0,?edgenum?=?0):
????????self.map?=?maps???????#图的矩阵结构
????????self.nodenum?=?len(maps)
????????self.edgenum?=?edgenum
?????#???self.nodenum?=?GetNodenum()#节点数
?????#??self.edgenum?=?GetEdgenum()#边数
????def?isOutRange(self,?x):
????????try?:
????????????if?x?>=?self.nodenum?or?x?<=?0:
????????????????raise??IndexError
????????except?IndexError:
????????????print("节点下标出界")
????????????
????def?GetNodenum(self):
????????self.nodenum?=?len(self.map)
????????return?self.nodenum
????def?GetEdgenum(self):
????????GetNodenum()
????????self.edgenum?=?0
????????for?i?in?range(self.nodenum):
????????????for?j?in?range(self.nodenum):
????????????????if?self.map[i][j]?is?1:
????????????????????self.edgenum?=?self.edgenum?+?1
????????return?self.edgenum
????
????def?InsertNode(self):
????????for?i?in?range(self.nodenum):
????????????self.map[i].append(0)
????????self.nodenum?=?self.nodenum?+?1
????????ls?=?[0]?*?self.nodenum
????????self.map.append(ls)
????#假删除,只是归零而已
????def?DeleteNode(self,?x):????????
????????for?i?in?range(self.nodenum):
????????????if?self.map[i][x]?is?1:
????????????????self.map[i][x]?=?0
????????????????self.edgenum?=?self.edgenum?-1
????????????if?self.map[x][i]?is?1:
????????????????self.map[x][i]?=?0
????????????????self.edgenum?=?self.edgenum?-?1
????????????????
????def?AddEdge(self,?x,?y):
????????if?self.map[x][y]?is?0:
????????????self.map[x][y]?=?1
????????????self.edgenum?=?self.edgenum?+?1
????????
????def?RemoveEdge(self,?x,?y):
????????if?self.map[x][y]?is?0:
????????????self.map[x][y]?=?1
????????????self.edgenum?=?self.edgenum?+?1
????????????
????def?BreadthFirstSearch(self):
????????def?BFS(self,?i):
????????????print(i)
????????????visited[i]?=?1
????????????for?k?in?range(self.nodenum):
????????????????if?self.map[i][k]?==?1?and?visited[k]?==?0:
????????????????????BFS(self,?k)
????????????????
????????visited?=?[0]?*?self.nodenum
????????for?i?in?range(self.nodenum):
????????????if?visited[i]?is?0:
????????????????BFS(self,?i)
????????
????def?DepthFirstSearch(self):
????????def?DFS(self,?i,?queue):
????????????
????????????queue.append(i)?
????????????print(i)
????????????visited[i]?=?1
????????????if?len(queue)?!=?0:
????????????????w?=?queue.pop()
????????????????for?k?in?range(self.nodenum):
????????????????????if?self.map[w][k]?is?1?and?visited[k]?is?0:
????????????????????????DFS(self,?k,?queue)
???????
????????visited?=?[0]?*?self.nodenum
????????queue?=?[]
????????for?i?in?range(self.nodenum):
????????????if?visited[i]?is?0:
????????????????DFS(self,?i,?queue)?
def?DoTest():
????maps?=?[
????????[-1,?1,?0,?0],
????????[0,?-1,?0,?0],
????????[0,?0,?-1,?1],
????????[1,?0,?0,?-1]]
????G?=?Graph(maps)
????G.InsertNode()
????G.AddEdge(1,?4)
????print("广度优先遍历")
????G.BreadthFirstSearch()
????print("深度优先遍历")
????G.DepthFirstSearch()
????
if?__name__?==?'__main__':
????DoTest()


    您可能感兴趣的文章:

相关文章推荐:
  • <<大话数据结构>>中冒泡排序算法改进
  • 强人,linux下驱动相关数据结构和usb设备数据结构之间的功能分析
  • 基于Key-Value的NOSQL数据库Redis的数据结构及常用相关命令介绍
  • GNU汇编fill填充一个数据结构使得另一个数据结构全部清零
  • Oracle数据库(Oracle Database)体系结构及基本组成介绍
  • 请问:在用proc方式往数据库插入数据时,我能不能定义一个结构体,它与表的每一项对应,将结构体赋好值后,再只将这个结构体插入表中,这行不行啊?
  • 请教:请问java中存放数据库中的记录,用什么数据结构?(hashtable?vector?还是别的?)
  • 通用数据结构库 GDSL
  • 如何把一个数组转化为一个数据结构,如ArrayList。
  • 多维数据结构 mdds
  • 数据结构存储
  • 数据结构和算法教程 OpenDSA
  • C数据结构库 liblfds
  • 一个新的JavaScript数据结构 stream.js
  • 数据结构
  • 高手帮帮忙!vi中如何实现跳转到任意结构体或函数的声明处,包括系统库中声明的函数和数据结构?
  • 请教各位,数据结构在工程中到底有什么应用呢
  • 放假了,想用java数据结构,请问大虾们该如何开始?
  • 数据结构讨论群
  • 数据结构库 libx1f4l2
  • 请问哪里有关于JAVA版的数据结构的书当


  • 站内导航:


    特别声明:169IT网站部分信息来自互联网,如果侵犯您的权利,请及时告知,本站将立即删除!

    ?2012-2019,169IT.COM,E-mail:www_169it_com#163.com(请将#改为@)

    浙ICP备11055608号