数据结构:图(有向图，无向图),在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) < len(shortest):
shortest = newpath
return shortest
运行结果：
>>> find_shortest_path(graph, 'A', 'D')
['A', 'C', 'D']
这些函数都非常简单，但是却已经接近最优了(用Python写成的代码中)。在另一篇文章中，我将尝试去分析它们的运行速度，并改进它们的性能。
另外还可以引入更多的数据抽象：用一个类来表示一个图，并通过各种方法来实现各种算法。如果通过结构化编程来做这个事情的话，其实对代码的效率提升没什么帮助(有时恰恰相反)。很容易把节点或者弧加上一个命名，就可以来解决实际问题了(比如在地图上查找两个城市中的最短路)。
Python的图邻接矩阵法做为存储结构，0表示没有边，1表示有边。具体代码如下:
#邻接矩阵结构：(www.)
# 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()
-
本站(WWW.)旨在分享和传播互联网科技相关的资讯和技术，将尽最大努力为读者提供更好的信息聚合和浏览方式。
本站(WWW.)站内文章除注明原创外，均为转载,整理或搜集自网络.欢迎任何形式的转载，转载请注明出处.
转载请注明：文章转载自:[169IT-IT技术资讯]
本文标题:地图
iis7站长之家
