文档介绍：图的定义与存储结构
第1页，本讲稿共25页
基本概念
G = (V, E) V是顶点集，E是顶点间二元关系的集合。
与树的区别：
①树有特殊的根结点；
②树的结点和关系能分成互不相交的若干子集
第2页，本讲稿共2f struct {
int vexnum,arcnum; //图的当前顶点数和边数
Vexs vexs; //顶点数组
AdjMatrix arcs; //邻接矩阵
}Graph;
arcs[i][j]=
1 顶点vi与vj间有边(弧)
0 顶点vi与vj间无边(弧)
第12页，本讲稿共25页
图的数组表示法
0 1 0 1 0
0 1 0 1
0 1 0 1 1
0 1 0 0
0 1 1 0 0
0 1 1 0
0 0 0 0
0 0 0 1
0 0 0
V0
V4
V3
V1
V2
V0
V1
V2
V3
Graph G1;
=
=5；
=6;
={V0,V1,V2,V3,V4};
Graph G2;
=
=4；
=4;
={V0,V1,V2,V3};
第13页，本讲稿共25页
1）无向图的邻接矩阵是对称矩阵，有向图的邻接矩阵不一定是对称的；
2）顶点v的度：等于二维数组对应行（或列）中值为1的元素个数；
顶点v的出度：等于二维数组对应行中值为1的元素个数；
顶点v的入度：等于二维数组对应列中值为1的元素个数；
3）判断两顶点v、u是否为邻接点：只需判二维数组对应分量是否为1
4）顶点不变，在图中增加、删除边：只需对二维数组对应分量赋值1或清0；
5）设图G的顶点数为 n , 则G占用的存储空间为：n+n2；图的存储空间占用量只与它的顶点数有关，与边数无关，适用于边稠密的图。
数组表示法的特点
第14页，本讲稿共25页
网的数组表示法
8
2
7
3
4
9
6
2
2
1
V3
2
V2
V4
V1
V6
V5
∞ 8 ∞ 7 4 9
8 ∞ 2 1 ∞ ∞
∞ 2 ∞ 3 ∞ 2
7 1 3 ∞ ∞ 2
4 ∞ 2 ∞ ∞ 6
9 ∞ 2 2 6 ∞
1
2
3
4
5
6
1 2 3 4 5 6
arcs[i][j]=
权值 顶点vi与vj间有边(弧)
∞ 顶点vi与vj间无边(弧)
第15页，本讲稿共25页
图的邻接表存储结构
例
V0
V4
V3
V1
V2
下标
v0
1
v1
v2
v3
v4
3
∧
0
2
4
∧
1
3
4
∧
0
2
∧
1
2
∧
0
1
2
3
4
无向图的邻接表
顶点：顺序结构
关联同一顶点的边：用线性链表存储
该结点表示边（V0,V1）,其中1是V1在一维数组中的下标
顶点数据
指向第一个
邻接顶点的指针
数组元素结构
无向图的邻接表
第16页，本讲稿共25页
下标
v0
1
v1
∧
v2
v3
2
∧
3
∧
0
∧
0
1
2
3
例
V0
V1
V2
V3
例
V0
V1
V2
V3
下标
v0
v1
v2
v3
3
∧
0
∧
2
∧
0
1
2
3
0
∧
有向图的邻接表
顶点：顺序结构
以同一顶点为起点的弧：用线性链表存储（出边表）
有向图的逆邻接表
以同一顶点为终点的弧：用线性链表存储（入边表）
第17页，本讲稿共25页
网的邻接表表示
8
2
7
3
4
9
6
2
2
1
V3
2
V2
V4
V1
V6
V5
(c) 邻接链表
1
2
3
4
5
6
2
8
5
4
6
9
4
7
∧
1
8
3
2