下一页 返 回 退 出
27
图8.8 网络邻接矩阵示例
邻接矩阵存储结构
/**************************************/ /* 邻接矩阵类型定义 文件名：ljjz.h */ /**************************************/ #include <stdio.h> #define FINITY 5000 /*此处用5000代表无穷大*/ #define M 20 /*最大顶点数*/ typedef char vertextype; /*顶点值类型*/ typedef int edgetype; /*权值类型*/ typedef struct{ vertextype vexs[M]; /*顶点信息域*/ edgetype edges[M][M]; /*邻接矩阵*/ int n,e; /*图中顶点总数与边数*/ } Mgraph;
首 页 上一页 下一页 返 回 退 出
10
无论有向图还是无向图，图中的每条边均关联于两 个顶点，因此，顶点数n、边数e和度数之间有如下 关系：
1 n e= D(vi ) ……….（式8-1） 2 i 1
四、子图
给定两个图Gi和Gj，其中Gi=（Vi，Ei），Gj= （Vj，Ej），若满足ViVj，EiEj，则称Gi是Gj的 子图。
j 0
n 1
… （8-3）
首 页
上一页
下一页
返 回
退 出
25
二、网络的邻接矩阵
当G=（V，E）是一个网络时，G的邻接矩阵是具 有如下性质的n阶方阵： Wij 当（vi，vj）或< vi，vj >E（G）
A[i，j]=
0
当（vi，vj）或< vi，vj > E（G）且i=j
∞ 当（vi，vj）或< vi，vj > E（G）且i≠j 其中Wij表示边上的权值；∞表示一个计算机允 许的、大于所有边上权值的数。
G=<V, E>是图, V={v0,v1,v2, … vn-1 },设顶点的 角标为它的编号
首 页 上一页 下一页 返 回 退 出
22
8.3.1邻接矩阵及其实现
一、非网络的邻接矩阵
给定图G=（V，E），其中V（G）={v0，…， vi，…，vn-1}，G的邻接矩阵（Adacency Matrix）是 具有如下性质的n阶方阵：
1, 如果 < i , j > E 或者 (i , j ) E A [i, j ] 0, 否则
无向图的邻接矩阵是对称的，有向图的邻接矩 阵可能是不对称的。
首 页 上一页 下一页 返 回 退 出
23
图的邻接矩阵示例
v0 v2 v0 v1 v1 v3 v3
v2
0 1 1 1
0 1 0 0
v1 v2 v2 v3 v4 v1 v3 v4
图8.5 （a）非强连通图G6
首 页 上一页
（b）G6的两个强连通分量H3和H4
下一页 返 回 退 出
17
七、网络
有时在图的每条边上附上相关的数值，这种与 图的边相关的数值叫权。 权可以表示两个顶点之间的距离、耗费等具有 某种意义的数。若将图的每条边都赋上一个权，则 称这种带权图为网络。
首 页
上一页
下一页
返 回
退 出
13
如果一条路径上除了起点v和终点u相同外，其余 顶点均不相同，则称此路径为一条简单路径。起点和 终点相同（v=u）的简单路径称为简单回路或简单环。
首 页
上一页
下一页
返 回
退 出
14
v1
v1 v3 无向图G2 v3
v2
六、连通图与强连通图
无向完全图G3 v2 v4
v4
首 页 上一页 下一页 返 回 退 出
20
8.3图的基本存储结构

