源代码--数据结构与算法(Python版)第8章 图

算法

......... .................................................. ......................

1

4

8.5.2

佛洛伊德（

Floyd< /p>

）算法

......................... .................................................. ..........

1

6

8.6

实例

.

........................... .................................................. ...............................................

1

7

8.6.1

城市之间的交通路线

.

............................................. ...........................................

1

7

8.6.2

单词搜索

.

.................................................. .................................................. ........

1

8

第

8

章

图

图的邻接矩阵举例

import networkx as nx

#

调用

networkx

import as plt

#

调用< /p>

matplotlib

，绘制图

class Graph_Matrix:

#

邻接矩阵

Adjacency Matrix

def __init__(self, vertices=[], matrix=[]):

= matrix

_dict = {}

# {(tail, head):weight}

_array = []

# (tail, head, weight)

es = vertices

_edges = 0

if len(matrix) > 0:

#

创建边的列表

if len(vertices) != len(matrix):

raise IndexError

= Edges()

_edges = len()

elif len(vertices) > 0:

#

节点

列表

= [[0 for col in range(len(vertices))] for row in range(len(vertices))]

_vertices = len()

def isOutRange(self, x):

#

越界

try:

if x >= _vertices or x <= 0:

raise IndexError

except IndexError:

print(

节点下标出界

def isEmpty(self):

#

是否为空

if _vertices == 0:

_vertices = len()

return _vertices == 0

def add_vertex(self, key):

#

添加

结点

if key not in es:

es[key] = len(es) + 1

#

添加一个节点意味着

添加行和列

,

对每一行都

添加一列

for i in range(ticesNumbers()):

[i].append(0)

_vertices += 1

nRow = [0] * _vertices

(nRow)

def getVertex(self, key):

#

返回

节点

pass

def add_edges_from_list(self, edges_list):

#

边列表

: [(tail, head, weight),()]

for i in range(len(edges_list)):

_edge(edges_list[i][0], edges_list[i][1], edges_list[i][2], )

def add_edge(self, tail, head, cost=0):

#

添加

边

if tail not in es:

_vertex(tail)

if head not in es:

_vertex(head)

[(tail)][(head)] = cost

_dict[(tail, head)] = cost

_((tail, head, cost))

_edges = len(_dict)

def getEdges(self, V):

#

返回边

pass

def getVerticesNumbers(self):

#

返回节点数目

if _vertices == 0:

_vertices = len()

return _vertices

def getAllVertices(self):

#

返回

所有的

节点

return es

def getAllEdges(self):

#

返回

所有的

边

for i in range(len()):

for j in range(len()):

if 0 < [i][j] < float('inf'):

_dict[es[i], es[j]] = [i][j]

_([es[i], es[j], [i][j]])

return _array

def __repr__(self):

return str(''.join(str(i) for i in ))

def to_do_vertex(self, i):

print('vertex: %s' % (es[i]))

def to_do_edge(self, w, k):

print('edge

tail:

%s,

edge

head:

%s,

weight:

%s'

%

(es[w],

es[k],

str([w][k])))

def create_undirected_matrix(my_graph):

nodes = ['a', 'b', 'c', 'd', 'e', 'f', 'g', 'h']

matrix = [[0, 1, 1, 1, 1, 1, 0, 0],

# a

[0, 0, 1, 0, 1, 0, 0, 0],

# b

[0, 0, 0, 1, 0, 0, 0, 0],

# c

[0, 0, 0, 0, 1, 0, 0, 0],

# d

[0, 0, 0, 0, 0, 1, 0, 0],

# e

[0, 0, 1, 0, 0, 0, 1, 1],

# f

[0, 0, 0, 0, 0, 1, 0, 1],

# g

[0, 0, 0, 0, 0, 1, 1, 0]]

# h

my_graph = Graph_Matrix(nodes, matrix)

print(my_graph)

return my_graph

def draw_undircted_graph(my_graph):

G = ()

#

建立一个空的无向图

G

for node in my_es:

#

添加

节点

G

.add_node(str(node))

for edge in my_:

#

添加

边

G

.add_edge(str(edge[0]), str(edge[1]))

print(

.nodes())

#

输出全部的节点

print(

.edges())

#

输出全部的边

print(

.number_of_edges())

#

输出边的数量

(G

, with_labels=True)

g(

()

if __name__=='__main__':

my_graph = Graph_Matrix()

create_graph=create_undirec ted_matrix(my_graph)

draw_undircted_graph(create_graph)

【程序运行结果如下所示】

[0, 1, 1, 1, 1, 1, 0, 0][0, 0, 1, 0, 1, 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, 1, 0, 0, 0, 1, 1][0, 0, 0, 0, 0, 1, 0, 1][0, 0, 0, 0, 0, 1, 1, 0]

nodes: ['a', 'b', 'c', 'd', 'e', 'f', 'g', 'h']

edges: [('a', 'b'), ('a', 'c'), ('a', 'd'), ('a', 'e'), ('a', 'f'), ('b', 'c'), ('b', 'e'), ('c', 'd'), ('c', 'f'), ('d', 'e'), ('e', 'f'),

('f', 'g'), ('f', 'h'), ('g', 'h')]

number of edges: 14

程序运行如图

8.5

所示。

图

8.5

加权有向图的邻接矩阵

图的邻接表举例

#

顶点类

class Vertex:

def __init__(self,name):

= name

= []

class Graph:

def __init__(self):

List = {}

def addVertex(self,vertex):

#

图中添加一个顶点

vertex

if vertex in List:

return

List[vertex] = Vertex(vertex)

def addEdge(self,fromVertex,toVertex):

#

添加从顶点

fromVertex

和顶点

toVertex

的边

if fromVertex == toVertex:

return

if fromVertex not in List:

print(

return

if toVertex not in List:

print(

return

if(toVertex not in List[fromVertex].next):

List[fromVertex].(toVertex)

if(fromVertex not in List[toVertex].next):

List[toVertex].(fromVertex)

def removeVertex(self,vertex):

#

图中删除一个顶点

vertex

if vertex in List:

removed = (vertex)

removed =

for key, vertex in ():

if removed in :

(removed)

def removeEdge(self,fromVertex,toVertex):

#

删除从

fromVertex

到

toVert ex

的边

if fromVertex not in List:

if fromVertex not in List:

print(

return

if toVertex not in List:

print(

return

if fromVertex in List[toVertex].next:

List[fromVertex].(toVertex)

List[toVertex].(fromVertex)

if __name__ ==

G = Graph()

for i in range(1,8):

tex(i)

for i in range(1,7):

e(i,i+1)

for i in range(1,4):

e(i,2)

e(i,3)

Vertex(2)

Edge(4,3)

for i,g in G

.():

print(i,)

程序运行结果如下：

1 [3]

3 [1]

4 [5]

5 [4, 6]

6 [5, 7]

7 [6]

8.3

图的遍历

从图中某个顶点出发访遍图 中其余顶点且仅访问一次的过程称为图的遍历。

图的遍历有

两种 方式：深度优先遍历和广度优先遍历。

8.3.1

深度优先遍历

【例

< br>8-7

】深度优先遍历有递归深度优先和迭代深度优先两种方式，针对图

8.9

，具体实现

如下所示：

< br>

图

8.9

例

8-7

无 向图

G = [

{1, 2, 3},

# 0

{0, 4, 6},

# 1

{0, 3},

# 2

{0, 2, 4},

# 3

{1, 3, 5, 6},

# 4

{4, 7},

# 5

{1, 4},

# 6

{5, }

#7

]

print(G)

（

1

）递归深度优先

from collections import deque

def dfs(G

, v, visited=set()):

print(v,

(v)

#

用来存放已经访问过的顶点

# G[v]

是这个顶点的相邻的顶点

for u in G[v]:

# < /p>

这一步很重要，

否则进入无限循环，

只有 这个顶点没有出现在这个集合中才会访问

if u not in visited:

dfs(G

, u, visited)

print('

递归深度优先

dfs')

dfs(G

, 0)

【程序运行结果】

递归深度优先

dfs

0

1

4

3

2

5

7

6

< /p>

（

2

）迭代深度优先

from collections import deque

def dfs_iter(G, v):

visited = set()

s = [v]

while s:

u = ()

if u not in visited:

print(u,

(u)

(G[u])

print('

迭代深 度优先

dfs')

dfs_iter(G

, 0)

【程序运行结果】

迭代深度优先

dfs

0

3

4

6

1

5

7

2

【解析】

可以看到，针对相同的图， 从节点

0

出发进行深度优先遍历。由于第一次选择的