文档介绍：第七章图
图的定义
图的存储表示
图的遍历
第七章 图
最小生成树
最短路径问题
拓扑排序
第七章 图
图的存储表示
一、图的数组(邻接矩阵)存储表示
二、图的邻接表存储表示
三、有向图的十字链表存储表示
四、无向图的邻接多重表存储表示
Aij={
0 (i,j)VE
1 (i,j)VE
一、图的数组(邻接矩阵)存储表示
B
A
C
D
F
E
定义:矩阵的元素为
有向图的邻接矩阵为非对称矩阵
A
B
E
C
F
D
B
A
C
F
E
二、图的邻接表
存储表示
A 1 4
B 0 4 5
C 3 5
D 2 5
E 0 1
F 1 2 3
0 1 2 3 4 5
有向图的邻接表
1 4
2
3
0 1
2
0 1 2 3 4
A
B
C
D
E
A
B
E
C
F
可见,在有向图的邻接表中不易找到指向该顶点的弧
图的遍历
从图中某个顶点出发游历图,访遍
图中其余顶点,并且使图中的每个顶点
仅被访问一次的过程。
深度优先搜索
广度优先搜索
遍历应用举例
从图中某个顶点V0 出发,访问此顶点,然后依次从V0的各个未被访问的邻接点出发深度优先搜索遍历图,直至图中所有和V0有路径相通的顶点都被访问到。
一、深度优先搜索遍历图
连通图的深度优先搜索遍历