3.便于实现图的一些基本操作
如：FirstAdjVertex（G，v）： • 首先，由LocateVertex（G，v）找到v在图 中的位置，即v在一维数组vexs中的序号I。 • 二维数组arcs中第i行上第一个adj域非零的 分量所在的列号j，便是v的第一个邻接点在 图G中的位置。 • 取出一维数组vexs[j]中的数据信息，即与 顶点v邻接的第一个邻接点的信息。
由于“弧”是有方向的，因此称由顶点 集和弧集构成的图为有向图。
例如: G1 = (V1, VR1)
A
B C D E 其中 V1={A, B, C, D, E} VR1={<A,B>, <A,E>,
<B,C>, <C,D>, <D,B>, <D,A>, <E,C> }
若<v, w>VR 必有<w, v>VR, 则称 (v,w) 为顶点 v 和顶点 由顶点集和边 集构成的图称 w 之间存在一条边。 作无向图。 例如: G2=(V2,VR2) V2={A, B, C, D, E, F} VR2={(A, B), (A, E),
插入和删除弧
对邻接点的操作
遍历
结构的建立和销毁
CreatGraph(&G, V, VR):
// 按定义(V, VR) 构造图 DestroyGraph(&G):
// 销毁图
对顶点的访问操作
LocateVex(G, u); // 若G中存在顶点u，则返回该顶点在 // 图中“位置” ；否则返回其它信息。 GetVex(G, v); // 返回 v 的值。
PutVex(&G, v, value); // 对 v 赋值value。
对邻接点的操作
FirstAdjVex(G, v);
// 返回 v 的“第一个邻接点” 。若该顶点 //在 G 中没有邻接点，则返回“空”。
NextAdjVex(G, v, w); // 返回 v 的（相对于 w 的） “下一个邻接
A B E
C
F
0 A 1 B 2 C 3 F
1 2 3 0
4
可见，在有向图的 邻接表中不易找到
1
指向该顶点的弧
4 E
2
存储空间
•对于有n个顶点，e条边的无向图而言， 若采取邻接表作为存储结构，则需要n个 表头结点和2e个表结点。很显然在边很 稀疏（即e远小于n(n-1)/2时）的情况下， 用邻接表存储所需的空间要比邻接矩阵 所需的n(n-1)/2要节省得多。 •在有向图邻接表中，一条弧对应一个表 结点，表结点的数目和弧的数目相同。
// 点”。若 w 是 v 的最后一个邻接点，则 // 返回“空”。
插入或删除顶点
InsertVex(&G, v);
//在图G中增添新顶点v。
DeleteVex(&G, v);
// 删除G中顶点v及其相关的弧。
插入和删除弧
InsertArc(&G, v, w); // 在G中增添弧<v,w>，若G是无向的， //则还增添对称弧<w,v>。 DeleteArc(&G, v, w); //在G中删除弧<v,w>，若G是无向的， //则还删除对称弧<w,v>。
假若顶点v 和顶点w 之间存在一条边， 则称顶点v 和w 互为邻接点，
边(v,w) 和顶点v 和w 相关联。 和顶点v 关联的边的数目定义为v的度。 B C
例如: 右侧图中
TD(B) = 3 TD(A) = 2
A F E
D
对有向图来说，由于弧有方向性，则
A
有入度和出度之分
B
C F
E
顶点的出度: 以顶点 v 为弧尾的弧的数目; 顶点的入度: 以顶点 v为弧头的弧的数目。 顶点的度(TD)= 出度(OD)+入度(ID)
结构组成
一个n个顶点的图的邻接表表示需要有两 部分构成： ①表头结点表 由所有表头结点以顺序结构（向量）的形 式存储，以便可以随机访问任一顶点的单 链表 ②表示图中顶点间邻接关系的n个单链表 (即边表或弧表)
弧结点的结构
adjvex nextarc info
typedef struct ArcNode {
第 7 章
图
7.1 图的定义和术语
7.2 图的存储结构
7.3 图的遍历 7.4 图的连通性问题
7.5 有向无环图及其应用
7.6 最短路径
7.1
图的定义和术语
图的结构定义:
图是由一个顶点集 V 和一个弧集V R构成
的数据结构。 Graph = (V, VR ) 其中，VR＝{<v,w>| v,w∈V 且 P(v,w)} <v,w>表示从 v 到 w 的一条弧，并称 v 为 弧尾，w 为弧头。 谓词 P(v,w) 定义了弧 <v,w>的意义或信息。
图的结构定义(邻接表)
typedef struct {
AdjList vertices; int vexnum, arcnum;
int
kind;
// 图的种类标志
} ALGraph;
示例
A
B
C D
0 1 2 3 4 5
A B C D E F
1 0 3 2 0 1
ቤተ መጻሕፍቲ ባይዱ
4 4 5 5 1 2
5
F
E
3
有向图的邻接表
E
分别称作有向网或 无向网。
C
F B A E C
设图G=(V,{VR}) 和 图 G=(V,{VR}), B 且 VV, VRVR, 则称 G 为 G 的子图。
A
假设图中有 n 个顶点，e 条边，则
含有 e=n(n-1)/2 条边的无向图称作 完全图; 含有 e=n(n-1) 条弧的有向图称作 有向完全图; 若边或弧的个数 e<nlogn，则称作 稀疏图，否则称作稠密图。
C F
个顶点相同的路径。
若图G中任意两个顶 点之间都有路径相通， 则称此图为连通图; A B A
F E
B
C D
C
D
F
E
若无向图为非连通图， 则图中各个极大连通 子图称作此图的连通 分量。
对有向图， 若任意两个顶点之间都存在
一条有向路径，则称此有向图为强连通图。 否则，其极大强连通子图称作它的 强连通分量。 A B E B A E
无向图的度
• 在无向图的邻接表中，各顶点对应的单链 表的结点数（不算表头结点）就等于该顶 点的度数。
有向图的度
• 在有向图邻接表中，单链表的结点数就等 于相应顶点的出度数。 • 要求有向图中某顶点的入度数，需扫视邻 接表的所有单链表，统计与顶点标号相应 的结点个数。 解决方法:再建立一个逆邻接表
有向图的逆邻接表
B
A E
在有向图的邻接表
中，对每个顶点，
C
0 A
3
3 4 2 0
D
0 1 ^
链接的是指向该顶
点的弧
1 B
2 C
3 D
4 E
三、有向图的十字链表存储表示
十字链表(Orthogonal List)是有向图的另 一种链式存储结构。我们也可以把它看成 是将有向图的邻接表和逆邻接表结合起来 形成的一种链表。有向图中的每一条弧对 应十字链表中的一个弧结点，同时有向图 中的每个顶点在十字链表中对应有一个结 点，叫做顶点结点。
A
B C F E
0 0 0 0 1
1 0 0 0 1
0 1 0 1 0
1 0 0 0 0
0 0 1 0 0
图的邻接矩阵存储表示
#define INFINITY INT_MAX //最大顶点数 typedef enum{DG,DN,UDG,UDN} GraphKind; //{有向图,有向网,无向图,无向网} //最大值∞
一、图的数组 ( 邻接矩阵 ) 存储表示 C B 二、图的邻接表存储表示
A D
三、有向图的十字链表存储表示
F E
四、无向图的邻接多重表存储表示
一、图的数组(邻接矩阵)存储表示
• 邻接矩阵是表示顶点之间相邻关系的矩 阵。所谓两顶点的相邻关系即它们之间 有边相连。 • 邻接矩阵是一个（n×n）阶方阵，n为图 的顶点数，它的每一行分别对应图的各 个顶点，它的每一列也分别对应图的各 个顶点。我们规定矩阵的元素为：
1.存储空间
• 无向图的邻接矩阵是对称的，如果A[i， j]=1，必有A[j，i]=1。这说明，只输入和 存储其上三角阵元素即可得到整个邻接矩阵。 其存储空间仅需n(n-1)/2 • 一般有向图的邻接矩阵是不对称的，A[i，j] 不一定等于A[j，i]。其存储空间需n2 • 对于稀疏图而言，不适于用邻接矩阵来存储， 因为这样会造成存储空间的浪费。
二、图的邻接表存储表示
基本思想 • 邻接表是图的一种链接存储结构。 • 对于图中存在的边信息则存储起来，而 对于不相邻接的顶点则不保留信息。在 邻接表中，对图中的每个顶点建立一个 带头结点的单链表，如第i个单链表中 的结点则表示依附于顶点vi的边（若是 有向图，则表示以vi为弧尾的弧）。每 个单链表的头结点又构成一个表头结点 表。
typedef struct { // 图的定义
VertexType
AdjMatrix
// 顶点信息
arcs; // 弧的信息 // 图的种类标志
vexs[MAX_VERTEX_NUM];
int vexnum, arcnum; // 顶点数，弧数
GraphKind kind;
} MGraph;
邻接矩阵表示法的特点
C
F
C
F