图的邻接矩阵存储表示法 图的邻接表表示法
图的邻接多重表表示法
首 页
上一页
下一页
返 回
退 出
21
8.3图的基本存储结构
V0 V2 V3 V4 V2 V3 V1 V0
V1
图的存储结构至少要保存两类信息： 1)顶点的数据 如何表示顶点间的关系？ 2)顶点间的关系 约定:
首 页
上一页
下一页
返 回
退 出
26
网络的邻接矩阵示例
V0 56 V1 34 78 V2 25 V3 V0 64 V1 45 50 V2
0 56 34 78 56 0 ∞ ∞ A3= 34 ∞ 0 25 A4=
0
∞
50
45
∞ 0
78 ∞ 25 0
（a）G7的邻接矩阵
首 页 上一页
64 ∞
0
（b）G8的邻接矩阵
首 页 上一页 下一页 返 回 退 出
15
例：非连通图及其连通分量示例
V3 V1 V2
V4 V1 V2
V3
V4
V5
V5
（a）非连通图G5
（b）G5的两个连通分量H1和H2
在有向图G中，若对于V（G）中任意两个不同的 顶点vi和vj，都存在从vi到vj以及从vj到vi的路径，则称 G是强连通图。
首 页 上一页 下一页 返 回 退 出
16
有向图的极大强连通子图称为G的强连通分量。 根据强连通图的定义，可知强连通图的唯一强连通 分量是其自身，而非强连通的有向图有多个强连分 量。例如，图8.2（b）所示的有向图G4是一个具有 4个顶点的强连通图，图8.5（a）所示的有向图G6 不是强连通图（v2、v3、v4没有到达v1的路径）， 它的两个强连通分量H3与H4如图8.5（b）所示。
第８章 图
图的基本概念
图的基本运算 图的基本存储结构 图的遍历 生成树与最小生成树
最短路径
拓扑排序 关键路径
首 页 上一页 下一页 返 回 退 出
1
8.1 图的基本概念
一、图的定义
图是由一个非空的顶点集合和一个描述顶点之间 多对多关系的边（或弧）集合组成的一种数据结构， 它可以形式化地表示为：
首 页
上一页
下一页
返 回
退 出
8
例：图8-2
v1
v2 v4 v3 v2 v4
v1
v3
（a）无向完全图G3（b）有向完全图G4
图8.2所示的G3与G4分别是具有4个顶点的无向 完全图和有向完全图。图G3共有4个顶点6条边；图 G4共有4个顶点12条边。 若（vi，vj）是一条无向边，则称顶点vi和vj互为 邻接点 。
图＝（V，E）
其中V={x|x某个数据对象集}，它是顶点的有穷 非空集合；E={（x，y）|x，yV}或E={<x，y>|x， yV且P（x，y）}，它是顶点之间关系的有穷集合， 也叫做边集合，P（x，y）表示从x到y的一条单向 通路。
首 页 上一页 下一页 返 回 退 出
2
图的应用举例
例1 交通图（公路、铁路） 顶点：地点 边：连接地点的公路 交通图中的单行道双行道，分别用有向边、无向边表示； 例2 电路图 顶点：元件 边：连接元件之间的线路 例3 通讯线路图 顶点：地点 边：地点间的连线 V0 V2 V1
首 页 上一页 下一页 返 回 退 出
9
若<vi，vj>是一条有向边，则称vi邻接到vj，vj邻 接于vi，并称有向边<vi，vj>关联于vi与vj，或称有向 边<vi，vj>与顶点vi和vj相关联。
三、度、入度、出度
在图中，一个顶点的度就是与该顶点相关联的 边的数目，顶点v的度记为D（v）。例如在图8.2 （a）所示的无向图G3中，各顶点的度均为3。 若G为有向图，则把以顶点v为终点的边的数目 称为顶点v的入度，记为ID（v）；把以顶点v为始 点的边的数目称为v的出度，记为OD（v），有向 图中顶点的度数等于顶点的入度与出度之和，即D （v）=ID（v）+OD（v）。
首 页 上一页 下一页 返 回 退 出
19
图的基本操作如下： （1）Creat（n） 创建一个具有n个顶点，没 有边的图； （2）Exist（i，j） 如果存在边（i，j）则返回1， 否则返回0； （3）Edges（） 返回图中边的数目； （4）Vertices（） 返回图中顶点的数目； （5）Add（i，j） 向图中添加边（i，j）； （6）Delete（i，j） 删除边（i，j）； （7）Degree（i） 返回顶点i的度； （8）InDegree（i） 返回顶点i的入度； （9）OutDegree（i） 返回顶点i的出度； } ADT Graph
首 页
上一页
下一页
返 回
退 出
11
子图示例
v1 v2 v4 v2 v4 v3 v2 v1 v3
v4
（a）无向图G3的部分子图 v1 v2 v4 v4 （b）有向图G4的部分子图
首 页 上一页 下一页 返 回 退 出
12
v3
v1 v2
v1 v3 v4
五、路径
无向图G中若存在着一个顶点序列v、v1’、v2’、…、 vm’、u，且（v，v1’）、（v1’，v2’）、…、（vm’，u） 均属于E（G），则称该顶点序列为顶点v到顶点u的 一条路径，相应地，顶点序列u、vm’、vm-1’、…、v1’、 v是顶点u到顶点v的一条路径。 如果G是有向图，路径也是有向的，它由E（G） 中的有向边<v，v1’>、<v1’，v2’>、…、<vm’，u>组 成。路径长度是该路径上边或弧的数目。
V0 34 V2 V0 64 V1 45 50 V2
56
V1
首 页
78
25
V3
上一页 下一页