数据结构 图的存储表示
@staticmethod def _out_edges(mat, v): edges = [] row = mat[v] for i in range(len(row)): if row[i] != 0 and row[i] != inf: edges.append((i, row[i])) # (邻接点,边权) return edges
2016 《数据结构》
图
主要内容
图的概念和操作 图的存储:邻接矩阵,邻接表 图的遍历:宽度优先,深度优先 生成树:DFS 生成树,BFS 生成树 最小生成树:Prim 算法,Kruskal 算法 最短路径问题:
单源点最短路径和 Dijkstra 算法 所有顶点之间的最短路径和 Floyd 算法
2018/3/7
第七章 图
21
获取顶点v的所有“邻接点”(邻接边、出边)
def out_edges(self, v): '''获取v的所有(邻接点,边权)对,以list形式返回''' assert 0 <= v < self._vnum return self._mat[v]
2018/3/7
第七章 图
2018/3/7
第七章 图
24
2018/3/7
第七章 图
25
无权图的读入
input = sys.stdin.read()
data = list(map(int, input.split())) n, m = data[0:2] data = data[2:] edges = list(zip(data[0:(2 * m):2], data[1:(2 * m):2])) adj = [[] for _ in range(n)] for (a, b) in edges: adj[a - 1].append(b - 1) adj[b - 1].append(a - 1) # 有向图去除此句!
8
A
3 9 4
6 5 1
D
2
0 3 5 0 1 9 0 6
8 4 2 0
14
B
2018/3/7
C
g3.out_edges(2) = [ (0, 9), (3, 2) ]
获取顶点v的所有“邻接点”(邻接边、出边)
def out_edges(self, v): '''获取v的所有(邻接点,边权)对,以list形式返回''' assert 0 <= v < self._vnum # 用assert替代异常 return Graph._out_edges(self._mat, v)
2018/3/7 第七章 图 27
将标准输入stdin重定向到文件
import sys # 导入sys模块 input = sys.stdin.read() 这里要在 console窗口 中,转到文件所在的目录,执行命令: python **.py < graph.txt 其中: **.py 是包含代码段的文件 graph.txt是图信息文件,和**.py在同一目录下
g1.out_edges(1) = [ (0, 1), (4, 1), (5, 1) ]
第七章 图
17
有向图的邻接表
A
B C E
0 1 2 3 4 A B 1 2 3 0 2 ^ ^ ^ 1 ^ 4 ^
C
D E
D
Python中list的list:
[ [(1, 1), (4, 1)], [(2, 1)], [(3, 1)], [(0, 1), (1, 1)] [(2, 1)] ]
22
说明
课本中对无权、有权图统一处理了,具体应用中 可针对图的类型做专门的定义,使得无权图的邻 接点集是单纯的点集,不是(u, 1)形式的边对。
通常对图的表示和操作,直接使用list的list型的对 象即可,不需要封装成专门Graph类型。
2018/3/7
第七章 图
23
由文件中读入图信息
UCSD_Algorithms on Graph
0
A
1 2 0 0
3 1 9 6 ^
2 0 3
5 4 ^ 2 ^
3
8 ^
1
2 3
B
C D
B
1
C
Python中list的list:
[ [(1, 3), (2, 5), (3, 8)], [(2, 1), (0, 4)], [(0, 9), (3, 2)], [(0, 6)] ]
2018/3/7
g3.out_edges(2) = [ (0, 9), (3, 2) ]
2018/3/7
第七章 图
15
邻接表 Adjacent List
(邻接矩阵的压缩)
2018/3/7
第七章 图
16
无向图的邻接表
B A
F E
C
D
0
1 2 3 4 5
A B C D E F
1
0 3 2 0 1
4
4 5 5 1 2
^
5 ^ ^ ^ 3 ^ ^
Python中list的list: [ [(1, 1), (4, 1)], [(0, 1), (4, 1)], [(3, 1), (5, 1)], [(2, 1), (5, 1)], [(0, 1), (1, 1)], [(1, 1), (2, 1), (3, 1)] ] 2018/3/7
B A F
C
D
E
Python等长list的list:
[ [0, 1, 0, 0, 1, 0], [1, 0, 0, 0, 1, 1], [0, 0, 0, 1, 0, 1], [1, 1, 0, 0, 0, 0], [0, 1, 1, 1, 0, 0] ]
2018/3/7 第七章 图 10
有向图的邻接矩阵:非对称
第七章 图
20
图的建立——邻接表
# 课本采用了继承方式,逻辑上不是太好!
class GraphA(Graph): def __init__(self, mat): vnum = len(mat)
# mat是等长list的list
# 所有顶点的(邻接点,边权)对的list self._mat = [Graph._out_edges(mat, i) for i in range(vnum)] self._vnum = vnum
12
2018/3/7
第七章 图
图的建立——邻接矩阵
class Graph: def __init__(self, mat): vnum = len(mat) # 对传入的mat做了拷贝构造 self._mat = [mat[i][:] for i in range(vnum)] self._vnum = vnum
2018/3/7
第七章 图
13
获取顶点v的所有“邻接点”
B A F E C
0 1 0 0 1 0 1 0 0 1 0 0 0 0 1 1 0 0 1 0 1 0 1 0 0 1 1 0 0 0 0 1 1 1 0 0
D
g1.out_edges(1) = [ (0, 1), (4, 1), (5, 1) ]
关系集
顶点之间关系,即边集或弧集 边或弧的总数
图的类型
有向、无向、带权、不带权
第七章 图 *
*
邻接矩阵 Adjacent Matrix
2018/3/7
第七章 图
9
无向图的邻接Байду номын сангаас阵:对称
0 1 0 0 1 0 1 0 0 1 0 0 0 0 1 1 0 0 1 0 1 0 1 0 0 1 1 0 0 0 0 1 1 1 0 0
也可以: python **.py 然后手工输入图信息,以Ctrl+Z结束输入。
2018/3/7
第七章 图
28
AOV 网,拓扑排序
AOE 网,关键路径
*
第七章 图
*
无向图、有向图、带权图(网)
B A F E A
3 9 4 5 8 6
C D B C D
2
A E D
B
2018/3/7
1
第七章 图
C
3
图的概念
Graph=( V, E )
V = { v | v 某数据对象}
• 顶点的有穷非空集合;
v
*
第七章 图
图的基本操作
ADT Graph:
Graph(self)
vertex_num(self) vertices(self) add_vertex(self, v) add_edge(self, v1, v2) get_edge(self, v1, v2) out_edges(self, v) degree(self, v)
E = {(u, v) | u, v V } 或 E = {<u, v> | x, y V}
• 是顶点之间关系的有穷集合,也叫边(或弧)集合。
u
v
u
v
• 称u、v互为邻接点。
2018/3/7
第七章 图
4
顶点的度
与之相关联的边或弧的数目 有向图:D(v)=ID(v)+OD(v)
ID(v): 入度(in-degree),即入边数; OD(v):出度(out-degree),即出边数。
*
第七章 图
*