启迪管理课程1
9.1 图的基本概念
9.2 图的存储结构
9.3 图的遍历
9.4 生成树和最小生成树
9.5 最短路径第九章 图启迪管理课程2
9.1 图的基本概念 －－图的定义
图 (G)的定义,由顶点（ Vertex)或结点
（ Node)的一个非空有限集和一个边
（ edge)或弧（ Arc)的有限集组成。
是否存在“空图”？
顶点,图中的数据元素，用 V表示顶点的有限非空集
边,两顶点之间的关系，用 E表示边的有限集
有向图,图 G中的每条边都是有方向的，
则称图为有向图。否则称为无向图。
V1 V2
V3 V4
G1
V1 V2
V4 V5
V3
G2
启迪管理课程3
在 有向图 中，一条边是由两个顶点组成的有序对，用 尖括号 表示，如 G1中的 <v1,v2>。
这样的边又称为弧,v1为弧的起点，称为弧尾（ Tail)； v2为弧的终点，称为弧头 (Head)。
则图 G1可表示为,G1=(V1,E1)
其中,V1={v1,v2,v3,v4}
E1={<v1,v2>,<v1,v3>,<v3,v4>,<v4,v1>}
v1 v2
v3 v4
G1
9.1 图的基本概念 －－图的定义注,<x,y>表示从 x到 y的一条弧 (arc),x为弧尾 (tail)，
y为弧头 (head).
启迪管理课程4
v1 v2
v4 v5
v3
G2
而在 无向图 中，一条边是由两个顶点的无序对组成，
用 圆括号 表示,如 G2中的 (V1,V2)。
图 G2可表示为,G2=(V2,E2)
其中,V2={v1,v2,v3,v4,v5}
E2={(v1,v2),(v1,v4),(v2,v3),(v2,v5),(v3,v4),(v3,v5)}
9.1 图的基本概念 －－图的定义注,(x,y)表示从 x到 y之间的一条连线，称为边
(edge).
启迪管理课程5
假设 <vi,vj>∈ E,(1)则 i≠j,即无顶点到自身的弧 ;(2)
两顶点间没有多条边的情况
有向完全图,有向图中的每两个顶点之间都存在着方向相反的两条边,
无向完全图,无向图中的每两个顶点之间都存在着一条边。
2
1 3
2
1 3
有向完全图 无向完全图有 n个顶点的有向完全图有 边有 n个顶点的无向完全图有 边n(n-1)/2
n(n-1)
9.1 图的基本概念 －－图的基本术语
完全图当一个图接近完全图时，则称为 稠密图 。相反，当一个图含有较少的边数 (即当 e<<n(n-1))时，则称为 稀疏图 。
稠密图、稀疏图启迪管理课程6
9.1 图的基本概念 －－图的基本术语
端点、邻接点；顶点的度、入度和出度对于无向图 G=(V,E),
端点、邻接点,若存在边（ vi,vj）
∈ E,则称 vi和 vj为该边的两个 端点,
并称他们互为 邻接点 。
边 （ vi,vj)则依附于顶点 vi和 vj,或者说
（ vi,vj) 和顶点 vi和 vj 相关联。
顶点的度,和顶点相关联的边的数目，
记为 d(V) 。
v1 v2
v4 v5
v3
G1
启迪管理课程7
9.1 图的基本概念 －－图的基本术语对于有向图 G=(V,A)，如果弧 <v,v’>∈ A，
则称顶点 v邻接到顶点 v’，顶点 v’邻接自 v。
入度,以顶点 v为弧头的弧 的数目，记为
id(v)。
出度,以顶点 v为弧尾的弧的数目，记为
od(v)。
顶点的度 d=入度 id+出度 od
图的边与顶点的度的关系：
v1 v2
v3 v4
G1
n
i
ivde
1
)(
2
1
启迪管理课程8
9.1 图的基本概念 －－图的基本术语
权和网
子图
权（ weight),与图的边或弧相关的数 称之为 权
网（ Nerwork）,带权的图 v1
v2 v3
5 1
2?子图（ Subgraph),假设有两个图 G=(V,E)和
G’=(V’,E’),如果 V’?V,E’?E，则称 G’为 G的子图。
3
5
6
2 4 5
1 3 6
2
1
2 4
(a) (b) (c)G
启迪管理课程9
9.1 图的基本概念 －－图的基本术语
路径和路径长度
路径,在无向图中，若存在一个顶点序列 (vi,vi,0,
vi,1,vi,2,…,v i,m,vj ),其中 (vi,j-1,vi,j)∈ E,1≤j≤m,则称顶点 v到 v’存在一条路径。如果 G是有向图，则路径也是有向的，顶点序列应满足 <vi,j-1,vi,j>∈ E,1≤j≤m 。
路径长度,路径上的边或弧的数目。
v1 v2
v4 v5
v3
G2
v1 v2
v3 v4
G1
启迪管理课程10
9.1 图的基本概念 －－图的基本术语
回路或环
回路（环）,第一个顶点和最后一个顶点相同的路径。
简单路径,若一条路径上除开始点和结束点可以相同外，其余顶点均不相同，
则称此路径为简单路径。
简单回路（环）,除了第一个顶点和最后一个顶点之外，其余顶点不重复出现的回路。
v1 v2
v4 v5
v3
G2
v1 v2
v3 v4
G1
启迪管理课程11
9.1 图的基本概念 －－图的基本术语
连通、连通图和连通分量在无向图中，如果从顶点 v到顶点 v′有 路径,则称 v和
v′是连通的。
连通图,任意两个顶点都是连通的图。
连通分量,无向图中的 极大 连通子图。
v1 v2
v4 v5
v3
G2
A B
L M
C
F
D E
HG
I J K
G3
顶点集极大启迪管理课程12
9.1 图的基本概念 －－图的基本术语
强连通图和强连通分量
强连通图,在有向图 G中，如果对于每一对 vi,vj∈ V,
vi≠vj，从 vi到 vj和从 vj到 vi都存在路径，则称 G是强连通图。
强连通分量,有向图中的极大强连通子图。
v1 v2
v3 v4
G1
3
5
6
启迪管理课程13
9.1 图的基本概念 －－图的基本术语例 9.1 有 n个顶点的有向强连通图最多需要多少条弧？
最少需要多 少条弧？ 这样的有向图是什么形状？
答：有 n个顶点的有向强连通图最多有 n(n-1)
条边 (构成一个有向完全图的情况 )；最少有 n条边
(n个顶点依次首尾相接构成一个环的情况 )。
启迪管理课程14
9.2.1数组表示法（邻接矩阵表示法）
9.2 图的存储结构 －－邻接矩阵表示法
邻接矩阵（ Adjacency Matrix):是表示顶点之间相邻关系的矩阵。设 G=(V,E)是具有 n个顶点的图，
则 G的邻接矩阵是具有如下性质的 n阶方阵：
中的边不是或若（，
中的边是或若（
E ( G ),v),0
E ( G ),v),,1]][[
jiji
jiji
vvv
vvvjiA
图的存储结构 除了要存储图中各个顶点本身的信息外，同时还要存储顶点与顶点之间的所有关系。常用的图的存储结构有 邻接矩阵,邻接表,十字邻接表和邻接多重表。
启迪管理课程15
9.2 图的存储结构 －－邻接矩阵表示法
v0 v1
v3 v4
v2
G2
对称矩阵
00110
00101
11010
10101
01010
2G
A
0 1 2 3 4
0
1
2
3
4
无向图中顶点 Vi的度 d(Vi)=邻接矩阵 A中第 i行 /列 元素之和第 i行 /列元素的值：表示顶点 Vi与图中所有顶点是否存在边的关系，有则相应位置上的值为 1，否则为 0。
启迪管理课程16
9.2 图的存储结构 －－邻接矩阵表示法
v0 v1
v2 v3
G1
A中第 i行元素之和
A中第 i列元素之和
0 1 2 3
0001
1000
0000
0110
1GA
0
1
2
3
有向图中：顶点 Vi的出度 =,
顶点 Vi的入度 =,
第 i行元素的值,表示是否有从顶点 vi出发到图中其他顶点的弧
（即以 vi为尾的弧），若有则相应位置上的值为 1，否则为 0；
第 i列元素的值,表示是否有从图中其他顶点出发到顶点 vi的弧
（即以 vi为头的弧），若有则相应位置上的值为 1，否则为 0。
启迪管理课程17
9.2 图的存储结构 －－邻接矩阵表示法网的邻接矩阵定义为：
V0 V1
V5 V
2
V4
V3
5
48
7 5
5
1
3
N
13
5
5
8
4
75
N
A 0 1 2 3 4 5
0
1
2
3
4
5
反之或若 VRvvvvwjiA jijiji,),(]][[,
其他或若
ji
jijiji
vv
VRvvvvw
jiA 0
,),(
]][[
,或启迪管理课程18
9.2 图的存储结构 －－邻接矩阵表示法
邻接矩阵的特点如下：
(1) 图的邻接矩阵表示是惟一的。
(2) 无向图的邻接矩阵一定是一个对称矩阵。因此,
按照压缩存储的思想,在具体存放邻接矩阵时只需存放上 (或下 )三角形阵的元素即可
(3) 不带权的有向图的邻接矩阵一般来说是一个稀疏矩阵,因此,当图的顶点较多时,可以采用三元组表的方法存储邻接矩阵。
(4) 对于无向图,邻接矩阵的第 i行 (或第 i列 )非零元素 (或非 ∞元素 )的个数正好是第 i个顶点 vi的度。
启迪管理课程19
9.2 图的存储结构 －－邻接矩阵表示法
邻接矩阵的特点如下：
(5) 对于有向图,邻接矩阵的第 i行 (或第 i列 )非零元素 (或非 ∞元素 )的个数正好是第 i个顶点 vi的出度 (或入度 )。
(6) 用邻接矩阵方法存储图,很容易确定图中任意两个顶点之间是否有边相连 。 但是,要确定图中有多少条边,则必须按行,按列对每个元素进行检测,所花费的时间代价很大 。 这是用邻接矩阵存储图的局限性 。
启迪管理课程20
9.2 图的存储结构 －－邻接矩阵表示法
数组表示法的存储结构描述：
#define MAXV <最大顶点个数 >
#define INFINITY INT_MAX //最大值 ∞
typedef struct
{ int no; /*顶点编号 */
InfoType info; /*顶点其他信息 */
} VertexType; /*顶点类型 */
启迪管理课程21
9.2 图的存储结构 －－邻接矩阵表示法
typedef struct /*图的定义 */
{ int edges[MAXV][MAXV]; /*邻接矩阵 */
int n,e; /*顶点数,弧数 */
VertexType vexs[MAXV]; /*存放顶点信息 */
} MGraph;
启迪管理课程22
9.2 图的存储结构 －－邻接矩阵表示法
typedef struct
{ int edges[MAXV][MAXV];
int n,e;
VertexType vexs[MAXV];
} MGraph;
MGraph G2;
邻接矩阵的下标要与顶点的下标对应
a b
d e
c
G2
G2.n=5;
G2.e=6;
G2.vexs=
[{0,a},{1,b},{2,c},{3,d},{4,e}];
00110
00101
11010
10101
01010
.2 e dge sG
a b c d e
a
b
c
d
e
建立无向网络邻接矩阵的算法 (补充 ）
void CREATGRAPH(MGraph *&G,int n,int e)
{int i,j,k;
float w;
G->n=n; //顶点数
G->e=e; //边数
for(i=0;i<n;i++)
{ G->vexs[i].no=i; G->vexs[i],Info=getchar( );}
for(i=0;i<n;i++)
for(j=0;j<n;j++)
G->edges[i][j]=INFINITY;
for(k=0,k<e;k++)
{scanf(“%d,%d,%f”,&i,&j,&w);
G->edges[i][j]=w;
G->edges[j][i]=w;
}
}
a b
d e
c
G2
2
1 4
5
9 6
启迪管理课程24
advex nextarc info data firstarc
表结点 表头结点图的邻接表存储方法是一种顺序与链式存储结构相结合的存储方法。在邻接表中,对图中每个顶点建立一个单链表,单链表中的第 i个结点表示依附于顶点 vi的边,对有向图是以顶点 vi为尾的弧
(出边 )。每个单链表上附设一个表头结点。表结点和表头结点的结构如下：
表结点采用链存储结构 表头结点采用顺序存储结构
9.2 图的存储结构 －－邻接表启迪管理课程25
表结点的三个域,
adjvex 是个整形变量,指示与顶点 vi邻接的点在图中的位置 ;
nextarc 是指针型变量,指向下一条边或弧的结点 ;
Info存储与边或弧相关的信息,如权值等 ;
表头结点的两个域,
data 存储顶点 vi的名称或其他信息 ;
firstarc指向链表中第一个结点。
advex nextarc info data firstarc
表结点 表头结点
9.2 图的存储结构 －－邻接表启迪管理课程26
1
2 3 0
4
10
1
2
3
4
3 4v0
v1
v2
v3
v4
表头结点 表结点
∧
0 2 3 ∧
1 3 4 ∧
0 1 2 4 ∧
0 2 3 ∧无向图 G1
无向图 G1的邻接表无向图的邻接表示意图
9.2 图的存储结构 －－邻接表边数 × 2边结点的个数 =
顶点 i的度 = 第 i个链表中的表结点个数启迪管理课程27
10
1
2
3
4
3v0
v1
v2
v3
v4
表头结点 表结点
∧
2 3 ∧
3 4 ∧
∧
0 3 ∧
有向图 G2
有向图 G2的邻接表
1
2 3 0
4
有向图的邻接表示意图
9.2 图的存储结构 －－邻接表表结点的个数 =
结点 vi的出度：,
结点 vi的入度,.
第 i个链表中的结点个数遍历整个邻接表，查找表结点中 adjvex等于 vi位置的所有结点。
边的条数启迪管理课程28
0
1
2
3
4
v0
v1
v2
v3
v4
表头结点 表结点带权有向图 G3
带权有向图 G3的邻接表
1
0 2
3
4
38 6
5 9
1 8 3 5 ∧
2 3 ∧
4 6 ∧
2 9 ∧
∧
9.2 图的存储结构 －－邻接表启迪管理课程29
9.2 图的存储结构 －－邻接表
40
1
2
3
4
v0
v1
v2
v3
v4
表头结点 表结点
∧
0 ∧
1 ∧
有向图 G2
有向图 G2的 逆 邻接表
1
2 3 0
4 0 1 2 4 ∧
2 ∧
表结点的个数 =
结点 vi的入度：,
结点 vi的出度,.
第 i个链表中的结点个数遍历整个逆邻接表，查找表结点中 adjvex等于 vi位置的所有结点。
边的条数启迪管理课程30
邻接表的特点如下：
(1) 邻接表表示不惟一 。 这是因为在每个顶点对应的单链表中,各边结点的链接次序可以是任意的,取决于建立邻接表的算法以及边的输入次序 。
(2) 对于有 n个顶点和 e条边的无向图,其邻接表有 n
个顶点结点和 2e个边结点 。 显然,在总的边数小于 n(n-
1)/2的情况下,邻接表比邻接矩阵要节省空间 。
(3) 对于无向图,邻接表的顶点 vi对应的第 i个链表的边结点数目正好是顶点 vi的度 。
(4) 对于有向图,邻接表的顶点 vi对应的第 i个链表的边结点数目仅仅是 vi的 出度 。 其入度为邻接表中所有
adjvex域值为 i的边结点数目 。
启迪管理课程31
9.2 图的存储结构 －－邻接表邻接表的类型说明
typedef struct ANode /*弧的结点结构类型 */{ int adjvex;
/*该弧的依附的另一顶点的下标 */struct ANode *nextarc;
/*指向下一条弧的指针 */InfoType info;
/*该弧的相关信息 */
} ArcNode;
firstarcdata
adjvex info nextarc
typedef struct Vnode /*邻接表头结点的类型 */
{ Vertex data; /*顶点信息 */
ArcNode *firstarc; /*指向第一条弧 */
} VNode;
typedef VNode AdjList[MAXV];//AdjList是邻接表类型
typedef struct
{ AdjList adjlist; /*邻接表 */
int n,e; /*图中顶点数 n和边数 e*/
} ALGraph; /*图的类型 */
typedef 还可以掩饰符合类型，如指针和数组。例如，
你不用象下面这样重复定义有 100个字符元素的数组：
char line[100]; char text[100];
定义一个 typedef，每当要用到相同类型和大小的数组时，可以这样：
typedef char Line[100]; Line line,text;
void CREATADJLIST(ALGraph *&ga,int n,int e)
{int i,j,k;
ArcNode *s;
ga->n=n; ga->e=e;
for(i=0;i<n;i++)
{ga->adjlist[i].data=getchar( );
ga->adjlist[i].firstarc=NULL;
}
for(k=0;k<e;k++)
{scanf("\n%d,%d",&i,&j);
s=(ArcNode *)malloc(sizeof(ArcNode));
s->adjvex=j; s->nexarc=ga->adjlist[i].firstarc;
ga->adjlist[i].firstarc=s;
s=(ArcNode *)malloc(sizeof(ArcNode));
s->adjvex=i; s->nextarc=ga->adjlist[j].firstarc;
ga->adjlist[j].firstarc=s;
}
}
A
DC
B
^D
^C
^B
^A0
1
2
3
生成邻接表的算法（无向图）
void CREATADJLIST(ALGraph *&ga,int n,int e)
{int i,j,k;
ArcNode *s;
ga.n=n; ga.e=e;
for(i=0;i<n;i++)
{ga->adjlist[i].data=getchat( );
ga->adjlist[i].firstarc=NULL;
}
for(k=0;k<e;k++)
{scanf("\n%d,%d",&i,&j);
s=(ArcNode *)malloc(sizeof(ArcNode));
s->adjvex=j; s->nexarc=ga->adjlist[i].firstarc;
ga->adjlist[i].firstarc=s;
s=(ArcNode *)malloc(sizeof(ArcNode));
s->adjvex=i; s->nextarc=ga->adjlist[j].firstarc;
ga->adjlist[j].firstarc=s;
}
}
A
DC
B
//0,1
^D
^C
^B
^A0
1
2
3
^1
s
^0
s
void CREATADJLIST(ALGraph *&ga,int n,int e)
{int i,j,k;
ArcNode *s;
ga.n=n; ga.e=e;
for(i=0;i<n;i++)
{ga->adjlist[i].data=getchat( );
ga->adjlist[i].firstarc=NULL;
}
for(k=0;k<e;k++)
{scanf("\n%d,%d",&i,&j);
s=(ArcNode *)malloc(sizeof(ArcNode));
s->adjvex=j; s->nexarc=ga->adjlist[i].firstarc;
ga->adjlist[i].firstarc=s;
s=(ArcNode *)malloc(sizeof(ArcNode));
s->adjvex=i; s->nextarc=ga->adjlist[j].firstarc;
ga->adjlist[j].firstarc=s;
}
}
A
DC
B
^D
^C
B
A0
1
2
3
^1
^0
//0,2
2
s
^0
s
启迪管理课程35
9.2 图的存储结构 －－十字邻接表和多重邻接表
十字邻接表是对有向图而言的，实际上是邻接表和逆邻接表的结合。
在无向图的邻接表存储方法中，每条边 (vi,vj)用两个表结点表示。这给图的某些操作带来不便。
邻接多重表用于存储无向图。
十字邻接表多重邻接表启迪管理课程36
图的遍历,从图中某一顶点出发访遍图中其余顶点，
且使每一个顶点仅被访问一次。 v
1 v2
v4 v5
v3
G2
在图的遍历过程中，需设置一个辅助数组 visited[n]记录每个顶点是否已被访问过，它的初值为 0，表示未被访问过，在访问了顶点之后便将相应的值置为 1。
图的两种遍历方法,深度优先搜索法广度优先搜索法
9.3 图的遍历 －－图的遍历的概念启迪管理课程37
9.3 图的遍历 －－深度优先搜索遍历
搜索规则,从图中指定顶点 v出发，先访问 v，然后依次从该顶点未被访问过的邻接顶点出发进行深度优先搜索，
直到图中与 v相通的所有顶点都被访问过。
V1
V2 V3
V4 V5
V8
V6 V7
V1
V2
V4
V8
V5
V3
V6
V7
遍历序列,v1,v2,v4,v8,v5,v3,v6,v7
9.3.2 深度优先搜索深度优先搜索生成树深度优先遍历的实现 (邻接矩阵）
v0 v1
v2 v3
0001
1000
0000
0110
1G
A
设从第 1个顶点出发，请给出访问的序列及过程。
// 算法中使用的全局变量
int visited[n];
MGraph g; //图的邻接矩阵
DFSM( int i)
{int j;
printf(“node:%c\n”,g.vexs[i].info);
visited[i]=1;
for(j=0;j<n;j++)
if(g.edges[i][j]==1)&&(!visited[j]))
DFSM(j);
}
深度优先遍历的实现（邻接表）
int visited[n]={0};
void DFS(ALGraph *G,int v)
{ ArcNode *p;
visited[v]=1;
printf("%d ",v);
p=G->adjlist[v].firstarc;
while (p!=NULL)
{ if (visited[p->adjvex]==0)
DFS(G,p->adjvex);
p=p->nextarc;
}
}
1
3 0 2
4
0
1
2
3
4
1
0
1
0
0
3
2
3
1
2
4 ∧
3 ∧
4 ∧
2
3 ∧
4 ∧
v 0
v 1
v 2
v 3
v 4
V=2 0
1
2
3
4
0
0
0
0
0
visited[n]
1
输出序列,2
p
V=1 1
1
p
V=0
1
0
p p
V=3
1
3
p p p p
V=4
1
4
p p p p
p
p p
p p p
p p p
启迪管理课程40
9.3 图的遍历 －－广度优先搜索遍历
9.3.3 广度优先搜索搜索规则,首先访问初始点 v，接着访问 v的所有未被访问过的邻接点 v1,v2,…,v t,然后在按照 v1,v2,…,v t的次序，
访问每一个顶点的所有未被访问过的邻接点，依次类推，
直到图中所有和初始点 v有路径相通的顶点都没访问过为止。
V1
V2 V3
V4 V5
V8
V6 V7
V1
V2 V3
V4 V
5 V6
V7
V8 v1 v2 v3 v4 v5 v6 v7 v8
广度优先搜索生成树启迪管理课程41
9.3 图的遍历 －－广度优先搜索遍历特点,广度优先搜索遍历图的过程是以 v为起点，由近至远，依次访问和 v有路径相通且路径长度分别为 1，
2,… 的顶点，即相当于按层次遍历。
V1
V2 V3
V4 V5
V8
V6 V7
V1
V2 V3
V4 V5 V6 V7
V8 v1 v2 v3 v4 v5 v6 v7 v8
启迪管理课程42
9.3 图的遍历 －－广度优先搜索遍历
算法的实现：
①设置 visited[ vexnum]
② 需附设一个队列以实现层次遍历。
广度优先遍历算法 V1
V2 V3
V4 V5
V8
V6 V7
遍历过程：
(1)开始时将队列置空,visited置为 0；
(2)在每访问一个顶点 v时,要将其入队,且 vistied[v]=1.
(3)队头元素出队，依次访问其未被访问过的邻接点。
(4)重复 (2)(3)的步骤，直至队列为空，此时说明每一个访问过的顶点的所有邻接点均已被访问，本次遍历完毕。
v0 v1
v2 v3
0001
1000
0000
0110
1G
A
BFSM(int k) //k=0
//广度优先遍历以邻接矩阵存储的图 g
{ int i,j;
InitQueue(Q); //置空队列
print("%c\n",g.vexs[k]);
visited[k]=1;
EnQueue(Q,k);
while(!QueueEmpty(Q))
{i=DeQueue(Q);
for(j=0;j<n;j++)
if(g.edges[i][j]==1)&&(!visited[j])
{printf("%c\n",g.vexs[j]);
visited[j]=1;
EnQueue(Q,j);
}
}
}
头 尾
0
visited[ ]={0,0,0,0};1
//i=0
1 2
1 1
v0 v1
//i=1
v2
//i=2
v3
1
3
//i=3
void BFS(ALGraph *G,int v)
{ ArcNode *p; int w,i;
int queue[MAXV],front=0,rear=0; /*定义循环队列 */
int visited[MAXV]; /*定义存放结点的访问标志的数组 */
for (i=0;i<G->n;i++) visited[i]=0; /*访问标志数组初始化 */
printf("%2d",v); /*输出被访问顶点的编号 */
visited[v]=1; /*置已访问标记 */
rear=(rear+1)%MAXV;
queue[rear]=v; /*v进队 */
1 23
40
0
1
2
3
4
0
0
0
0
0
visited[n]
V=2
1
2输出序列：
2
while (front!=rear) /*若队列不空时循环 */
{ front=(front+1)%MAXV;
w=queue[front]; /*出队并赋给 w*/
p=G->adjlist[w].firstarc; /*找 w的第一个的邻接点 */
while (p!=NULL)
{ if (visited[p->adjvex]==0)
{ printf(“%2d”,p->adjvex); /*访问之 */
visited[p->adjvex]=1;
rear=(rear+1)%MAXV;/*该顶点进队 */
queue[rear]=p->adjvex;
}
p=p->nextarc; /*找下一个邻接顶点 */
}
}
printf("\n");
}
0
1
2
3
4
1
0
1
0
0
3
2
3
1
2
4 ∧
3 ∧
4 ∧
2
3 ∧
4 ∧
v 0
v 1
v 2
v 3
v 4
1 23
40
0
1
2
3
4
0
0
0
0
0
visited[n]
1
2输出序列：
2
p
W=2
1
1
1
p
3
1
3
p
4
1
4 p
W=1
p
0
1
0
1
3 0 2
4
启迪管理课程46
9.3 图的遍历 －－非连通图的遍历非连通图的遍历 (深度优先）
V1
V2
V4
V3
V5
A
DC
B
从图中指定顶点 v出发，先访问 v，然后依次从该顶点未被访问过的邻接顶点出发进行深度优先搜索，直到图中与 v相通的所有顶点都被访问过。 如果图中尚有未被访问过的顶点，则从另一个未被访问过的顶点出发重复上述过程，直到图中所有顶点都被访问过。
启迪管理课程47
9.3 图的遍历 －－非连通图的遍历
DFS1(ALGraph *g)
{
int i;
for (i=0;i<g->n;i+)
if (visited[i]==0)
DFS(g,i);
}
BFS1(ALGraph *g)
{
int i;
for (i=0;i<g->n;i+)
if (visited[i]==0)
BFS(g,i);
}
启迪管理课程48
9.4 生成树和最小生成树 －－生成树的概念
9.4.1 生成树的概念生成树是一个具有 n个顶点的连通图的一个极小连通子图,它含有图中全部顶点,但只有构成一棵树的 (n-1)条边。
极小连通子图,若删除极小连通子图的任意一条边,
该图就成为非连通图。
无向连通图 G
0
1 2
3 4
0
1 2
3 4
0
1 2
3 4
图 G的二颗生成树启迪管理课程49
9.4 生成树和最小生成树 －－生成树的概念一个连通图可以有多个生成树,即生成树不是唯一的。
最小生成树的定义：
一个带权连通图的所有生成树中具有边上的权值之和最小的树称为最小生成树。
生成树的特点：
(1) 一颗有 n个顶点的生成树有且仅有 n-1条边；
(2)生成树是个无任何回路的连通图；
(3)如果在生成树上添加一条边,必定构成一个环
(4)如果在生成树中删除一条边,则变为非连通图。
启迪管理课程50
9.4 生成树和最小生成树 －－生成树的概念对于一个具有 n个顶点的连通图 G，构造它的生成树的准则为：
(1) 必须使用图 G中的边来构造；
(2)必须使用且仅使用图 G中的 n-1条边来连接 n个顶点；
(3)不能使用生产回路的边；
说明：具有 n个顶点,n-1条边的图并不一定是生成树！只有那些符合定义的才是生成树。
如何构造生成树？
启迪管理课程51
9.4 生成树和最小生成树 －无向图的连通分量和生成树
9.4.2 无向图的连通分量和生成树
对于连通图，连通分量就是图本身，故只需调用遍历过程一次即可。
本节要解决的问题是：如何构造一个无向连通图的生成树？
实际上,对一个具有 n个顶点的无向连通图 G进行遍历 (深度优先或广度优先 )一次所得到的顶点集合及相关边的集合就构成图 G的一个极小连通子图，即图 G的一颗生成树。
看一个例子启迪管理课程52
无向连通图 G
0
1 2
3 4
10
1
2
3
4
3v0
v1
v2
v3
v4
∧
0 2 3 ∧
1 3 4 ∧
0 1 2 4 ∧
2 3 ∧
图 G的邻接表图 G的生成树
0
1 2
3 4
图 G的深度优先生成树深度优先遍历启迪管理课程53
9.4 生成树和最小生成树 －无向图的连通分量和生成树
对于非连通图，每个连通分量中的顶点集和遍历此连通分量过程中经过的边一起构成一棵生成树，这些连通分量的生成树组成非连通图的生成森林。
说明
一个图可以有许多棵不同的生成树（起点、次序）
所有生成树具有以下共同特点：
生成树的结点个数与图的顶点个数相同
生成树是图的极小连通子图
一个有 n个顶点的连通图的生成树有 n-1条边
生成树中任意两个结点间的路径是唯一的
在生成树中再加一条边必然形成回路
含 n个顶点 n-1条边的图不一定是生成树一旦确定了存储结构、起点以及遍历方法，那么图的生成树将惟一确定。
启迪管理课程54
9.4 生成树和最小生成树 －无向图的连通分量和生成树问题：假设要在 n个城市之间建立通讯联络网，则连通
n个城市只需修建 n-1条线路,如何在最节省经费的前提下建立这个通讯网？
最小生成树边 max=n(n-1)/2
边 min=n-1
问题转化,该问题等价于构造网的一棵最少生成树，即 e条带权的边中选取 n-1条 (不构成回路 )，
使,权值之和,为最小。
a
b
c
d
4
2
3
f
g
h
e9
7 3
25
4 6
5
5
5 6
权值之和,4+5+5+4+5+6+7=36
权值之和,2+3+5+4+5+2+5=22
启迪管理课程56
9.4 生成树和最小生成树 －普里姆算法
算法思想,G=(V,E)是连通无向网络,T=(U,TE)是 G
的最小生成树,其中 U是 T的顶点集,TE是 T的边集 。
(1)初始化 U={v0}。 v0到其他顶点的所有边为候选边；
(2)重复以下步骤 n-1次,使得其他 n-1个顶点被加入到 U
中
① 从候选边中挑选权值最小的边输出,设该边在 V-U
中的顶点是 v,将 v加入 U中；
② 考察当前 V-U中的所有顶点 vi,修改候选边：若
(v,vi)的权值小于原来和 vi关联的候选边,则用 (v,vi)取代后者作为候选边。
普里姆 (Prim)算法
u0
U
u1
V-U
u2
ui uk
un
假设当前生成树 T中有 k个顶点，则当前连接 U和 V-U
的边有 k(n-k)条。 （如果两顶点间无边，则虚拟其存在一条无穷大的边）
另设一数组 closest[n]:数组中的各分量表示 U中到 V-U的各顶点距离最近的顶点。
Prim算法的关键,如何 有效地 找到连接 U和 V-U的最短边来扩充生成树 T。
方法,构造候选边集 (即辅助数组 lowcost[n]），且保证两个集合间的最短边属于候选边集。
6 5
1 75
3 6
6
4 2
V0
V1 V3
V2
V4 V5
v1
v2
v3
v4
v5
v0
U V-U
0624
6063
2075
467051
3506
5160
di s t
lowcost[ ]={6,0,5,∞,3,∞};
closest[ ]={1,1,1,1,1,1};
0 6
4
01
2
7
2
4
2
0 5
0
02
5
0
closest[i]存储该边依附在 U中的顶点启迪管理课程59
Prim算法的语言描述
（ 1）置 T为任意一个顶点，初始化候选边集 lowcost
和 closest；
（ 2） while(T中顶点数目 <n）
（ 3） {从候选边集中选取最短的边（ u,v）；
（ 4） 将 (u,v）及顶点 v扩充到 T中；
（ 5） 调整 lowcost和 closest；
}
9.4 生成树和最小生成树 －普里姆算法启迪管理课程60
9.4 生成树和最小生成树 －克鲁斯卡尔算法克鲁斯卡尔 (Kruskal)算法
算法思想,设连通网 N=(V,E),令最小生成树,
初始状态为只有 n个顶点而无边的非连通图 T=(V,?)，
每个顶点自成一个连通分量
在 E中选取代价最小的边,若该边依附的顶点落在 T中不同的连通分量上，则将此边加入到 T中；否则，舍去此边，选取下一条代价最小的边
依此类推，直至 T中所有顶点都在同一连通分量上为止启迪管理课程61
9.4 生成树和最小生成树 －克鲁斯卡尔算法克鲁斯卡尔 (Kruskal)算法例 1
65
4
3
2
6 5
1
3
5
6
6
4 2
5
1
65
4
3
2 1
23 4
5
5
5
1
1
3
2
4
6
3
2
5
4
3
6
5
1
4
5
3
4
5
2
3
6
1
2
6
3
5
6
5
6
权值邻接点邻接点启迪管理课程62
9.5 最短路径 －路径的概念
9.5 最短路径
问题提出用带权的有向图表示一个交通运输网，图中：
顶点 —— 表示城市边 —— 表示城市间的交通联系权 —— 表示此线路的长度或沿此线路运输所花的时间或费用等,
问题：从某顶点出发,沿图的边到达另一顶点所经过的路径中，各边上权值之和最小的一条路径 —— 最短路径求图的最短路径分以下两方面：求图中某一顶点到其余各顶点的最短路径和求图中每一对顶点之间的最短路径。
启迪管理课程63
9.5 最短路径
9.5.2 从一个顶点到其余各顶点的最短路径单源最短路径,对于给定的有向网络 G=(V,E)及单个源点 v,求从 v到 G的其余个顶点的最短路径。
算法的基本思想,按最短路径长度的递增次序依次求得各条路径。
狄克斯特拉（ Dijkstra)算法启迪管理课程64
9.5 最短路径假设图中所示为从源点到其余各点之间的最短路径，则在这些路径中，必然存在 一条长度 最短者。
源点 a b
c
…
在这条路径上，必定只含有一条 (权值最小 )弧，由此，
只要在所有从源点出发的弧中查找权值最小者；
长度次短的路径 可能有两种情况,
它可能是从源点直接到该点的路径。
也可能是：从源点到 c，再从 c到该点的路径之和。
其余依次类推。
启迪管理课程65
1 4
0 2 6
3 5
8
1
6 6
4
2
5
6
6
1
4
7
终点
dist
路径
1 2 3 4 5 6
disk[k]表示当前所求得的从源点到顶点
k的最短路径长度。一般情况下，
disk[k]=源点到顶点 k的弧上的权值或者＝源点到 其他顶点 的路径长度 +
其它顶点 到顶点 k弧上的权值
4
0,1
6
0,2
6
0,3
∞ ∞ ∞5
0,1,2
11
0,1,4
9
0,1,2,5
17
0,1,2,5,6
10 16
0,1,2,5,4 0,1,2,5,4,6
求顶点 0到其余各顶点的最短路径启迪管理课程66
9.5 最短路径
9.5.3 每一对顶点之间的最短路径
方法一,每次以一个顶点为源点，重复执行
Dijkstra算法 n次 ——T(n)=O(n3)
for(i=0;i<n;i++)
Dijkstra(cost,n,i);
方法二,弗洛伊德 (Floyd)算法 (不讲）
启迪管理课程67
本 章 小 结：
图的相关概念
图的存储结构邻接矩阵邻接表
图的遍历深度优先搜索广度优先搜索
图的最小生成树及应用
最短路径
9.1 图的基本概念
9.2 图的存储结构
9.3 图的遍历
9.4 生成树和最小生成树
9.5 最短路径第九章 图启迪管理课程2
9.1 图的基本概念 －－图的定义
图 (G)的定义,由顶点（ Vertex)或结点
（ Node)的一个非空有限集和一个边
（ edge)或弧（ Arc)的有限集组成。
是否存在“空图”？
顶点,图中的数据元素，用 V表示顶点的有限非空集
边,两顶点之间的关系，用 E表示边的有限集
有向图,图 G中的每条边都是有方向的，
则称图为有向图。否则称为无向图。
V1 V2
V3 V4
G1
V1 V2
V4 V5
V3
G2
启迪管理课程3
在 有向图 中，一条边是由两个顶点组成的有序对，用 尖括号 表示，如 G1中的 <v1,v2>。
这样的边又称为弧,v1为弧的起点，称为弧尾（ Tail)； v2为弧的终点，称为弧头 (Head)。
则图 G1可表示为,G1=(V1,E1)
其中,V1={v1,v2,v3,v4}
E1={<v1,v2>,<v1,v3>,<v3,v4>,<v4,v1>}
v1 v2
v3 v4
G1
9.1 图的基本概念 －－图的定义注,<x,y>表示从 x到 y的一条弧 (arc),x为弧尾 (tail)，
y为弧头 (head).
启迪管理课程4
v1 v2
v4 v5
v3
G2
而在 无向图 中，一条边是由两个顶点的无序对组成，
用 圆括号 表示,如 G2中的 (V1,V2)。
图 G2可表示为,G2=(V2,E2)
其中,V2={v1,v2,v3,v4,v5}
E2={(v1,v2),(v1,v4),(v2,v3),(v2,v5),(v3,v4),(v3,v5)}
9.1 图的基本概念 －－图的定义注,(x,y)表示从 x到 y之间的一条连线，称为边
(edge).
启迪管理课程5
假设 <vi,vj>∈ E,(1)则 i≠j,即无顶点到自身的弧 ;(2)
两顶点间没有多条边的情况
有向完全图,有向图中的每两个顶点之间都存在着方向相反的两条边,
无向完全图,无向图中的每两个顶点之间都存在着一条边。
2
1 3
2
1 3
有向完全图 无向完全图有 n个顶点的有向完全图有 边有 n个顶点的无向完全图有 边n(n-1)/2
n(n-1)
9.1 图的基本概念 －－图的基本术语
完全图当一个图接近完全图时，则称为 稠密图 。相反，当一个图含有较少的边数 (即当 e<<n(n-1))时，则称为 稀疏图 。
稠密图、稀疏图启迪管理课程6
9.1 图的基本概念 －－图的基本术语
端点、邻接点；顶点的度、入度和出度对于无向图 G=(V,E),
端点、邻接点,若存在边（ vi,vj）
∈ E,则称 vi和 vj为该边的两个 端点,
并称他们互为 邻接点 。
边 （ vi,vj)则依附于顶点 vi和 vj,或者说
（ vi,vj) 和顶点 vi和 vj 相关联。
顶点的度,和顶点相关联的边的数目，
记为 d(V) 。
v1 v2
v4 v5
v3
G1
启迪管理课程7
9.1 图的基本概念 －－图的基本术语对于有向图 G=(V,A)，如果弧 <v,v’>∈ A，
则称顶点 v邻接到顶点 v’，顶点 v’邻接自 v。
入度,以顶点 v为弧头的弧 的数目，记为
id(v)。
出度,以顶点 v为弧尾的弧的数目，记为
od(v)。
顶点的度 d=入度 id+出度 od
图的边与顶点的度的关系：
v1 v2
v3 v4
G1
n
i
ivde
1
)(
2
1
启迪管理课程8
9.1 图的基本概念 －－图的基本术语
权和网
子图
权（ weight),与图的边或弧相关的数 称之为 权
网（ Nerwork）,带权的图 v1
v2 v3
5 1
2?子图（ Subgraph),假设有两个图 G=(V,E)和
G’=(V’,E’),如果 V’?V,E’?E，则称 G’为 G的子图。
3
5
6
2 4 5
1 3 6
2
1
2 4
(a) (b) (c)G
启迪管理课程9
9.1 图的基本概念 －－图的基本术语
路径和路径长度
路径,在无向图中，若存在一个顶点序列 (vi,vi,0,
vi,1,vi,2,…,v i,m,vj ),其中 (vi,j-1,vi,j)∈ E,1≤j≤m,则称顶点 v到 v’存在一条路径。如果 G是有向图，则路径也是有向的，顶点序列应满足 <vi,j-1,vi,j>∈ E,1≤j≤m 。
路径长度,路径上的边或弧的数目。
v1 v2
v4 v5
v3
G2
v1 v2
v3 v4
G1
启迪管理课程10
9.1 图的基本概念 －－图的基本术语
回路或环
回路（环）,第一个顶点和最后一个顶点相同的路径。
简单路径,若一条路径上除开始点和结束点可以相同外，其余顶点均不相同，
则称此路径为简单路径。
简单回路（环）,除了第一个顶点和最后一个顶点之外，其余顶点不重复出现的回路。
v1 v2
v4 v5
v3
G2
v1 v2
v3 v4
G1
启迪管理课程11
9.1 图的基本概念 －－图的基本术语
连通、连通图和连通分量在无向图中，如果从顶点 v到顶点 v′有 路径,则称 v和
v′是连通的。
连通图,任意两个顶点都是连通的图。
连通分量,无向图中的 极大 连通子图。
v1 v2
v4 v5
v3
G2
A B
L M
C
F
D E
HG
I J K
G3
顶点集极大启迪管理课程12
9.1 图的基本概念 －－图的基本术语
强连通图和强连通分量
强连通图,在有向图 G中，如果对于每一对 vi,vj∈ V,
vi≠vj，从 vi到 vj和从 vj到 vi都存在路径，则称 G是强连通图。
强连通分量,有向图中的极大强连通子图。
v1 v2
v3 v4
G1
3
5
6
启迪管理课程13
9.1 图的基本概念 －－图的基本术语例 9.1 有 n个顶点的有向强连通图最多需要多少条弧？
最少需要多 少条弧？ 这样的有向图是什么形状？
答：有 n个顶点的有向强连通图最多有 n(n-1)
条边 (构成一个有向完全图的情况 )；最少有 n条边
(n个顶点依次首尾相接构成一个环的情况 )。
启迪管理课程14
9.2.1数组表示法（邻接矩阵表示法）
9.2 图的存储结构 －－邻接矩阵表示法
邻接矩阵（ Adjacency Matrix):是表示顶点之间相邻关系的矩阵。设 G=(V,E)是具有 n个顶点的图，
则 G的邻接矩阵是具有如下性质的 n阶方阵：
中的边不是或若（，
中的边是或若（
E ( G ),v),0
E ( G ),v),,1]][[
jiji
jiji
vvv
vvvjiA
图的存储结构 除了要存储图中各个顶点本身的信息外，同时还要存储顶点与顶点之间的所有关系。常用的图的存储结构有 邻接矩阵,邻接表,十字邻接表和邻接多重表。
启迪管理课程15
9.2 图的存储结构 －－邻接矩阵表示法
v0 v1
v3 v4
v2
G2
对称矩阵
00110
00101
11010
10101
01010
2G
A
0 1 2 3 4
0
1
2
3
4
无向图中顶点 Vi的度 d(Vi)=邻接矩阵 A中第 i行 /列 元素之和第 i行 /列元素的值：表示顶点 Vi与图中所有顶点是否存在边的关系，有则相应位置上的值为 1，否则为 0。
启迪管理课程16
9.2 图的存储结构 －－邻接矩阵表示法
v0 v1
v2 v3
G1
A中第 i行元素之和
A中第 i列元素之和
0 1 2 3
0001
1000
0000
0110
1GA
0
1
2
3
有向图中：顶点 Vi的出度 =,
顶点 Vi的入度 =,
第 i行元素的值,表示是否有从顶点 vi出发到图中其他顶点的弧
（即以 vi为尾的弧），若有则相应位置上的值为 1，否则为 0；
第 i列元素的值,表示是否有从图中其他顶点出发到顶点 vi的弧
（即以 vi为头的弧），若有则相应位置上的值为 1，否则为 0。
启迪管理课程17
9.2 图的存储结构 －－邻接矩阵表示法网的邻接矩阵定义为：
V0 V1
V5 V
2
V4
V3
5
48
7 5
5
1
3
N
13
5
5
8
4
75
N
A 0 1 2 3 4 5
0
1
2
3
4
5
反之或若 VRvvvvwjiA jijiji,),(]][[,
其他或若
ji
jijiji
vv
VRvvvvw
jiA 0
,),(
]][[
,或启迪管理课程18
9.2 图的存储结构 －－邻接矩阵表示法
邻接矩阵的特点如下：
(1) 图的邻接矩阵表示是惟一的。
(2) 无向图的邻接矩阵一定是一个对称矩阵。因此,
按照压缩存储的思想,在具体存放邻接矩阵时只需存放上 (或下 )三角形阵的元素即可
(3) 不带权的有向图的邻接矩阵一般来说是一个稀疏矩阵,因此,当图的顶点较多时,可以采用三元组表的方法存储邻接矩阵。
(4) 对于无向图,邻接矩阵的第 i行 (或第 i列 )非零元素 (或非 ∞元素 )的个数正好是第 i个顶点 vi的度。
启迪管理课程19
9.2 图的存储结构 －－邻接矩阵表示法
邻接矩阵的特点如下：
(5) 对于有向图,邻接矩阵的第 i行 (或第 i列 )非零元素 (或非 ∞元素 )的个数正好是第 i个顶点 vi的出度 (或入度 )。
(6) 用邻接矩阵方法存储图,很容易确定图中任意两个顶点之间是否有边相连 。 但是,要确定图中有多少条边,则必须按行,按列对每个元素进行检测,所花费的时间代价很大 。 这是用邻接矩阵存储图的局限性 。
启迪管理课程20
9.2 图的存储结构 －－邻接矩阵表示法
数组表示法的存储结构描述：
#define MAXV <最大顶点个数 >
#define INFINITY INT_MAX //最大值 ∞
typedef struct
{ int no; /*顶点编号 */
InfoType info; /*顶点其他信息 */
} VertexType; /*顶点类型 */
启迪管理课程21
9.2 图的存储结构 －－邻接矩阵表示法
typedef struct /*图的定义 */
{ int edges[MAXV][MAXV]; /*邻接矩阵 */
int n,e; /*顶点数,弧数 */
VertexType vexs[MAXV]; /*存放顶点信息 */
} MGraph;
启迪管理课程22
9.2 图的存储结构 －－邻接矩阵表示法
typedef struct
{ int edges[MAXV][MAXV];
int n,e;
VertexType vexs[MAXV];
} MGraph;
MGraph G2;
邻接矩阵的下标要与顶点的下标对应
a b
d e
c
G2
G2.n=5;
G2.e=6;
G2.vexs=
[{0,a},{1,b},{2,c},{3,d},{4,e}];
00110
00101
11010
10101
01010
.2 e dge sG
a b c d e
a
b
c
d
e
建立无向网络邻接矩阵的算法 (补充 ）
void CREATGRAPH(MGraph *&G,int n,int e)
{int i,j,k;
float w;
G->n=n; //顶点数
G->e=e; //边数
for(i=0;i<n;i++)
{ G->vexs[i].no=i; G->vexs[i],Info=getchar( );}
for(i=0;i<n;i++)
for(j=0;j<n;j++)
G->edges[i][j]=INFINITY;
for(k=0,k<e;k++)
{scanf(“%d,%d,%f”,&i,&j,&w);
G->edges[i][j]=w;
G->edges[j][i]=w;
}
}
a b
d e
c
G2
2
1 4
5
9 6
启迪管理课程24
advex nextarc info data firstarc
表结点 表头结点图的邻接表存储方法是一种顺序与链式存储结构相结合的存储方法。在邻接表中,对图中每个顶点建立一个单链表,单链表中的第 i个结点表示依附于顶点 vi的边,对有向图是以顶点 vi为尾的弧
(出边 )。每个单链表上附设一个表头结点。表结点和表头结点的结构如下：
表结点采用链存储结构 表头结点采用顺序存储结构
9.2 图的存储结构 －－邻接表启迪管理课程25
表结点的三个域,
adjvex 是个整形变量,指示与顶点 vi邻接的点在图中的位置 ;
nextarc 是指针型变量,指向下一条边或弧的结点 ;
Info存储与边或弧相关的信息,如权值等 ;
表头结点的两个域,
data 存储顶点 vi的名称或其他信息 ;
firstarc指向链表中第一个结点。
advex nextarc info data firstarc
表结点 表头结点
9.2 图的存储结构 －－邻接表启迪管理课程26
1
2 3 0
4
10
1
2
3
4
3 4v0
v1
v2
v3
v4
表头结点 表结点
∧
0 2 3 ∧
1 3 4 ∧
0 1 2 4 ∧
0 2 3 ∧无向图 G1
无向图 G1的邻接表无向图的邻接表示意图
9.2 图的存储结构 －－邻接表边数 × 2边结点的个数 =
顶点 i的度 = 第 i个链表中的表结点个数启迪管理课程27
10
1
2
3
4
3v0
v1
v2
v3
v4
表头结点 表结点
∧
2 3 ∧
3 4 ∧
∧
0 3 ∧
有向图 G2
有向图 G2的邻接表
1
2 3 0
4
有向图的邻接表示意图
9.2 图的存储结构 －－邻接表表结点的个数 =
结点 vi的出度：,
结点 vi的入度,.
第 i个链表中的结点个数遍历整个邻接表，查找表结点中 adjvex等于 vi位置的所有结点。
边的条数启迪管理课程28
0
1
2
3
4
v0
v1
v2
v3
v4
表头结点 表结点带权有向图 G3
带权有向图 G3的邻接表
1
0 2
3
4
38 6
5 9
1 8 3 5 ∧
2 3 ∧
4 6 ∧
2 9 ∧
∧
9.2 图的存储结构 －－邻接表启迪管理课程29
9.2 图的存储结构 －－邻接表
40
1
2
3
4
v0
v1
v2
v3
v4
表头结点 表结点
∧
0 ∧
1 ∧
有向图 G2
有向图 G2的 逆 邻接表
1
2 3 0
4 0 1 2 4 ∧
2 ∧
表结点的个数 =
结点 vi的入度：,
结点 vi的出度,.
第 i个链表中的结点个数遍历整个逆邻接表，查找表结点中 adjvex等于 vi位置的所有结点。
边的条数启迪管理课程30
邻接表的特点如下：
(1) 邻接表表示不惟一 。 这是因为在每个顶点对应的单链表中,各边结点的链接次序可以是任意的,取决于建立邻接表的算法以及边的输入次序 。
(2) 对于有 n个顶点和 e条边的无向图,其邻接表有 n
个顶点结点和 2e个边结点 。 显然,在总的边数小于 n(n-
1)/2的情况下,邻接表比邻接矩阵要节省空间 。
(3) 对于无向图,邻接表的顶点 vi对应的第 i个链表的边结点数目正好是顶点 vi的度 。
(4) 对于有向图,邻接表的顶点 vi对应的第 i个链表的边结点数目仅仅是 vi的 出度 。 其入度为邻接表中所有
adjvex域值为 i的边结点数目 。
启迪管理课程31
9.2 图的存储结构 －－邻接表邻接表的类型说明
typedef struct ANode /*弧的结点结构类型 */{ int adjvex;
/*该弧的依附的另一顶点的下标 */struct ANode *nextarc;
/*指向下一条弧的指针 */InfoType info;
/*该弧的相关信息 */
} ArcNode;
firstarcdata
adjvex info nextarc
typedef struct Vnode /*邻接表头结点的类型 */
{ Vertex data; /*顶点信息 */
ArcNode *firstarc; /*指向第一条弧 */
} VNode;
typedef VNode AdjList[MAXV];//AdjList是邻接表类型
typedef struct
{ AdjList adjlist; /*邻接表 */
int n,e; /*图中顶点数 n和边数 e*/
} ALGraph; /*图的类型 */
typedef 还可以掩饰符合类型，如指针和数组。例如，
你不用象下面这样重复定义有 100个字符元素的数组：
char line[100]; char text[100];
定义一个 typedef，每当要用到相同类型和大小的数组时，可以这样：
typedef char Line[100]; Line line,text;
void CREATADJLIST(ALGraph *&ga,int n,int e)
{int i,j,k;
ArcNode *s;
ga->n=n; ga->e=e;
for(i=0;i<n;i++)
{ga->adjlist[i].data=getchar( );
ga->adjlist[i].firstarc=NULL;
}
for(k=0;k<e;k++)
{scanf("\n%d,%d",&i,&j);
s=(ArcNode *)malloc(sizeof(ArcNode));
s->adjvex=j; s->nexarc=ga->adjlist[i].firstarc;
ga->adjlist[i].firstarc=s;
s=(ArcNode *)malloc(sizeof(ArcNode));
s->adjvex=i; s->nextarc=ga->adjlist[j].firstarc;
ga->adjlist[j].firstarc=s;
}
}
A
DC
B
^D
^C
^B
^A0
1
2
3
生成邻接表的算法（无向图）
void CREATADJLIST(ALGraph *&ga,int n,int e)
{int i,j,k;
ArcNode *s;
ga.n=n; ga.e=e;
for(i=0;i<n;i++)
{ga->adjlist[i].data=getchat( );
ga->adjlist[i].firstarc=NULL;
}
for(k=0;k<e;k++)
{scanf("\n%d,%d",&i,&j);
s=(ArcNode *)malloc(sizeof(ArcNode));
s->adjvex=j; s->nexarc=ga->adjlist[i].firstarc;
ga->adjlist[i].firstarc=s;
s=(ArcNode *)malloc(sizeof(ArcNode));
s->adjvex=i; s->nextarc=ga->adjlist[j].firstarc;
ga->adjlist[j].firstarc=s;
}
}
A
DC
B
//0,1
^D
^C
^B
^A0
1
2
3
^1
s
^0
s
void CREATADJLIST(ALGraph *&ga,int n,int e)
{int i,j,k;
ArcNode *s;
ga.n=n; ga.e=e;
for(i=0;i<n;i++)
{ga->adjlist[i].data=getchat( );
ga->adjlist[i].firstarc=NULL;
}
for(k=0;k<e;k++)
{scanf("\n%d,%d",&i,&j);
s=(ArcNode *)malloc(sizeof(ArcNode));
s->adjvex=j; s->nexarc=ga->adjlist[i].firstarc;
ga->adjlist[i].firstarc=s;
s=(ArcNode *)malloc(sizeof(ArcNode));
s->adjvex=i; s->nextarc=ga->adjlist[j].firstarc;
ga->adjlist[j].firstarc=s;
}
}
A
DC
B
^D
^C
B
A0
1
2
3
^1
^0
//0,2
2
s
^0
s
启迪管理课程35
9.2 图的存储结构 －－十字邻接表和多重邻接表
十字邻接表是对有向图而言的，实际上是邻接表和逆邻接表的结合。
在无向图的邻接表存储方法中，每条边 (vi,vj)用两个表结点表示。这给图的某些操作带来不便。
邻接多重表用于存储无向图。
十字邻接表多重邻接表启迪管理课程36
图的遍历,从图中某一顶点出发访遍图中其余顶点，
且使每一个顶点仅被访问一次。 v
1 v2
v4 v5
v3
G2
在图的遍历过程中，需设置一个辅助数组 visited[n]记录每个顶点是否已被访问过，它的初值为 0，表示未被访问过，在访问了顶点之后便将相应的值置为 1。
图的两种遍历方法,深度优先搜索法广度优先搜索法
9.3 图的遍历 －－图的遍历的概念启迪管理课程37
9.3 图的遍历 －－深度优先搜索遍历
搜索规则,从图中指定顶点 v出发，先访问 v，然后依次从该顶点未被访问过的邻接顶点出发进行深度优先搜索，
直到图中与 v相通的所有顶点都被访问过。
V1
V2 V3
V4 V5
V8
V6 V7
V1
V2
V4
V8
V5
V3
V6
V7
遍历序列,v1,v2,v4,v8,v5,v3,v6,v7
9.3.2 深度优先搜索深度优先搜索生成树深度优先遍历的实现 (邻接矩阵）
v0 v1
v2 v3
0001
1000
0000
0110
1G
A
设从第 1个顶点出发，请给出访问的序列及过程。
// 算法中使用的全局变量
int visited[n];
MGraph g; //图的邻接矩阵
DFSM( int i)
{int j;
printf(“node:%c\n”,g.vexs[i].info);
visited[i]=1;
for(j=0;j<n;j++)
if(g.edges[i][j]==1)&&(!visited[j]))
DFSM(j);
}
深度优先遍历的实现（邻接表）
int visited[n]={0};
void DFS(ALGraph *G,int v)
{ ArcNode *p;
visited[v]=1;
printf("%d ",v);
p=G->adjlist[v].firstarc;
while (p!=NULL)
{ if (visited[p->adjvex]==0)
DFS(G,p->adjvex);
p=p->nextarc;
}
}
1
3 0 2
4
0
1
2
3
4
1
0
1
0
0
3
2
3
1
2
4 ∧
3 ∧
4 ∧
2
3 ∧
4 ∧
v 0
v 1
v 2
v 3
v 4
V=2 0
1
2
3
4
0
0
0
0
0
visited[n]
1
输出序列,2
p
V=1 1
1
p
V=0
1
0
p p
V=3
1
3
p p p p
V=4
1
4
p p p p
p
p p
p p p
p p p
启迪管理课程40
9.3 图的遍历 －－广度优先搜索遍历
9.3.3 广度优先搜索搜索规则,首先访问初始点 v，接着访问 v的所有未被访问过的邻接点 v1,v2,…,v t,然后在按照 v1,v2,…,v t的次序，
访问每一个顶点的所有未被访问过的邻接点，依次类推，
直到图中所有和初始点 v有路径相通的顶点都没访问过为止。
V1
V2 V3
V4 V5
V8
V6 V7
V1
V2 V3
V4 V
5 V6
V7
V8 v1 v2 v3 v4 v5 v6 v7 v8
广度优先搜索生成树启迪管理课程41
9.3 图的遍历 －－广度优先搜索遍历特点,广度优先搜索遍历图的过程是以 v为起点，由近至远，依次访问和 v有路径相通且路径长度分别为 1，
2,… 的顶点，即相当于按层次遍历。
V1
V2 V3
V4 V5
V8
V6 V7
V1
V2 V3
V4 V5 V6 V7
V8 v1 v2 v3 v4 v5 v6 v7 v8
启迪管理课程42
9.3 图的遍历 －－广度优先搜索遍历
算法的实现：
①设置 visited[ vexnum]
② 需附设一个队列以实现层次遍历。
广度优先遍历算法 V1
V2 V3
V4 V5
V8
V6 V7
遍历过程：
(1)开始时将队列置空,visited置为 0；
(2)在每访问一个顶点 v时,要将其入队,且 vistied[v]=1.
(3)队头元素出队，依次访问其未被访问过的邻接点。
(4)重复 (2)(3)的步骤，直至队列为空，此时说明每一个访问过的顶点的所有邻接点均已被访问，本次遍历完毕。
v0 v1
v2 v3
0001
1000
0000
0110
1G
A
BFSM(int k) //k=0
//广度优先遍历以邻接矩阵存储的图 g
{ int i,j;
InitQueue(Q); //置空队列
print("%c\n",g.vexs[k]);
visited[k]=1;
EnQueue(Q,k);
while(!QueueEmpty(Q))
{i=DeQueue(Q);
for(j=0;j<n;j++)
if(g.edges[i][j]==1)&&(!visited[j])
{printf("%c\n",g.vexs[j]);
visited[j]=1;
EnQueue(Q,j);
}
}
}
头 尾
0
visited[ ]={0,0,0,0};1
//i=0
1 2
1 1
v0 v1
//i=1
v2
//i=2
v3
1
3
//i=3
void BFS(ALGraph *G,int v)
{ ArcNode *p; int w,i;
int queue[MAXV],front=0,rear=0; /*定义循环队列 */
int visited[MAXV]; /*定义存放结点的访问标志的数组 */
for (i=0;i<G->n;i++) visited[i]=0; /*访问标志数组初始化 */
printf("%2d",v); /*输出被访问顶点的编号 */
visited[v]=1; /*置已访问标记 */
rear=(rear+1)%MAXV;
queue[rear]=v; /*v进队 */
1 23
40
0
1
2
3
4
0
0
0
0
0
visited[n]
V=2
1
2输出序列：
2
while (front!=rear) /*若队列不空时循环 */
{ front=(front+1)%MAXV;
w=queue[front]; /*出队并赋给 w*/
p=G->adjlist[w].firstarc; /*找 w的第一个的邻接点 */
while (p!=NULL)
{ if (visited[p->adjvex]==0)
{ printf(“%2d”,p->adjvex); /*访问之 */
visited[p->adjvex]=1;
rear=(rear+1)%MAXV;/*该顶点进队 */
queue[rear]=p->adjvex;
}
p=p->nextarc; /*找下一个邻接顶点 */
}
}
printf("\n");
}
0
1
2
3
4
1
0
1
0
0
3
2
3
1
2
4 ∧
3 ∧
4 ∧
2
3 ∧
4 ∧
v 0
v 1
v 2
v 3
v 4
1 23
40
0
1
2
3
4
0
0
0
0
0
visited[n]
1
2输出序列：
2
p
W=2
1
1
1
p
3
1
3
p
4
1
4 p
W=1
p
0
1
0
1
3 0 2
4
启迪管理课程46
9.3 图的遍历 －－非连通图的遍历非连通图的遍历 (深度优先）
V1
V2
V4
V3
V5
A
DC
B
从图中指定顶点 v出发，先访问 v，然后依次从该顶点未被访问过的邻接顶点出发进行深度优先搜索，直到图中与 v相通的所有顶点都被访问过。 如果图中尚有未被访问过的顶点，则从另一个未被访问过的顶点出发重复上述过程，直到图中所有顶点都被访问过。
启迪管理课程47
9.3 图的遍历 －－非连通图的遍历
DFS1(ALGraph *g)
{
int i;
for (i=0;i<g->n;i+)
if (visited[i]==0)
DFS(g,i);
}
BFS1(ALGraph *g)
{
int i;
for (i=0;i<g->n;i+)
if (visited[i]==0)
BFS(g,i);
}
启迪管理课程48
9.4 生成树和最小生成树 －－生成树的概念
9.4.1 生成树的概念生成树是一个具有 n个顶点的连通图的一个极小连通子图,它含有图中全部顶点,但只有构成一棵树的 (n-1)条边。
极小连通子图,若删除极小连通子图的任意一条边,
该图就成为非连通图。
无向连通图 G
0
1 2
3 4
0
1 2
3 4
0
1 2
3 4
图 G的二颗生成树启迪管理课程49
9.4 生成树和最小生成树 －－生成树的概念一个连通图可以有多个生成树,即生成树不是唯一的。
最小生成树的定义：
一个带权连通图的所有生成树中具有边上的权值之和最小的树称为最小生成树。
生成树的特点：
(1) 一颗有 n个顶点的生成树有且仅有 n-1条边；
(2)生成树是个无任何回路的连通图；
(3)如果在生成树上添加一条边,必定构成一个环
(4)如果在生成树中删除一条边,则变为非连通图。
启迪管理课程50
9.4 生成树和最小生成树 －－生成树的概念对于一个具有 n个顶点的连通图 G，构造它的生成树的准则为：
(1) 必须使用图 G中的边来构造；
(2)必须使用且仅使用图 G中的 n-1条边来连接 n个顶点；
(3)不能使用生产回路的边；
说明：具有 n个顶点,n-1条边的图并不一定是生成树！只有那些符合定义的才是生成树。
如何构造生成树？
启迪管理课程51
9.4 生成树和最小生成树 －无向图的连通分量和生成树
9.4.2 无向图的连通分量和生成树
对于连通图，连通分量就是图本身，故只需调用遍历过程一次即可。
本节要解决的问题是：如何构造一个无向连通图的生成树？
实际上,对一个具有 n个顶点的无向连通图 G进行遍历 (深度优先或广度优先 )一次所得到的顶点集合及相关边的集合就构成图 G的一个极小连通子图，即图 G的一颗生成树。
看一个例子启迪管理课程52
无向连通图 G
0
1 2
3 4
10
1
2
3
4
3v0
v1
v2
v3
v4
∧
0 2 3 ∧
1 3 4 ∧
0 1 2 4 ∧
2 3 ∧
图 G的邻接表图 G的生成树
0
1 2
3 4
图 G的深度优先生成树深度优先遍历启迪管理课程53
9.4 生成树和最小生成树 －无向图的连通分量和生成树
对于非连通图，每个连通分量中的顶点集和遍历此连通分量过程中经过的边一起构成一棵生成树，这些连通分量的生成树组成非连通图的生成森林。
说明
一个图可以有许多棵不同的生成树（起点、次序）
所有生成树具有以下共同特点：
生成树的结点个数与图的顶点个数相同
生成树是图的极小连通子图
一个有 n个顶点的连通图的生成树有 n-1条边
生成树中任意两个结点间的路径是唯一的
在生成树中再加一条边必然形成回路
含 n个顶点 n-1条边的图不一定是生成树一旦确定了存储结构、起点以及遍历方法，那么图的生成树将惟一确定。
启迪管理课程54
9.4 生成树和最小生成树 －无向图的连通分量和生成树问题：假设要在 n个城市之间建立通讯联络网，则连通
n个城市只需修建 n-1条线路,如何在最节省经费的前提下建立这个通讯网？
最小生成树边 max=n(n-1)/2
边 min=n-1
问题转化,该问题等价于构造网的一棵最少生成树，即 e条带权的边中选取 n-1条 (不构成回路 )，
使,权值之和,为最小。
a
b
c
d
4
2
3
f
g
h
e9
7 3
25
4 6
5
5
5 6
权值之和,4+5+5+4+5+6+7=36
权值之和,2+3+5+4+5+2+5=22
启迪管理课程56
9.4 生成树和最小生成树 －普里姆算法
算法思想,G=(V,E)是连通无向网络,T=(U,TE)是 G
的最小生成树,其中 U是 T的顶点集,TE是 T的边集 。
(1)初始化 U={v0}。 v0到其他顶点的所有边为候选边；
(2)重复以下步骤 n-1次,使得其他 n-1个顶点被加入到 U
中
① 从候选边中挑选权值最小的边输出,设该边在 V-U
中的顶点是 v,将 v加入 U中；
② 考察当前 V-U中的所有顶点 vi,修改候选边：若
(v,vi)的权值小于原来和 vi关联的候选边,则用 (v,vi)取代后者作为候选边。
普里姆 (Prim)算法
u0
U
u1
V-U
u2
ui uk
un
假设当前生成树 T中有 k个顶点，则当前连接 U和 V-U
的边有 k(n-k)条。 （如果两顶点间无边，则虚拟其存在一条无穷大的边）
另设一数组 closest[n]:数组中的各分量表示 U中到 V-U的各顶点距离最近的顶点。
Prim算法的关键,如何 有效地 找到连接 U和 V-U的最短边来扩充生成树 T。
方法,构造候选边集 (即辅助数组 lowcost[n]），且保证两个集合间的最短边属于候选边集。
6 5
1 75
3 6
6
4 2
V0
V1 V3
V2
V4 V5
v1
v2
v3
v4
v5
v0
U V-U
0624
6063
2075
467051
3506
5160
di s t
lowcost[ ]={6,0,5,∞,3,∞};
closest[ ]={1,1,1,1,1,1};
0 6
4
01
2
7
2
4
2
0 5
0
02
5
0
closest[i]存储该边依附在 U中的顶点启迪管理课程59
Prim算法的语言描述
（ 1）置 T为任意一个顶点，初始化候选边集 lowcost
和 closest；
（ 2） while(T中顶点数目 <n）
（ 3） {从候选边集中选取最短的边（ u,v）；
（ 4） 将 (u,v）及顶点 v扩充到 T中；
（ 5） 调整 lowcost和 closest；
}
9.4 生成树和最小生成树 －普里姆算法启迪管理课程60
9.4 生成树和最小生成树 －克鲁斯卡尔算法克鲁斯卡尔 (Kruskal)算法
算法思想,设连通网 N=(V,E),令最小生成树,
初始状态为只有 n个顶点而无边的非连通图 T=(V,?)，
每个顶点自成一个连通分量
在 E中选取代价最小的边,若该边依附的顶点落在 T中不同的连通分量上，则将此边加入到 T中；否则，舍去此边，选取下一条代价最小的边
依此类推，直至 T中所有顶点都在同一连通分量上为止启迪管理课程61
9.4 生成树和最小生成树 －克鲁斯卡尔算法克鲁斯卡尔 (Kruskal)算法例 1
65
4
3
2
6 5
1
3
5
6
6
4 2
5
1
65
4
3
2 1
23 4
5
5
5
1
1
3
2
4
6
3
2
5
4
3
6
5
1
4
5
3
4
5
2
3
6
1
2
6
3
5
6
5
6
权值邻接点邻接点启迪管理课程62
9.5 最短路径 －路径的概念
9.5 最短路径
问题提出用带权的有向图表示一个交通运输网，图中：
顶点 —— 表示城市边 —— 表示城市间的交通联系权 —— 表示此线路的长度或沿此线路运输所花的时间或费用等,
问题：从某顶点出发,沿图的边到达另一顶点所经过的路径中，各边上权值之和最小的一条路径 —— 最短路径求图的最短路径分以下两方面：求图中某一顶点到其余各顶点的最短路径和求图中每一对顶点之间的最短路径。
启迪管理课程63
9.5 最短路径
9.5.2 从一个顶点到其余各顶点的最短路径单源最短路径,对于给定的有向网络 G=(V,E)及单个源点 v,求从 v到 G的其余个顶点的最短路径。
算法的基本思想,按最短路径长度的递增次序依次求得各条路径。
狄克斯特拉（ Dijkstra)算法启迪管理课程64
9.5 最短路径假设图中所示为从源点到其余各点之间的最短路径，则在这些路径中，必然存在 一条长度 最短者。
源点 a b
c
…
在这条路径上，必定只含有一条 (权值最小 )弧，由此，
只要在所有从源点出发的弧中查找权值最小者；
长度次短的路径 可能有两种情况,
它可能是从源点直接到该点的路径。
也可能是：从源点到 c，再从 c到该点的路径之和。
其余依次类推。
启迪管理课程65
1 4
0 2 6
3 5
8
1
6 6
4
2
5
6
6
1
4
7
终点
dist
路径
1 2 3 4 5 6
disk[k]表示当前所求得的从源点到顶点
k的最短路径长度。一般情况下，
disk[k]=源点到顶点 k的弧上的权值或者＝源点到 其他顶点 的路径长度 +
其它顶点 到顶点 k弧上的权值
4
0,1
6
0,2
6
0,3
∞ ∞ ∞5
0,1,2
11
0,1,4
9
0,1,2,5
17
0,1,2,5,6
10 16
0,1,2,5,4 0,1,2,5,4,6
求顶点 0到其余各顶点的最短路径启迪管理课程66
9.5 最短路径
9.5.3 每一对顶点之间的最短路径
方法一,每次以一个顶点为源点，重复执行
Dijkstra算法 n次 ——T(n)=O(n3)
for(i=0;i<n;i++)
Dijkstra(cost,n,i);
方法二,弗洛伊德 (Floyd)算法 (不讲）
启迪管理课程67
本 章 小 结：
图的相关概念
图的存储结构邻接矩阵邻接表
图的遍历深度优先搜索广度优先搜索
图的最小生成树及应用
最短路径
