第七 章 图
? 7.1 图的定义和基本术语
? 7.2 图的存储结构
? 7.2.1数组表示法
7.2.2邻接表
7.2.3十字链表
7.2.4邻接多重表
? 7.3 图的遍历
7.3.1 深度优先搜索
7.3.2 广度优先搜索
? 7.4 图的连通性问题
7.4.1 无向图的连通分量和生成树
7.4.2 最小生成树
? 7.5 有向无环图及其应用
7.5.1 拓扑排序
7.5.2 关键路径
? 7.6 最短路径
? 7.6.1 从某个源点到其余各顶点的最短路径
? 7.6.2 每一对顶点间的最短路径
?图 (Graph)是较线性表和树更为复杂的结构。
?图 中任意数据两个元素之间都可能相关。
第七 章 图
G1 = (V1,{ A1})
V1 = {v1,v2,v3,v4}
A1 = {<v1,v2>,<v1,v3>,<v3,v4>,<v4,v1>}
G2 = (V2,{ E2})
V2 = {v1,v2,v3,v4,v5}
E2 = {(v1,v2),(v1,v4),(v2,v3),(v2,v5),(v3,v4),(v3,v5)}
7.1 图的定义和基本术语
V1
V3 V4
V2
有向图 G1
V1
V4 V5
V2
无向图 G2
V3
顶点
弧
弧尾
弧头
顶点
边
7.1 图的定义和基本术语 (续一 )
完全图,n个顶点有 n(n-1)/2条边的无向图
有向完全图,n个顶点有 n(n-1)条弧的有向图
稀疏图：有 很少条边的图（如边数 e < nlogn)
稠密图,非稀疏图
权,与边或弧相关的 数
网络,带权的图
V1
V3
V2V
1
V3
V2
2
7
4
子图,G =(V,{E})和 G1 = (V1,{E1})
若 V1属于 V,E1属于 E 则 G1是 G的子图
7.1 图的定义和基本术语 (续二 )
V1 V1
V3 V4
V2
V3
V1
V3 V4
V1
邻接点, 无向图中有边相连的两个顶点互为 邻接点
顶点的 度,无向图中和某顶点相连的邻接点数
入度,有向图中指向某顶点的弧的数目
出度,有向图中从某顶点出发的弧的数目
7.1 图的定义和基本术语 (续三 )
路径,两个顶点之间的顶点序列，该序列的每个顶点
与其前驱是邻接点，每个顶点与其后继也是邻接点
回路（环）,第一顶点和最后顶点相同的路径
简单路径,顶点不重复的路径
连通,两个顶点之间有路径
连通图,任意 两个顶点之间有路径
连通分量,无向图中的极大连通子图 。
强连通图：任意 两个顶点之间有双向路径
强连通分量,有向图中的极大强连通子图。
连通图的 生成树,极小连通子图。
不唯一，但 n个顶点的生成树
有且仅有 n-1条边。
生成森林：
7.2 图的存储结构
7.2.1 数组表示法
#define INFINITY INT_MAX
#define MAX_VERTEX_NUM 20
typedef enum{DG,DN,AG,AN} GraphKind;
typedef struct ArcCell{
VRType adj;
InfoType *info;
}ArcCell,AdjMatrix[MAX_VERTEX_NUM ][MAX_VERTEX_NUM ]
typedef struct {
VetexType vexs[MAX_VERTEX_NUM ];
AdjMatrix arc;
int vexnum,arcnum;
GraphKind kind;
}MGraph;
数组表示法 (邻接矩阵 )
?无向图、有向图、网均适用
易求各顶点的度。
?例如有向图 G1和无向图 G2的 邻接矩阵为
0 1 1 0
0 0 0 0
0 0 0 1
1 0 0 0
G1.arc =
0 1 0 1 0
1 0 1 0 1
0 1 0 1 1
1 0 1 0 0
0 1 1 0 0
G2.arc =
n2的存储量
无向图的 邻接矩阵总是对称的 --可以采用压缩存储
网及其 邻接矩阵
V1
V3
V4
V2
V5
V6
5
48
9
73
1
5
6 5
(a) 网
? 5 ? 7 ? ?
? ? 4 ? ? ?
8 ? ? ? ? 9
? ? 5 ? ? 6
? ? ? 5 ? ?
3 ? ? ? 1 ?
(b) 邻接矩阵
7.2.2 邻接表
--- 链式 存储结构
#define MAX_VERTEX_NUM 20
typedef struct ArcNode{
int adjvex;
struct ArcNode *nextarc;
InfoType *info;
}ArcNode;
typedef struct {
AdjList verteces;
int vexnum,arcnum;
int kind;
}ALGraph;
typedef struct VNode{
VetexType data;
ArcNode *firstarc;
} Vnode,AdjList [MAX_VERTEX_NUM ];
data firstarc头结点
Adjvex nextarc info
表结点
邻接表的 链式 存储结构示意图
0
1
2
3
V1
V2 ^
V3
V4
0
1
2
3
V1
V2
V3
V4
0
1
2
3
4
V1
V2
V3
V4
V5
2 1 ^
3 ^
3 ^
0 ^
0 ^
2 ^
0 ^ 3 1 ^
2 0 ^
2 1 ^
2 0 ^4
3 1 ^4 G1的邻接表
G2的邻接表
G1的逆邻接表
邻接表：
求出度容易，求入度难
邻接表：
求入度容易，求出度难
7.3 图的遍历
?图的遍历：从图的某顶点出发，访问所
有顶点，且每个顶点仅被访问一次。
?两种遍历图的路径：
?深度优先搜索和广度优先搜索
?它们对无向图和有向图都适用
?深度优先搜索类似于树的先根遍历
?广度优先搜索类似于树的层次遍历
7.3.1 深度优先搜索
V1
V2
V4 V5
V8
V3
V6 V7
V1 V2 V4 V8 V5 V3 V6 V7
1 2 3 4 5 6 7 8
visited 1 1 0 1 1 0 0 1
遍历顺序：
非连通的图重复上述过程,使每个顶点均被访问
V1 V2
stack
V4 V8 V5
深度优先搜索算法
Boolean visited[MAX];
Status (* VisitFunc)(int v);
void DFSTraverse(Graph G,Status (* visit)(int v))
{ VisitFunc = visit;
for(v=0; v<G.vexnum; ++v) visited[v] = FALSE;
for(v=0; v<G.vexnum; ++v)
if(!visited[v]) DFS(G,v);
}
void DFS(Graph G,int v)
{ visited[v] = TRUE; VisitFunc(v);
for(w=FirstAdjVex(G,v); w; w = NextAdjVex(G,v,w))
if(!visited[w]) DFS(G,w);
}
7.3.2 广度优先搜索
V1
V2
V4 V5
V8
V3
V6 V7
V1 V2 V3 V4 V5 V6 V7 V8
1 2 3 4 5 6 7 8
visited 1 0 0 0 0 0 0 0
V2 V3
Queue
遍历顺序：
非连通的图重复上述过程,使每个顶点均被访问
void BFSTraverse(Graph G,Status (* visit)(int v))
{
for(v=0; v<G.vexnum; ++v) visited[v] = FALSE;
IntiQueque(Q);
for(v=0; v<G.vexnum; ++v)
if(!visited[v]) {
EnQueue(Q,v);
while(!QueueEmpty(Q)){
DeQueue(u);
visited[u] = TRUE; Visit (u);
for(w=FirstAdjVex(G,u); w; w = NextAdjVex(G,u,w))
if(!visited[w]) {visited[w]=TRUE; visited(w);
EnQueue(G,w); }
}
}
}
广度优先搜索算法
7.4 图的连通性问题
? 7.4.1 无向图的连通分量和生成树
V1
V2
V4
V5
V8
V3
V6
V7
深度优先生成树
V1
V2
V4 V5
V8
V3
V6 V7
广度优先生成树
7.4.3 最小生成树
?连通网的生成树
?一棵生成树的代价 ---树上各边的代价之和
?最小生成树 ---- 一个 连通网的所有生成树中
代价最小的生成树
?求最小生成树的 Prim算法
?求最小生成树的 Kruskal算法
Prim算法示意图
V1
V2 V4
V5
V3
V6
6 5
55
6
6
2
1
3 4
V1
V2 V4
V5
V3
V6
1
V1
V2 V4
V5
V3
V6
1
4
V1
V2 V4
V5
V3
V6
1
4 2
V1
V2 V4
V5
V3
V6
1
4 2
5
V1
V2 V4
V5
V3
V6
1
4 2
5
3
Kruskal算法示意图
V1
V2 V4
V5
V3
V6
6 5
55
6
6
2
1
3 4
V1
V2 V4
V5
V3
V6
1
V1
V2 V4
V5
V3
V6
1
2
V1
V2 V4
V5
V3
V6
1
3 2
V1
V2 V4
V5
V3
V6
1
4 23
V1
V2 V4
V5
V3
V6
1
4 2
5
3
实验与习题
理论习题 7.1,7.2,7.4,7.5 7.7
实验算法题, 7.14