第七章 图
图的定义
图的存储结构
图的遍历
图的应用
7.1 图的定义和术语
1,图有向图（ Digragh）
无向图（ Undigraph）
图也是一种非线性地数据结构其抽象数据类型见书 P156.
7.1 图的定义和术语
有向图（ Digragh）
G=（ V,{A}）
其中,V为顶点的有穷非空集合
{A}为顶点之间的关系集合
G1=（ V,{A}）
V={v1,v2,v3,v4}
A={<v1,v2>,<v1,v3>,<v3,v4>,<v4,v1>}
其中 <x,y>表示从 x到 y的一条弧（ arc）,A为弧集合,x为弧尾（ tail）,y为弧头（ head)
① ②
③ ④
G1
7.1 图的定义和术语
无向图（ Undigraph）
G=(V,{E})
其中,V同有向图,{E}为顶点之间的关系集合,
E为边集合
G2=（ V,{A}）
V={v1,v2,v3,v4,v5}
E={(v1,v2),(v1,v4),(v2,v3),(v3,v4),(v2,v5),(v3,v5)}
其中,(x,y)表示 x与 y之间的一条连线，称为边（ edge）
① ②G2
③
④ ⑤
7.1 图的定义和术语设 n为顶点数,e为边或弧的条数对 无向图 有,0<=e<=n(n-1)/2
有向图 有,0<=e<=n(n-1)
证明：每个顶点至多有 n-1条边与其它的 n-1个顶点相连，则 n个顶点至多有 n(n-1)条边 。 但每条边连接 2个顶点，故最多为 n(n-1)/2
7.1 图的定义和术语
2,完全图边达到最大的图
无向完全图,边数为 n(n-1)/2的无向图
有向完全图,弧数为 n(n-1)的有向图权,与图的边或弧相关的数网,边或弧上带有权值的图
7.1 图的定义和术语
3,顶点的度 TD（ V）
无向图,为依附于顶点 V的边数有向图,等于以顶点 V为弧头的弧数（称为 V的 入度，记为 ID（ V））与以顶点 V为弧尾的弧数（称为 V
的出度，记为 OD（ V））之和。即：
TD（ V） =ID（ V） +OD（ V）
无向图
n
e= 1/2（ ∑ TD(vi)）
i=1
结论：
有向图
n n
e= ∑ ID(vi)=∑ OD(vi)
i=1 i=1
无向图的度数为依附于顶点 v
的边数；有向图的度数等于以顶点 v 为弧头的弧数与以顶点 v
为弧尾的弧数之和
7.1 图的定义和术语
4,路径无向图,顶点 v到 v’的路径是一个顶点序列（ v=vi0,vi1,…,vim=v’）
其中，（ vij-1,vij） ∈ E,1<=j<=m
有向图,顶点 v 到 v’的路径是有向的顶点序列 （ v=vi0,vi1,…,vim=v’）
其中，（ vij-1,vij） ∈ A,1<=j<=m
几个概念：
路径长度,路径上边或弧的数目回路或环,首尾顶点相同的路径，称为回路或环。即：
（ v=vi0,vi1,…,v im=v’=v）
简单路径,路径中不含相同顶点的路径简单回路,除首尾顶点外，路径中不含相同顶点的回路
7.1 图的定义和术语
5,连通顶点连通,若顶点 v到顶点 v’有路径，则称顶点 v与 v’是连通的连 通 图,包括无向连通图和有向连通图无向图,若图中任意两个顶点 vi,vj都是连通的，则称该图是连通图 (vi<>vj)
有向图,若图中任意两个顶点 vi,vj，都存在从 vi到 vj和从
vj到 vi的路径，则称该有向图为强连通图 (vi<>vj)
连通分量：
无向图,无向图中极大连通子图，称为连通分量有向图,有向图中极大强连通子图，称为强连通分量
7.1 图的定义和术语
5,连通连通分量：
① ②
③ ④
G1有两个强连通分量① ②
③ ④
G1
7.1 图的定义和术语
6,生成树定义,设无向图 G是含有 n个顶点 的连通图,则图 G的生成树是含有 n个顶点,且只有 n-1条边 的 连通 子图三要素：
n个顶点
n-1条边连通极小连通子图，
若再加一条边，
必构成环生成树 n-1条边
7.2 图的存储结构图有 数组,邻接表,邻接多重表 和 十字链表 等表示方法一、数组表示法（邻接矩阵）
设图 G=（ V,{E}）有 n个顶点，则 G的邻接矩阵定义为 n阶方阵 A。
其中,A[i,j]= 1 若 （ vi,vj）或 <vi,vj>∈E,i≠j
0 其它例如,G1的邻接矩阵
┌ 0 1 1 0 ┐ A1＝ │ 0 0 0 0 │
│ 0 0 0 1 │ 1 0 0 0
① ②G2
③
④ ⑤
┌ 0 1 0 1 0 ┐ A2＝ │ 1 0 1 0 1 │
│ 0 1 0 1 1 │ 1 0 1 0 0
0 1 1 0 0
无向图的邻接矩阵为对称矩阵
① ②
③ ④
G1
7.2 图的存储结构特点,判定两个顶点 Vi与 Vj是否关联,只需判 A[i,j]是否为 1
顶点的度容易求得,
有向图中,TD(Vi)=OD(Vi)+ID(Vi)
n n
= ∑ A[i,j]+∑ A[j,i]
j=1 j=1
n n
无向图中,TD(Vi)=∑ A[i,j]=∑ A[j,i]
j=1 j=1
即顶点 Vi的度等于邻接矩阵中第 i行（或第 i列）的元素之和（非 0元素个数之和）。
即顶点 Vi的出度为邻接矩阵中第 i行元素之和顶点 Vi的入度为邻接矩阵中第 i列元素之和
7.2 图的存储结构网的邻接矩阵定义为,A[i,j]= Wij,若（ Vi,Vj）或 < Vi,Vj>∈E
,其它
V1 V2
V3 V4
3
52
1
4
┌ 3 2 4 ┐ A＝ │ │
│
5 1
如图：
7.2 图的存储结构形式化定义为：
＃ define INFINITY INT_MAX //最大值 ∞
＃ define MAX_VERTEX_NUM 20 //最大顶点个数
Typedef enum{DG,DN,UDG,UDN} GraphyKind; //有向图、无向图、
//有向网、无向网
typedef struct ArcCell {
VrtType adj; // VrtType是顶点关系类型。对无权图，用 1或 0表示邻接否；
// 对带权图，即为权值类型
InfoType *info; //该弧相关信息指针
} ArcCell,AdjMatrix[MAX_VERTEX_NUM ][MAX_VERTEX_NUM ];
typedef struct
{
VertexType vexs[MAX_VERTEX_NUM ]; //顶点向量
AdjMatrix arcs； //邻接矩阵
int vexnum,arcnum;//图的当前顶点数和弧数
GraphyKind kind；
}MGraph; //广义表类型
7.2 图的存储结构二、邻接表（ adjacency list）
1,无向图邻接表对图中 每个顶点 Vi建立一个单链表，链表中的 结点 表示依附于顶点
Vi的边，每个链表结点为 两个域,adjvex nextarc
其中,邻接点域（ adjvex） 记载与顶点 Vi邻接的顶点信息；
链域（ nextarc） 指向下一个与顶点 Vi邻接的邻接的链表 p结点每个链表附设一个 头结点,头结点结构为,vexdata firstarc
其中,vexdata存放顶点信息（姓名、编号等） ；
fristarc指向链表的第一个结点。
形式化定义见书 P163.
7.2 图的存储结构二、邻接表（ adjacency list）
如图 G2的 邻接表 为：
2
5
3
4
1
5
4
3
5
3
3
4
1
2
2
1
2
1
2
3
4
5
特点：设无向图中顶点数为 n，边数为 e，
则它的邻接表需要 n个头结点和 2e个表结点。
顶点 Vi的度 TD（ Vi） =链表 i中的表结点数。
① ②G2
③
④ ⑤
7.2 图的存储结构二、邻接表（ adjacency list）
2,有向图邻接表与无向图的邻接表结构一样。只是在 第 i条链表 上的结点是以 Vi为弧尾 的各个 弧头顶点
2
3
4
1
4
3
1
21
2
3
4
特点,1,n个顶点,e条弧的有向图，需 n个表头结点,e 个表结点
2,第 i条链表上的结点数，为 Vi的出度
（求顶点的出度易，求入度难）
如图 G1的邻接表为：
① ②
G1③ ④
7.2 图的存储结构二、邻接表（ adjacency list）
3,有向图逆邻接表与无向图的邻接表结构一样。只是在 第 i条链表 上的结点是以 Vi为弧头 的各个 弧尾顶点
12
3
4
1
1
4
3
1
2
3
4
此时，第 i条链表上的结点数，为 Vi的入度如图 G1的逆邻接表为,① ②
G1③ ④
7.2 图的存储结构三、十字链表（ orthogonal list）
十字链表是将有向图的邻接表和逆邻接表结合起来的一种 有向图链式存储结构
1,结点结构有向图的每一条弧有一个 弧结点,每一个顶点必有一个 顶点结点,
其结构为,（形式化定义见书 P165.）
tailvex headvex hlink tlink data firstin firstout
弧结点 顶点结点
tailvex,指示该弧的弧尾顶点；
headvex,指示该弧的弧头顶点；
hlink,指向弧头相同的下一条弧；
tlink,指向弧尾相同的下一条弧
data,存放顶点的有关信息
（如顶点的名称，或位置）
firstin,指向以该顶点为弧头的第一个弧结点；
firstout,指向以该顶点为弧尾的第一个弧结点。
7.2 图的存储结构
2,整体结构
通过 hlink将 弧头相同 的弧连在一个链表上；
通过 tlink将 弧尾相同 的弧连在一个链表上
而 hlink链和 tlink链的头结点就是 顶点结点
3,例 G1的十字链表为：
1
2
3
4
1 2 1 3
4 1
3 4
e13e12
e34
e41
① ②
G1③ ④
7.2 图的存储结构
4,特点：
① 顶点结点数 =顶点数弧结点数 =弧的条数
② 求入度,从顶点 Vi的 firstin出发，沿着弧结点中的 hlink所经过的弧结点数。
求出度,从顶点 Vi的 firstout出发，沿着弧结点中的 tlink
所经过的弧结点数。
7.2 图的存储结构四、邻接多重表邻接多重表是 无向图 的另一种 链式 存储结构。
图的每一条边有一个边结点，边结点的结构为：
ivex ilink jvex jlink
每一个顶点有一个顶点结点，顶点结点结构为：
data firstedge
其中,ivex和 jvex为该边所依附的两个顶点。
ilink指向下一条依附于顶点 ivex的边。
jlink指向下一条依附于顶点 jvex 的边。
data存放顶点的信息。
firstedge指向第一条依附于该顶点的边结点。
（形式化定义见书 P167.）
7.2 图的存储结构四、邻接多重表如图 G2的邻接多重表,
① ②G2
③
④ ⑤
2
5
3
4
1 1 2
3 2
5 2
5 4
3 4
3 5
7.2 图的存储结构四、邻接多重表如图 G2的邻接多重表,
特点：顶点结点数为 n，边结点数为 e；
对需要得到边的两个顶点的一类操作很方便
（如删除一条边，判一条边是否已访问）。
① ②G2
③
④ ⑤
2
5
3
4
1 1 2
3 2
5 2
5 4
3 4
3 5
7.3 图的遍历从图中某个顶点出发，沿路径使图中 每个顶点 被访问且仅被访问一次 的过程，称为 遍历图 。
两种常用遍历图的方法深度优先搜索广度优先搜索
7.3 图的遍历一、深度优先搜索（ depth-first-search)
1,深度优先搜索法遍历图的过程为：
访问指定的某顶点 V，将 V作为当前顶点
将该顶点作为当前顶点，访问当前顶点的下一未被访问过的邻接点
重复 2，直到当前顶点的所有邻接点都被访问点。
沿搜索路径回退，退到尚有邻接点未被访问过的某结点，将该结点
作为当前结点，重复以上步骤，直到所有顶点被访问过的为止
7.3 图的遍历一、深度优先搜索（ depth-first-search)
如图 G4：
V1
V2 V3
V4 V5 V6 V7
V8
深到底 回退深到底
V1V2V4V8V5
（ V2V8均已访问） 深到底
V3V6V7
回退访问
7.3 图的遍历一、深度优先搜索（ depth-first-search)
深度优先搜索递归过程：
void traver(Graph g)
{ for( v=1;v<g.vexnum;v++) visited[v]=FALSE;//访问标志数组初始化
for( v=1;v<g.vexnum;v++)
if (!visited[v]) dfs(g,v) //dfs是以 v 为出发点，遍历一个连通分量
}//traver
void dfs(Graph g,int v) //从第 v个顶点出发递归的深度优先遍历图 g
{visit(v); visited[v]=TRUE;
w= FIRSTADJ(g,v); //找 v 的第一个邻接点
while (w!=0)
{ if (!visited[w]) dfs(g,w);
w=NEXTADJ(g,v,w) //找 v 的 w之后的下一邻接点
}
}//dfs
7.3 图的遍历一、深度优先搜索（ depth-first-search)
深度优先搜索递归过程：
几点说明：
visited[1..n]是一个辅助数组，记载顶点是否被访问过
visited[v]=
true,已访问过
false,未访问过（初值）
FIRSTADJ(g,v)和 NEXTADJ（ g,v,w） 函数的实现与图的具体存储结构有关
7.3 图的遍历
2,深度优先搜索递归过程,图若采用邻接表存储
int FIRSTADJ(g,v0) //找与 vo邻接的第一个顶点,不存在返回 0
Graph g;int v0;
{ p=adjlist[v0].firstarc;
if (p==NULL) return 0;
else return p->adjvex)
}//FIRSTADJ
Int NEXTADJ(g,v0,w)//找 V0 的 w之后的下一邻接点,不存在返回 0
Graph g;int v0,w;
{ p=adjlist[vo].firstarc;
while (!p&& (p->adjvex!=w)) p= p->nextarc; //将移动指针定位到 w
if ((p==NULL)|| (p->nextarc==NUUL)) return 0;
else return p->nextarc->adjvex);
} //NEXTADJ
7.3 图的遍历
2,深度优先搜索递归过程：
void traver(Graph g)
{ for( v=1;v<g.vexnum;v++) visited[v]=FALSE;//访问标志数组初始化
for( v=1;v<g.vexnum;v++)
if (!visited[v]) dfs(g,v) //dfs是以 v 为出发点，遍历一个连通分量
}//traver
void dfs(Graph g,int v) //从第 v个顶点出发递归的深度优先遍历图 g
{visit(v); visited[v]=TRUE;
w= FIRSTADJ(g,v); //找 v 的第一个邻接点
while (w!=0)
{ if (!visited[w]) dfs(g,w);
w=NEXTADJ(g,v,w) //找 v 的 w之后的下一邻接点
}
}//dfs
思考,traver调用 dfs的次数由什么决定？
图若采用邻接矩阵存储,编写相应的 FIRSTADJ(g,V0)和
NEXTADJ(g,V0,w)
7.3 图的遍历二、广度优先搜索（ breadth-first-search)
首先访问指定 顶点 v0，将 v0作为当前顶点 ;
访问当前顶点的 所有未访问过的邻接点,
并依次将访问的这些邻接点作为当前顶点 ;
重复 2,直到 所有顶点 被访问为止。
对右图广度优先搜索，访问顶点序列为：
V1 V2 V3 V4 V5 V6 V7 V8
V1
V2 V3
V4 V5 V6 V7
V8
7.3 图的遍历广度优先搜索算法：
Void bfs(Graph g,int vo)
{ visit(vo); visited[vo]=TRUE;
INIQUEUE(Q); ENQUEUE(Q,vo);
while (!EMPTY(Q))
{ v=DLQUEUE(Q);
w=FIRSTADJ(g,v);
while (w<>0)
{ if (!visited[w])
{ visit(w); visited[w]=TRUE;
ENQUEWE(Q,w)； }
w=NEXTADJ(g,v,w) ； }
} //bfs
图的定义
图的存储结构
图的遍历
图的应用
7.1 图的定义和术语
1,图有向图（ Digragh）
无向图（ Undigraph）
图也是一种非线性地数据结构其抽象数据类型见书 P156.
7.1 图的定义和术语
有向图（ Digragh）
G=（ V,{A}）
其中,V为顶点的有穷非空集合
{A}为顶点之间的关系集合
G1=（ V,{A}）
V={v1,v2,v3,v4}
A={<v1,v2>,<v1,v3>,<v3,v4>,<v4,v1>}
其中 <x,y>表示从 x到 y的一条弧（ arc）,A为弧集合,x为弧尾（ tail）,y为弧头（ head)
① ②
③ ④
G1
7.1 图的定义和术语
无向图（ Undigraph）
G=(V,{E})
其中,V同有向图,{E}为顶点之间的关系集合,
E为边集合
G2=（ V,{A}）
V={v1,v2,v3,v4,v5}
E={(v1,v2),(v1,v4),(v2,v3),(v3,v4),(v2,v5),(v3,v5)}
其中,(x,y)表示 x与 y之间的一条连线，称为边（ edge）
① ②G2
③
④ ⑤
7.1 图的定义和术语设 n为顶点数,e为边或弧的条数对 无向图 有,0<=e<=n(n-1)/2
有向图 有,0<=e<=n(n-1)
证明：每个顶点至多有 n-1条边与其它的 n-1个顶点相连，则 n个顶点至多有 n(n-1)条边 。 但每条边连接 2个顶点，故最多为 n(n-1)/2
7.1 图的定义和术语
2,完全图边达到最大的图
无向完全图,边数为 n(n-1)/2的无向图
有向完全图,弧数为 n(n-1)的有向图权,与图的边或弧相关的数网,边或弧上带有权值的图
7.1 图的定义和术语
3,顶点的度 TD（ V）
无向图,为依附于顶点 V的边数有向图,等于以顶点 V为弧头的弧数（称为 V的 入度，记为 ID（ V））与以顶点 V为弧尾的弧数（称为 V
的出度，记为 OD（ V））之和。即：
TD（ V） =ID（ V） +OD（ V）
无向图
n
e= 1/2（ ∑ TD(vi)）
i=1
结论：
有向图
n n
e= ∑ ID(vi)=∑ OD(vi)
i=1 i=1
无向图的度数为依附于顶点 v
的边数；有向图的度数等于以顶点 v 为弧头的弧数与以顶点 v
为弧尾的弧数之和
7.1 图的定义和术语
4,路径无向图,顶点 v到 v’的路径是一个顶点序列（ v=vi0,vi1,…,vim=v’）
其中，（ vij-1,vij） ∈ E,1<=j<=m
有向图,顶点 v 到 v’的路径是有向的顶点序列 （ v=vi0,vi1,…,vim=v’）
其中，（ vij-1,vij） ∈ A,1<=j<=m
几个概念：
路径长度,路径上边或弧的数目回路或环,首尾顶点相同的路径，称为回路或环。即：
（ v=vi0,vi1,…,v im=v’=v）
简单路径,路径中不含相同顶点的路径简单回路,除首尾顶点外，路径中不含相同顶点的回路
7.1 图的定义和术语
5,连通顶点连通,若顶点 v到顶点 v’有路径，则称顶点 v与 v’是连通的连 通 图,包括无向连通图和有向连通图无向图,若图中任意两个顶点 vi,vj都是连通的，则称该图是连通图 (vi<>vj)
有向图,若图中任意两个顶点 vi,vj，都存在从 vi到 vj和从
vj到 vi的路径，则称该有向图为强连通图 (vi<>vj)
连通分量：
无向图,无向图中极大连通子图，称为连通分量有向图,有向图中极大强连通子图，称为强连通分量
7.1 图的定义和术语
5,连通连通分量：
① ②
③ ④
G1有两个强连通分量① ②
③ ④
G1
7.1 图的定义和术语
6,生成树定义,设无向图 G是含有 n个顶点 的连通图,则图 G的生成树是含有 n个顶点,且只有 n-1条边 的 连通 子图三要素：
n个顶点
n-1条边连通极小连通子图，
若再加一条边，
必构成环生成树 n-1条边
7.2 图的存储结构图有 数组,邻接表,邻接多重表 和 十字链表 等表示方法一、数组表示法（邻接矩阵）
设图 G=（ V,{E}）有 n个顶点，则 G的邻接矩阵定义为 n阶方阵 A。
其中,A[i,j]= 1 若 （ vi,vj）或 <vi,vj>∈E,i≠j
0 其它例如,G1的邻接矩阵
┌ 0 1 1 0 ┐ A1＝ │ 0 0 0 0 │
│ 0 0 0 1 │ 1 0 0 0
① ②G2
③
④ ⑤
┌ 0 1 0 1 0 ┐ A2＝ │ 1 0 1 0 1 │
│ 0 1 0 1 1 │ 1 0 1 0 0
0 1 1 0 0
无向图的邻接矩阵为对称矩阵
① ②
③ ④
G1
7.2 图的存储结构特点,判定两个顶点 Vi与 Vj是否关联,只需判 A[i,j]是否为 1
顶点的度容易求得,
有向图中,TD(Vi)=OD(Vi)+ID(Vi)
n n
= ∑ A[i,j]+∑ A[j,i]
j=1 j=1
n n
无向图中,TD(Vi)=∑ A[i,j]=∑ A[j,i]
j=1 j=1
即顶点 Vi的度等于邻接矩阵中第 i行（或第 i列）的元素之和（非 0元素个数之和）。
即顶点 Vi的出度为邻接矩阵中第 i行元素之和顶点 Vi的入度为邻接矩阵中第 i列元素之和
7.2 图的存储结构网的邻接矩阵定义为,A[i,j]= Wij,若（ Vi,Vj）或 < Vi,Vj>∈E
,其它
V1 V2
V3 V4
3
52
1
4
┌ 3 2 4 ┐ A＝ │ │
│
5 1
如图：
7.2 图的存储结构形式化定义为：
＃ define INFINITY INT_MAX //最大值 ∞
＃ define MAX_VERTEX_NUM 20 //最大顶点个数
Typedef enum{DG,DN,UDG,UDN} GraphyKind; //有向图、无向图、
//有向网、无向网
typedef struct ArcCell {
VrtType adj; // VrtType是顶点关系类型。对无权图，用 1或 0表示邻接否；
// 对带权图，即为权值类型
InfoType *info; //该弧相关信息指针
} ArcCell,AdjMatrix[MAX_VERTEX_NUM ][MAX_VERTEX_NUM ];
typedef struct
{
VertexType vexs[MAX_VERTEX_NUM ]; //顶点向量
AdjMatrix arcs； //邻接矩阵
int vexnum,arcnum;//图的当前顶点数和弧数
GraphyKind kind；
}MGraph; //广义表类型
7.2 图的存储结构二、邻接表（ adjacency list）
1,无向图邻接表对图中 每个顶点 Vi建立一个单链表，链表中的 结点 表示依附于顶点
Vi的边，每个链表结点为 两个域,adjvex nextarc
其中,邻接点域（ adjvex） 记载与顶点 Vi邻接的顶点信息；
链域（ nextarc） 指向下一个与顶点 Vi邻接的邻接的链表 p结点每个链表附设一个 头结点,头结点结构为,vexdata firstarc
其中,vexdata存放顶点信息（姓名、编号等） ；
fristarc指向链表的第一个结点。
形式化定义见书 P163.
7.2 图的存储结构二、邻接表（ adjacency list）
如图 G2的 邻接表 为：
2
5
3
4
1
5
4
3
5
3
3
4
1
2
2
1
2
1
2
3
4
5
特点：设无向图中顶点数为 n，边数为 e，
则它的邻接表需要 n个头结点和 2e个表结点。
顶点 Vi的度 TD（ Vi） =链表 i中的表结点数。
① ②G2
③
④ ⑤
7.2 图的存储结构二、邻接表（ adjacency list）
2,有向图邻接表与无向图的邻接表结构一样。只是在 第 i条链表 上的结点是以 Vi为弧尾 的各个 弧头顶点
2
3
4
1
4
3
1
21
2
3
4
特点,1,n个顶点,e条弧的有向图，需 n个表头结点,e 个表结点
2,第 i条链表上的结点数，为 Vi的出度
（求顶点的出度易，求入度难）
如图 G1的邻接表为：
① ②
G1③ ④
7.2 图的存储结构二、邻接表（ adjacency list）
3,有向图逆邻接表与无向图的邻接表结构一样。只是在 第 i条链表 上的结点是以 Vi为弧头 的各个 弧尾顶点
12
3
4
1
1
4
3
1
2
3
4
此时，第 i条链表上的结点数，为 Vi的入度如图 G1的逆邻接表为,① ②
G1③ ④
7.2 图的存储结构三、十字链表（ orthogonal list）
十字链表是将有向图的邻接表和逆邻接表结合起来的一种 有向图链式存储结构
1,结点结构有向图的每一条弧有一个 弧结点,每一个顶点必有一个 顶点结点,
其结构为,（形式化定义见书 P165.）
tailvex headvex hlink tlink data firstin firstout
弧结点 顶点结点
tailvex,指示该弧的弧尾顶点；
headvex,指示该弧的弧头顶点；
hlink,指向弧头相同的下一条弧；
tlink,指向弧尾相同的下一条弧
data,存放顶点的有关信息
（如顶点的名称，或位置）
firstin,指向以该顶点为弧头的第一个弧结点；
firstout,指向以该顶点为弧尾的第一个弧结点。
7.2 图的存储结构
2,整体结构
通过 hlink将 弧头相同 的弧连在一个链表上；
通过 tlink将 弧尾相同 的弧连在一个链表上
而 hlink链和 tlink链的头结点就是 顶点结点
3,例 G1的十字链表为：
1
2
3
4
1 2 1 3
4 1
3 4
e13e12
e34
e41
① ②
G1③ ④
7.2 图的存储结构
4,特点：
① 顶点结点数 =顶点数弧结点数 =弧的条数
② 求入度,从顶点 Vi的 firstin出发，沿着弧结点中的 hlink所经过的弧结点数。
求出度,从顶点 Vi的 firstout出发，沿着弧结点中的 tlink
所经过的弧结点数。
7.2 图的存储结构四、邻接多重表邻接多重表是 无向图 的另一种 链式 存储结构。
图的每一条边有一个边结点，边结点的结构为：
ivex ilink jvex jlink
每一个顶点有一个顶点结点，顶点结点结构为：
data firstedge
其中,ivex和 jvex为该边所依附的两个顶点。
ilink指向下一条依附于顶点 ivex的边。
jlink指向下一条依附于顶点 jvex 的边。
data存放顶点的信息。
firstedge指向第一条依附于该顶点的边结点。
（形式化定义见书 P167.）
7.2 图的存储结构四、邻接多重表如图 G2的邻接多重表,
① ②G2
③
④ ⑤
2
5
3
4
1 1 2
3 2
5 2
5 4
3 4
3 5
7.2 图的存储结构四、邻接多重表如图 G2的邻接多重表,
特点：顶点结点数为 n，边结点数为 e；
对需要得到边的两个顶点的一类操作很方便
（如删除一条边，判一条边是否已访问）。
① ②G2
③
④ ⑤
2
5
3
4
1 1 2
3 2
5 2
5 4
3 4
3 5
7.3 图的遍历从图中某个顶点出发，沿路径使图中 每个顶点 被访问且仅被访问一次 的过程，称为 遍历图 。
两种常用遍历图的方法深度优先搜索广度优先搜索
7.3 图的遍历一、深度优先搜索（ depth-first-search)
1,深度优先搜索法遍历图的过程为：
访问指定的某顶点 V，将 V作为当前顶点
将该顶点作为当前顶点，访问当前顶点的下一未被访问过的邻接点
重复 2，直到当前顶点的所有邻接点都被访问点。
沿搜索路径回退，退到尚有邻接点未被访问过的某结点，将该结点
作为当前结点，重复以上步骤，直到所有顶点被访问过的为止
7.3 图的遍历一、深度优先搜索（ depth-first-search)
如图 G4：
V1
V2 V3
V4 V5 V6 V7
V8
深到底 回退深到底
V1V2V4V8V5
（ V2V8均已访问） 深到底
V3V6V7
回退访问
7.3 图的遍历一、深度优先搜索（ depth-first-search)
深度优先搜索递归过程：
void traver(Graph g)
{ for( v=1;v<g.vexnum;v++) visited[v]=FALSE;//访问标志数组初始化
for( v=1;v<g.vexnum;v++)
if (!visited[v]) dfs(g,v) //dfs是以 v 为出发点，遍历一个连通分量
}//traver
void dfs(Graph g,int v) //从第 v个顶点出发递归的深度优先遍历图 g
{visit(v); visited[v]=TRUE;
w= FIRSTADJ(g,v); //找 v 的第一个邻接点
while (w!=0)
{ if (!visited[w]) dfs(g,w);
w=NEXTADJ(g,v,w) //找 v 的 w之后的下一邻接点
}
}//dfs
7.3 图的遍历一、深度优先搜索（ depth-first-search)
深度优先搜索递归过程：
几点说明：
visited[1..n]是一个辅助数组，记载顶点是否被访问过
visited[v]=
true,已访问过
false,未访问过（初值）
FIRSTADJ(g,v)和 NEXTADJ（ g,v,w） 函数的实现与图的具体存储结构有关
7.3 图的遍历
2,深度优先搜索递归过程,图若采用邻接表存储
int FIRSTADJ(g,v0) //找与 vo邻接的第一个顶点,不存在返回 0
Graph g;int v0;
{ p=adjlist[v0].firstarc;
if (p==NULL) return 0;
else return p->adjvex)
}//FIRSTADJ
Int NEXTADJ(g,v0,w)//找 V0 的 w之后的下一邻接点,不存在返回 0
Graph g;int v0,w;
{ p=adjlist[vo].firstarc;
while (!p&& (p->adjvex!=w)) p= p->nextarc; //将移动指针定位到 w
if ((p==NULL)|| (p->nextarc==NUUL)) return 0;
else return p->nextarc->adjvex);
} //NEXTADJ
7.3 图的遍历
2,深度优先搜索递归过程：
void traver(Graph g)
{ for( v=1;v<g.vexnum;v++) visited[v]=FALSE;//访问标志数组初始化
for( v=1;v<g.vexnum;v++)
if (!visited[v]) dfs(g,v) //dfs是以 v 为出发点，遍历一个连通分量
}//traver
void dfs(Graph g,int v) //从第 v个顶点出发递归的深度优先遍历图 g
{visit(v); visited[v]=TRUE;
w= FIRSTADJ(g,v); //找 v 的第一个邻接点
while (w!=0)
{ if (!visited[w]) dfs(g,w);
w=NEXTADJ(g,v,w) //找 v 的 w之后的下一邻接点
}
}//dfs
思考,traver调用 dfs的次数由什么决定？
图若采用邻接矩阵存储,编写相应的 FIRSTADJ(g,V0)和
NEXTADJ(g,V0,w)
7.3 图的遍历二、广度优先搜索（ breadth-first-search)
首先访问指定 顶点 v0，将 v0作为当前顶点 ;
访问当前顶点的 所有未访问过的邻接点,
并依次将访问的这些邻接点作为当前顶点 ;
重复 2,直到 所有顶点 被访问为止。
对右图广度优先搜索，访问顶点序列为：
V1 V2 V3 V4 V5 V6 V7 V8
V1
V2 V3
V4 V5 V6 V7
V8
7.3 图的遍历广度优先搜索算法：
Void bfs(Graph g,int vo)
{ visit(vo); visited[vo]=TRUE;
INIQUEUE(Q); ENQUEUE(Q,vo);
while (!EMPTY(Q))
{ v=DLQUEUE(Q);
w=FIRSTADJ(g,v);
while (w<>0)
{ if (!visited[w])
{ visit(w); visited[w]=TRUE;
ENQUEWE(Q,w)； }
w=NEXTADJ(g,v,w) ； }
} //bfs
