数据结构-基于C语言的描述第2版课件 第7章 图

DATASTRUCTUREDATASTRUCTUREDataStructureBYPENGBO

图是一类非常重要的非线性结构，是计算机应用中对实际问题进行数学抽象和描述的强有力工具。图论是专门研究图性质一个数学分支，注重研究图的纯数学性质；而数据结构中对图讨论侧重在计算机中如何表示图及实现图的操作和应用等。第7章主要内容图第章7《数据结构–基于C语言的描述》（第2版）-清华大学出版社DATASTRUCTUREDATASTRUCTUREDataStructureBYPENGBO第7章主要内容7.1

图的类型定义7.2

图的存储表示与操作实现7.3

图的连通性及其应用7.4

有向无环图及其应用7.5

最短路径及其应用《数据结构–基于C语言的描述》-清华大学出版社图第章77.1图的类型定义

在线性结构中，元素之间仅有线性关系；在树形结构中，元素之间有着明显的层次关系；而在图形结构中，结点之间的关系可以是任意的，任意两个元素之间都可能相关。

7.1图的类型定义7.1.1图的定义

图G由两个集合V和VR组成，记为：G=(V,VR)。其中：V是顶点的有穷非空集合，VR是V中顶点偶对的有穷集，顶点偶对称为边或弧。

在图中，如果不存在顶点到其自身的边，且同一条边不重复出现，则称这样的图为简单图。

非简单图同一条边重复出现v1v2v4v5v3存在顶点到其自身的边v1v2v3v4●

无向图和有向图●

无向完全图和有向完全图●

邻接和依附●

稀疏图和稠密图●

顶点的入度、出度和度●

权和网●

路径、路径长度和回路●

子图●

连通图和连通分量●

强连通图和强连通分量●

生成树和生成森林●

顶点的位置7.1图的类型定义7.1.1图的定义●相关概念●

无向图和有向图●无向完全图和有向完全图●邻接和依附●稀疏图和稠密图●顶点的入度、出度和度●权和网●路径、路径长度和回路●子图●连通图和连通分量●强连通图和强连通分量●生成树和生成森林●顶点的位置7.1图的类型定义7.1.1图的定义●相关概念无向图v1v2v4v5v3若顶点vi

和vj

的边无方向，则称无向边(vi,vj)，该图称为无向图。有向图v1v2v3v4若顶点vi

和vj

的边有方向，则称有向边<vi,vj>，该图称为有向图。●无向图和有向图●

无向完全图和有向完全图●邻接和依附●稀疏图和稠密图●顶点的入度、出度和度●权和网●路径、路径长度和回路●子图●连通图和连通分量●强连通图和强连通分量●生成树和生成森林●顶点的位置7.1图的类型定义7.1.1图的定义●相关概念无向完全图v1v2v4v5v3含有n个顶点的无向完全图有n

(n-1)/2条边。在无向图中若任意两顶点间都存在边，则称为无向完全图。在有向图中若任意两顶点间都存在方向互反两条边，则称为有向完全图。有向完全图v1v2v3v4含有n个顶点的有向完全图有n

(n-1)条边。●无向图和有向图●无向完全图和有向完全图●

邻接和依附●稀疏图和稠密图●顶点的入度、出度和度●权和网●路径、路径长度和回路●子图●连通图和连通分量●强连通图和强连通分量●生成树和生成森林●顶点的位置在无向图中，对任意两个顶点vi

和vj，若存在(vi,vj)∈VR，则称vi

和vj

互为邻接点，(vi,vj)依附于vi

和vj。7.1图的类型定义7.1.1图的定义●相关概念v1v2v3v4

顶点v1

邻接到v2，v2

邻接于v1；<v1,v2>依附于顶点v1

和v2。在有向图中，对任意两个顶点vi

和vj，若存在<vi,vj>∈VR，则称vi

邻接到vj，vj

邻接自vi，<vi,vj>依附于vi

和vj。●无向图和有向图●无向完全图和有向完全图●邻接和依附●

稀疏图和稠密图●顶点的入度、出度和度●权和网●路径、路径长度和回路●子图●连通图和连通分量●强连通图和强连通分量●生成树和生成森林●顶点的位置7.1图的类型定义7.1.1图的定义●相关概念如果用e表示图中的边数，则e<nlogn的图称为稀疏图；反之称为稠密图。●无向图和有向图●无向完全图和有向完全图●邻接和依附●稀疏图和稠密图●

顶点的入度、出度和度●权和网●路径、路径长度和回路●子图●连通图和连通分量●强连通图和强连通分量●生成树和生成森林●顶点的位置7.1图的类型定义7.1.1图的定义●相关概念无向图中顶点v3

的度为3，即D(V3)=3。v1v2v4v5v3在无向图中顶点v的度指依附于该顶点的边的个数，记为D(v)。v2v3v4v1v1在有向图中顶点v入度指以该顶点为头的边个数，记为ID(v)；顶点v出度指以该顶点为尾的边个数，记为OD(v)。入度+出度=顶点度。有向图中顶点v1

的入度为1，出度为2，v1

的度为3。●无向图和有向图●无向完全图和有向完全图●邻接和依附●稀疏图和稠密图●顶点的入度、出度和度●

权和网●路径、路径长度和回路●子图●连通图和连通分量●强连通图和强连通分量●生成树和生成森林●顶点的位置7.1图的类型定义7.1.1图的定义●相关概念无向网v1v2v4v5v3101251188有向网v1v2v3v48529在图中，权通常是指对边赋予的有意义的数值量。边上带权的图称为网。●无向图和有向图●无向完全图和有向完全图●邻接和依附●稀疏图和稠密图●顶点的入度、出度和度●权和网●

路径、路径长度和回路●子图●连通图和连通分量●强连通图和强连通分量●生成树和生成森林●顶点的位置7.1图的类型定义7.1.1图的定义●相关概念v1v2v3v4(v1,v3,v4,v1,v2)是一条有向路径，但不是简单路径，长度为4。(v1,v3,v4)是一条简单有向路径，长度为2。(v1,v3,v4,v1)是一条简单有向回路，长度为3。在图G=(V,VR)中，vi

到vj

的顶点序列称为路径。路径上边的数目称为路径长度。第一个顶点和最后一个顶点相同的路径称为回路。在路径序列中，顶点不重复出现的路径称为简单路径。除第一个和最后一个顶点外，其余顶点不重复出现的回路称为简单回路。●无向图和有向图●无向完全图和有向完全图●邻接和依附●稀疏图和稠密图●顶点的入度、出度和度●权和网●路径、路径长度和回路●

子图●连通图和连通分量●强连通图和强连通分量●生成树和生成森林●顶点的位置7.1图的类型定义7.1.1图的定义●相关概念无向图G1

及其一个子图v1v2v5v3v1v2v4v5v3G1G1的一个子图对于图G=(V,VR)，G'=(V',VR')，如果V'

V且VR'

VR，则称G'是G的子图。v1v3v4v1v2v3v4G2G2的一个子图有向图G2

及其一个子图●无向图和有向图●无向完全图和有向完全图●邻接和依附●稀疏图和稠密图●顶点的入度、出度和度●权和网●路径、路径长度和回路●子图●

连通图和连通分量●强连通图和强连通分量●生成树和生成森林●顶点的位置7.1图的类型定义7.1.1图的定义●相关概念v1v2v4v5v3连通图在无向图中，若任意两个顶点vi和vj(i≠j)之间有路径，则称该图是连通图。非连通图ABDECFHGLJKHGLKFABDECJ非连通图的三个连通分量非连通图的极大连通子图称为连通分量。●无向图和有向图●无向完全图和有向完全图●邻接和依附●稀疏图和稠密图●顶点的入度、出度和度●权和网●路径、路径长度和回路●子图●连通图和连通分量●

强连通图和强连通分量●生成树和生成森林●顶点的位置7.1图的类型定义7.1.1图的定义●相关概念强连通图v1v2v3v4非强连通图v1v2v3v4v1v3v4v2非强连通图的两个强连通分量在有向图中，对任意两个顶点vi

和vj（i≠j），如果从vi

和vj均有路径，则称该图是强连通图。非强连通图的极大连通子图称为强连通分量。●无向图和有向图●无向完全图和有向完全图●邻接和依附●稀疏图和稠密图●顶点的入度、出度和度●权和网●路径、路径长度和回路●子图●连通图和连通分量●强连通图和强连通分量●

生成树和生成森林●顶点的位置7.1图的类型定义7.1.1图的定义●相关概念ABDECJ连通图具有n个顶点连通图G的生成树是一个极小连通子图，它含有图中全部顶点和n-1条边。ABDECJ连通图的一棵生成树非连通图图中有环

若一个图有n个顶点且有小于n-1条边则是非连通图。

若一个图有n个顶点且有多于n-1条边则一定有环。切记：有n-1条边的图不一定是生成树！不是生成树●无向图和有向图●无向完全图和有向完全图●邻接和依附●稀疏图和稠密图●顶点的入度、出度和度●权和网●路径、路径长度和回路●子图●连通图和连通分量●强连通图和强连通分量●

生成树和生成森林●顶点的位置7.1图的类型定义7.1.1图的定义●相关概念非连通图ABLMCFHGIK非连通图的生成森林BMFLACGIKH在非连通图中，由每个连通分量都可以得到一棵生成树，这些连通分量的生成树构成了该非连通图的生成森林。7.1图的类型定义7.1.1图的定义将图中顶点按任意顺序排列起来，即用顶点的存储顺序表示该顶点在图中的位置。●无向图和有向图●无向完全图和有向完全图●邻接和依附●稀疏图和稠密图●顶点的入度、出度和度●权和网●路径、路径长度和回路●子图●连通图和连通分量●强连通图和强连通分量●生成树和生成森林●

顶点的位置●

无向图和有向图●

无向完全图和有向完全图●

邻接和依附●

稀疏图和稠密图●

顶点的入度、出度和度●

权和网●

路径、路径长度和回路●

子图●

连通图和连通分量●

强连通图和强连通分量●

生成树和生成森林●

顶点的位置7.1图的类型定义7.1.2图的抽象数据类型ADTGraph{Data： 具有相同类型的数据元素的集合，称为顶点集。

Relation： R={E} E={<v,w>|v,w∈V且P(v,w)，<v,w>表示从v到w边，P(v,w)定义了<v,w>的意义或信息}

Operation：

CreateGraph(&G,V,VR)

初始条件：V是图中顶点集合，VR是图中顶点偶对集合。 操作结果：按照V和VR的定义构造图G。

…… DFSTraverse(G,v)

初始条件：图G已经存在，v是G中某个顶点。 操作结果：从v起深度优先访问G。

BFSTraverse(G,v)

初始条件：图G已经存在，v是G中某个顶点。 操作结果：从v起广度优先访问G。}ADTGraph

图中最基本的操作是遍历。它是指从图中某一顶点出发，对图中所有顶点访问一次且仅访问一次。7.1图的类型定义7.1.3图的遍历

在图中，没有一个确定的开始顶点，任意一个顶点都可以作为遍历的起始顶点，那么如何选取遍历的起始顶点？

在图中，从某个顶点出发可能到达不了所有其他顶点，如非连通图，那么如何才能遍历图的所有顶点？

在图中，由于可能存在回路，某些顶点会被重复访问，那么如何避免遍历不会因回路而陷入死循环？

在图中，一个顶点可以和其他多个顶点相邻接，当这样的顶点访问过后，如何选取下一个要访问的顶点？

可以从图中任一顶点出发，例如按编号的顺序，先从编号小的顶点开始。

可以多次调用从图中某一个顶点出发遍历图的算法。

可以设置一个访问标志数组，初值为0，若某顶点已被访问，则将该顶点访问标志置为1。

可以通过规定图的遍历次序解决，通常有深度优先遍历和广度优先遍历两种方式。

7.1图的类型定义7.1.3图的遍历●深度优先遍历

方法：是一个递归过程，采用递归方法完成操作。图的深度优先遍历类似于树的先序遍历。

定义：从图中某顶点v出发：访问顶点v；从v的未被访问邻接点中选取一个顶点w，从w出发深度优先遍历；重复上述两步，直至图中所有和v有路径相通的顶点都被访问到。无向图从v1出发得到一个深度优先遍历序列：v1v2v3v4v5v6

7.1图的类型定义7.1.3图的遍历●广度优先遍历

方法：以顶点v为起始点，由近至远，依次访问和v有路径相通且路径长度分别为1，2，…的顶点。图的广度优先遍历类似于树的层序遍历。

定义：从图中某顶点v出发：访问顶点v；依次访问v的各个未被访问的邻接点v1，v2，…，vk；

分别从v1，v2，…，vk

出发，依次访问其未被访问邻接点，并使“先被访问顶点的邻接点”先于“后被访问顶点的邻接点”被访问。直至图中所有与v有路径相通的顶点都被访问到。

为使“先被访问顶点的邻接点”先于“后被访问顶点的邻接点”被访问，需附设一个队列，存储已被访问的路径长度为1、2、…的顶点。7.1图的类型定义7.1.3图的遍历●广度优先遍历

方法：以顶点v为起始点，由近至远，依次访问和v有路径相通且路径长度分别为1，2，…的顶点。图的广度优先遍历类似于树的层序遍历。

定义：从图中某顶点v出发：访问顶点v；依次访问v的各个未被访问的邻接点v1，v2，…，vk；

分别从v1，v2，…，vk

出发，依次访问其未被访问邻接点，并使“先被访问顶点的邻接点”先于“后被访问顶点的邻接点”被访问。直至图中所有与v有路径相通的顶点都被访问到。

无向图从v1出发得到一个广度优先遍历序列：v1v2v3v6v5v4

7.2图的存储表示与操作实现

一个图包括两部分信息：顶点的信息以及描述顶点之间关系的信息。因此图的存储结构除了要求能存储各顶点的信息外，还要求能唯一地反映图中各顶点之间的逻辑关系。

7.2图的存储表示与操作实现7.2.1图的存储结构常用的存储结构：●

邻接矩阵●

邻接表●

十字链表●

邻接多重表7.2图的存储表示与操作实现

用一个一维数组存储图中顶点的信息，一个二维数组存储图中边（或弧）的信息，该二维数组称为图的邻接矩阵。

●

如果G=(V,E)是一个图，含有n个顶点，则G的邻接矩阵是具有如下性质的n阶方阵：

●

如果G=(V,E)是一个网，含有n个顶点，则G的邻接矩阵是具有如下性质的n阶方阵：7.2.1图的存储结构●邻接矩阵

定义7.2图的存储表示与操作实现7.2.1图的存储结构●邻接矩阵

定义7.2图的存储表示与操作实现7.2.1图的存储结构●邻接矩阵

类型定义#defineInfinityMAX //最大值∞#defineVertex_Max 20 //最大顶点个数typedefenum{DG,DN,UDG,UDN}GraphKind //有向图(网)，无向图(网)typedefstruct{ElemTypevexs[Vertex_Max]; //顶点数组VRTypeedges[Vertex_Max][Vertex_Max]; //邻接矩阵intvexnum;edgenum; //当前顶点数和边数（或弧）GraphKindkind; //图的种类标志}MGraph;

7.2图的存储表示与操作实现7.2.1图的存储结构●邻接矩阵

主要特点求顶点的度：无向图：有向图：求顶点的邻接点：易判断vi

和vj

之间是否存在边及寻找vi

的所有邻接点。存储空间：S(n)=O(n2)。无向图的邻接矩阵对称，可采用压缩存储。7.2图的存储表示与操作实现7.2.1图的存储结构●邻接表

定义

对于图中每个顶点vi

建立一个链表，第i个链表中的结点表示依附于vi

的边；每个链表上附设一个表头结点，为了随机访问任一顶点的链表，这些表头结点通常以顺序结构方式存储。采用这种存储结构的图称为邻接表。

在邻接表存储结构中存在两种结点：头结点和表结点。vexfirstedge数据域链域头结点结构存放顶点vi

的信息指向边表第一个表结点表结点结构adjvexnextedgeweight链域邻接点域权值域

存放与vi

相邻接的顶点在顶点表中下标；

存放网中边的权值(图无此域)。指向边表中的下一个结点7.2图的存储表示与操作实现7.2.1图的存储结构●邻接表

定义v0v1v3v4v2G1无向图G1

及邻接表v013v1v2v3v4024134021201234∧∧∧∧∧G2v0v1v2v3有向图G2

及邻接表

v012v1v2v330∧0123∧∧∧7.2图的存储表示与操作实现7.2.1图的存储结构●邻接表

类型定义#defineVertex_Max20 //最大顶点个数typedefenum{DG,DN,UDG,UDN}GraphKind //有向图(网)，无向图(网)typedefstructEdgeNode{ //表结点int adjvex; //该边所指向的顶点的位置

structEdgeNode*nextedge; //指向下一条边（或弧）

int weight; //若是网则存放权值，若是图则无此域}EdgeNode;typedefstructVexNode{ //头结点ElemType vex; //顶点信息

EdgeNode *firstedge; //指向第一条依附于该顶点的边（或弧）}VexNode;typedefstruct{ //邻接表VexNode vexs[Vertex_Max]; //顶点数组

int vexnum,edgenum; //当前顶点数和边数（或弧数）

GraphKind

kind; //图的种类标志}ALGraph;7.2图的存储表示与操作实现7.2.1图的存储结构●邻接表

主要特点

求顶点的度：无向图：vi

的度为第i个链表中结点数。v0v1v3v4v2v013v1v2v3v4024134021201234∧∧∧∧∧无向图及邻接表例如：v1

的度为第1个链表的结点数，即3。例如：v0

的出度为第0个链表的结点数，即2；遍历邻接表后得到v0

的入度，即1。

为了便于确定顶点入度或以vi

为头的弧，可以建立一个有向图的逆邻接表，即对每个顶点vi

将所有以vi

为弧头的弧链接起来。有向图及邻接表

有向图及逆邻接表

7.2图的存储表示与操作实现7.2.1图的存储结构●邻接表

主要特点

求顶点的度：无向图：vi

的度为第i个链表中结点数。v021v1v2v330∧0123∧∧∧v0v1v2v301230∧2∧0∧3∧v0v1v2v3

有向图：第i个链表中结点数是vi

的出度，但求入度需遍历邻接表。

求顶点的度：无向图：vi

的度为第i个链表中结点数。

有向图：第i个链表中结点数是vi

的出度，但求入度需遍历邻接表。7.2图的存储表示与操作实现7.2.1图的存储结构●邻接表

主要特点

求顶点的邻接点：容易找到任一顶点第一个和下一个邻接点，但要判定vi和vj间是否存在边，则需搜索第i或第j个链表。

存储空间：图中有n个顶点e条边，有向图需(n+e)个结点空间，无向图需(n+2e)个结点空间；因此S(n)=O(n+e)。

7.2图的存储表示与操作实现7.2.1图的存储结构头结点结构●十字链表

定义

十字链表是有向图的另一种存储表示，可以看成是将有向图的邻接表与逆邻接表结合起来得到的一种存储结构。

在十字链表中存在两种结点：头结点（顶点信息）和表结点（边信息）。顶点域尾指针域vexfirstinfirstout头指针域存放顶点信息存放以该顶点为头的第一个边结点指针存放以该顶点为尾的第一个边结点指针表结点结构头域尾域权域headvexhlinktlinktailvexweight头链域尾链域存放边尾顶点序号存放边头顶点序号存放边头相同的下一条边的边结点指针存放边尾相同的下一条边的边结点指针存放网中边的权值（图无此域）7.2图的存储表示与操作实现7.2.1图的存储结构●十字链表

定义2026/11/7v0v1v2v3有向图G有向图G的十字链表v0v1v2v30123∧0102∧2023∧∧303132∧∧∧∧7.2图的存储表示与操作实现7.2.1图的存储结构●十字链表

类型定义#defineVertex_Max20typedefstructArcBox{ //表结点int tailvex,headvex; //该弧的弧尾和弧头顶点的位置

structArcBox*hlink,*tlink; //分别指向弧头和弧尾相同的下一条弧

intweight; //若是网则存放权值，若是图则无此域}ArcBox;typedefstructVexNode{ //头结点ElemType vex; //顶点信息

ArcBox *firstin,*firstout; //分别指向该顶点第一条入弧和出弧}VexNode;typedefstruct{ //十字链表VexNode vexs[Vertex_Max]; //顶点数组

int vexnum,Arcnum; //当前顶点数和弧数}OLGraph;

7.2图的存储表示与操作实现7.2.1图的存储结构●十字链表

主要特点

在有向图的十字链表存储中容易求解有向图顶点出度和入度。

容易判断有向图中顶点vi

和vj

间是否存在边及寻找顶点vi

的所有邻接点。

如果有向图中有n个顶点e条边，则其空间复杂度为S(n)=O(n+e)。7.2图的存储表示与操作实现7.2.1图的存储结构●邻接多重表

定义

邻接多重表是无向图的另一种存储表示。可以避免由于邻接表重复存储无向图中结点，而给图的某些操作带来的不便。

在邻接多重表中存在两种结点：头结点(顶点信息)和表结点(边信息)。顶点域尾指针域vexfirstedge顶点结点存放顶点信息存放第一条依附于该顶点的边的表结点指针ivexilinkjvexmarkjlinkweight表结点标志域位置域链域位置域链域权域指示该条边是否被搜索过存放该边依附的两个顶点在图中的位置存放下一条依附于顶点ivex和jvex的表结点指针存放网中边的权值(图无此域)7.2图的存储表示与操作实现7.2.1图的存储结构●邻接多重表

定义无向图Gv0v1v3v4v2无向图G的邻接多重表v0v1v2v3v4012340103∧∧2141∧2324∧∧7.2图的存储表示与操作实现7.2.1图的存储结构●邻接多重表

类型定义#defineVertex_Max20typedefstructEdgeBox{ //表结点VisitIF mark; //访问标记

int ivex,jvex; //该边依附的两个顶点的位置

structEdgeBox*ilink,*jlink; //分别指向依附这两个顶点的下一条边

int weight; //若是网则存放权值，若是图则无此域}EdgeBox;typedefstructVexNode{ //头结点ElemType vex; //顶点信息

EdgeBox *firstedge; //指向第一条依附该顶点的边}VexBox;typedefstruct{ //邻接多重表VexBox vexlist[Vertex_Max];

//顶点数组

int vexnum,edgenum; //当前顶点数和边数}AMLGraph; 7.2图的存储表示与操作实现7.2.1图的存储结构●邻接多重表

主要特点

同一条边在邻接表中用两个结点表示，在邻接多重表中只用一个结点。

邻接多重表适合对边的操作。如对标记已访问过的边，删除图中某一条边等。

除了在表结点中增加一个标志域外，邻接多重表所需存储量和邻接表相同。

7.2图的存储表示与操作实现7.2.2图的操作实现●构造图voidCreateGraph(Graph&G){//根据图的种类，调用具体的构造算法

cin>>G.kind;switch(G.kind){ caseDG:CreateDG(G);break; //构造有向图 caseDN:CreateDN(G);break; //构造有向网 caseUDG:CreateUDG_MG(G);break; //构造无向图 caseUDN:CreateUDN_MG(G);break; //构造无向网 default:ErrorMessage("输入的图种类参数不合法！");}}//CreateGraph7.2图的存储表示与操作实现7.2.2图的操作实现●构造图设计

构造无向图的邻接矩阵

输入顶点信息存储在顶点数组中； 初始化邻接矩阵； 依次输入边(vi,vj)，确定该边所依附的两个顶点在图中的位置，并判断该边是否存在，若不存在则重新输入新边，否则构造邻接矩阵。

while((i<0)||(j<0)){cout<<"Theedgedoesn’texist,pleaseinputagain!"<<endl;cin>>v1>>v2;i=LocateVex_MG(G,v1);j=LocateVex_MG(G,v2); }7.2图的存储表示与操作实现7.2.2图的操作实现●构造图

构造无向图的邻接矩阵算法7-1voidCreateUDG_MG(MGraph&G,intn,inte){ //构造n个顶点e条边的无向图G的邻接矩阵；G.kind=UDG

G.vexnum=n;G.edgenum=e;for(i=0;i<G.vexnum;++i)cin>>G.vexs[i]; //构造顶点数组

for(i=0;i<G.vexnum;++i) //初始化邻接矩阵 for(j=0;j<G.vexnum;++j)G.edges[i][j]=0;for(k=0;k<G.edgenum;++k){ //构造邻接矩阵 cin>>v1>>v2;i=LocateVex_MG(G,v1);j=LocateVex_MG(G,v2); G.edges[i][j]=G.edges[j][i]=1; //置邻接矩阵对称元素为1}}//CreateUDG_MGintLocateVex_MG(MGraphG,ElemTypex){//确定x在G中位置

for(k=0;(k<G.vexnum)&&(G.vexs[k]!=x);++k);if(k<G.vexnum)returnk;elsereturn-1;}//LocateVex_MG7.2图的存储表示与操作实现7.2.2图的操作实现●构造图

构造无向图的邻接矩阵分析

假设是图顶点个数为

n，执行时间主要耗费在三个

for循环上：

（1）第一个

for循环（顶点数组初始化）执行次数为

n；

（2）第二个for循环（邻接矩阵初始化）执行次数为

n2；

（3）第三个

for循环（构造邻接矩阵），如果输入的顶点信息即为顶点的编号，则执行次数为e，否则需要通过查找才能得到顶点在图中位置，则执行次数为e

n。

因此算法的时间复杂度为O(n2)。7.2图的存储表示与操作实现7.2.2图的操作实现●构造图

构造有向图的邻接表设计

输入顶点信息存储在顶点数组中

； 依次输入弧<vi,vj>，确定该弧依附的两个顶点在图中位置，并判断该弧是否存在，若不存在则重新输入新弧，否则生成表示该弧的表结点

； 将该表结点插入到第i个链表头部。7.2图的存储表示与操作实现7.2.2图的操作实现●构造图

构造有向图的邻接表算法7-2for(k=0;k<G.edgenum;++k){ //构造邻接表 cin>>v1>>v2;i=LocateVex_ALG(G,v1);j=LocateVex_ALG(G,v2); p=newEdgeNode;p->adjvex=j; //插入p结点到第i个链表 p->nextedge=G.vexs[i].firstedge;G.vexs[i].firstedge=p;}}//CreateDG_ALGvoidCreateDG_ALG(ALGraph&G,intn,inte){//构造n个顶点e条边的有向图G的邻接表，即G.kind=DGG.vexnum=n;G.edgenum=e;for(i=0;i<G.vexnum;++i)

//构造顶点数组

{cin>>G.vexs[i].vex;G.vexs[i].firstedge=NULL;} while((i<0)||(j<0)){ cout<<"Theedgedoesn’texist,pleaseinputagain!"<<endl; cin>>v1>>v2;i=LocateVex_ALG(G,v1);j=LocateVex_ALG(G,v2); }7.2图的存储表示与操作实现7.2.2图的操作实现●构造图

构造有向图的邻接表分析

假设图顶点个数为

n，执行时间主要耗费在两个

for循环上：

（1）第一个

for循环（顶点数组初始化）执行次数为

n；

（2）第二个for循环（构造邻接表），如果输入的顶点信息即为顶点的编号，则执行次数为e，否则需要通过查找才能得到顶点在图中的位置，则执行次数为e

n。

因此算法的时间复杂度为O(e

n)。

深度优先遍历邻接表7.2图的存储表示与操作实现7.2.2图的操作实现算法7-3intvisited[Vertex_Max];

//访问标志数组是全局变量voidDFSTraverse_ALG(ALGraphG){//深度优先遍历以邻接表存储的图Gfor(v=0;v<G.vexnum;++v)visited[v]=0; //访问标志数组初始化for(v=0;v<G.vexnum;++v) //对尚未访问顶点进行搜索 if(!visited[v])DFS_ALG(G,v);}//DFSTraverse_ALGvoidDFS_ALG(ALGraphG,VexTypev){//从顶点v出发深度优先遍历以邻接表存储的图Gcout<<G.vexs[v].vex;visited[v]=1;for(p=G.vexs[v].firstedge;p;p=p->nextedge){ j=p->adjvex; if(!visited[j])DFS_ALG(G,j);}}//DFS_ALG●遍历图7.2图的存储表示与操作实现7.2.2图的操作实现●构造图

深度优先遍历邻接表分析

（1）假设图的顶点个数为

n，图中边（或弧）的数为e，执行时间主要耗费在调用

DFS_ALG上。

（2）当访问某个顶点时，DFS_ALG的执行时间主要耗费在从该顶点出发搜索其所有邻接点上，采用邻接表作为图的存储结构时，对n个顶点访问就需要对所有链表中的e个表结点检查一遍。

因此算法的时间复杂度为O(n+e)。7.2图的存储表示与操作实现7.2.2图的操作实现●遍历图

广度优先遍历邻接矩阵算法7-4voidBFSTraverse_MG(MGraphG){//广度优先遍历以邻接矩阵存储的图Gfor(v=0;v<G.vexnum;++v)visited[v]=0;

//访问标志数组初始化InitQueue_Sq(Q);

//初始化队列Qfor(v=0;v<G.vexnum;++v) if(!visited[v]){

//对尚未访问顶点进行搜索 cout<<G.vexs[v]);visited[v]=1;EnQueue_Sq(Q,v); while(Q.front!=Q.rear){ DeQueue_Sq(Q,u);

for(w=0;w<G.vexnum;w++) if(G.edges[u][w]&&(!visited[w]))

{visited[w]=1;cout<<G.vexs[w]);EnQueue_Sq(Q,w);} } }}//BFSTraverse_MG7.2图的存储表示与操作实现7.2.2图的操作实现●遍历图

广度优先遍历邻接矩阵

DFS和BFS不同之处仅仅在于对顶点访问的顺序不同。

分析（1）假设图的顶点个数为

n，该算法对图中的每个顶点均入队一次；

（2）当访问某个顶点时，执行时间主要耗费在从该顶点出发搜索其所有邻接点上；采用邻接矩阵作为图的存储结构时，查找每个顶点的邻接点所需要的时间为O(n2)。

因此算法的时间复杂度为O(n2)。7.3图的连通性及其应用

在图的应用中，常需要判定给定的无向图是否是一个连通图；对一个非连通图求其连通分量；对一个连通图求其生成树；对一个非连通图求其生成森林等。利用图的遍历算法可以求解这些应用问题。7.3图的连通性及其应用7.3.1无向图的连通分量

判断无向图G是否是连通图：若是，则给出相应信息；若否，则给出连通分量的个数：v0v1v3v4v2无向图计数器=1，连通图设计

设置一个计数器count，初始时取值为0； 每调用一次遍历算法，就使count增1。当对整个图搜索结束时，依据count值确定图是否连通，及连通分量个数。例如：7.3图的连通性及其应用7.3.1无向图的连通分量设计计数器=1无向图v0v1v3v4v2v5v7v6v10v8v9v5v0v1v3v4v2v8v7v6v10v9计数器=2计数器=3无向图有三个连通分量例如：

判断无向图G是否是连通图：若是，则给出相应信息；若否，则给出连通分量的个数：

设置一个计数器count，初始时取值为0； 每调用一次遍历算法，就使count增1。当对整个图搜索结束时，依据count值确定图是否连通，及连通分量个数。7.3图的连通性及其应用7.3.1无向图的连通分量intvisited[Vertex_Max]; //访问标志数组是全局变量voidConnectedUDG_ALG(ALGraphG){//判断无向图G是否是连通图：若是，则给出相应信息；若否，则给出连通分量的个数

for(v=0;v<G.vexnum;++v)visited[v]=0;count=0; //设置计数器初值0算法7-5for(v=0;v<G.vexnum;++v) if(!visited[v]){ //对尚未访问顶点进行搜索 count++; //计数器加1 DFS_ALG(G,v);

//从v出发深度优先遍历邻接表存储的图G， //参见算法7-3 }if(count==1)cout<<"Gisaconnectedgraph!"elsecout<<"Ghas"<<count<<"connectedcomponents!"}//ConnectedUDG_ALGn个顶点e条边，邻接表结构，时间复杂度

O(n+e)。7.3图的连通性及其应用7.3.2生成树和生成森林

对于连通图，由深度优先搜索得到的生成树称为深度优先生成树；由广度优先搜索得到的生成树称为广度优先生成树。

连通图v0v1v6v5v2v8v7v4v3DFS生成树v0v1v6v5v8v7v4v3v2BFS生成树v0v1v6v5v2v8v7v4v3

对于非连通图，每个连通分量中的顶点集，和搜索时走过的边一起构成了若干棵生成树，这些连通分量的生成树组成了非连通图的生成森林。由深度优先搜索得到的为深度优先生成森林，由广度优先搜索得到的为广度优先生成森林。设计7.3图的连通性及其应用7.3.2生成树和生成森林

从v0

出发深度优先遍历以邻接表表示的图，构造以T为根的深度优先生成森林二叉链表。第一次调用构造深度优先生成树算法第二次调用构造深度优先生成树算法第三次调用构造深度优先生成树算法深度优先生成森林的二叉链表v0v1v3v4v2v00v11v22v33v441300∧∧∧∧∧无向图及邻接表v0T∧∧v1∧∧qv2∧∧qv3∧∧qv4∧∧qqT=NULL生成一个结点。

第一棵生成树的根，即T的根。

一个连通图的生成树和一个非连通图的生成森林均不唯一，由遍历得到的生成森林取决于从哪个顶点出发、遍历次序及所用的存储结构。

7.3图的连通性及其应用7.3.2生成树和生成森林算法7-6intvisited[Vertex_Max]; //访问标志数组是全局变量voidDFSForest_ALG(ALGraphG,CSTree&T){//对邻接表表示的图G，构造以T为根的深度优先生成森林的二叉链表

T=NULL;for(v=0;v<G.vexnum;++v)visited[v]=0;for(v=0;v<G.vexnum;++v) if(!visited[v]){ //第v个顶点作为新生成树的根结点 p=newCSNode; //分配根结点

p->data=G.vexs[v].vex; p->firstchild=NULL;p->rightsib=NULL; if(!T)T=p; //第一棵生成树的根，即T的根 elseq->rightsib=p; //其他生成树的根，即前一棵根的兄弟 q=p; //当前生成树的根

DFSTree_ALG(G,v,p); //构造以p为根的深度优先生成树 }}//DFSForest_ALG7.3图的连通性及其应用7.3.2生成树和生成森林算法7-6voidDFSTree_ALG(ALGraphG,intv,CSTree&T){//从第v个顶点出发DFS邻接表表示的图G，构造以T为根深度优先生成树二叉链表

visited[v]=1;first=1; //设first为遍历第一个孩子标志for(p=G.vexs[v].firstedge;p;p=p->nextedge){ w=p->adjvex; if(!visited[w]){ //将第w个顶点作为新的生成树根结点 q=newCSNode; //分配孩子结点

q->data=G.vexs[w].vex;q->firstchild=NULL;q->rightsib=NULL; if(first){ //w是v第一个未被访问邻接点，q是根第一个孩子

T->firstchild=q;first=0;

} elset->rightsib=q; //q是上一个邻接顶点的右兄弟结点 t=q;

DFSTree_ALG(G,w,t);

//从w出发建立深度优先子生成树t }}}//DFSTree_ALGn个顶点e条边，邻接表结构，时间复杂度

O(n+e)。7.3图的连通性及其应用7.3.3最小生成树●最小生成树定义

设G=(V,VR)是一个连通网，生成树T上各边的权值之和称为该生成树的代价，其中：TE表示T的边集，w(u,v)表示边(u,v)的权。在G的所有生成树中，代价最小的生成树称为最小生成树。7.3图的连通性及其应用采用反证法证明，参见教材7.3.3最小生成树根据MST性质给出求最小生成树一般算法描述：（1）针对连通网G，从空树T开始逐条选择并加入n-1条边(u,v)；（2）最终生成一棵含n-1条边最小生成树；（3）当边(u,v)加入T时必须保证T∪{(u,v)}仍是最小生成树的子集。

●最小生成树性质

MST性质：设G=(V,VR)是一个连通网，U是顶点集合V的一个非空子集。如果(u,v)是G中所有的一个顶点在U(u∈U)里、另一个顶点在V(v∈V-U)里的边中具有最小权值的一条边，则必定存在一棵包含边(u,v)的最小生成树。

构造MST常用方法：普里姆算法和克鲁斯卡尔算法。都是对一般算法的求精。GenerieMST(G){//求连通网G的某棵最小生成树

T<-￠; //T初始为空

while(T未形成G的生成树){

找出并输出T的一条边(u,v); //即T∪{(u，v)}仍为MST的子集

T=T∪{(u,v)}; //加入边，扩充T}}7.3图的连通性及其应用7.3.3最小生成树●普里姆算法假设G=(V,VR)是一个连通网，令T=(U,TE)是G的最小生成树，TE是V上最小生成树边的集合。设计

T的初始状态为U={u0}(u0∈V)，TE={}。

重复执行：在所有u∈U，v∈V-U的边(u,v)∈VR中寻找一条代价最小的边(u0,v0)并入集合TE，同时将v0

并入U，直至U=V为止。此时TE中必有n-1条边，则T=(U,TE)为G的最小生成树。

7.3图的连通性及其应用7.3.3最小生成树●普里姆算法设计（1）从U={v0}(v0∈V)，TE={}开始。假设G=(V,VR)是一个连通网，令T=(U,TE)是G的最小生成树，TE是V上最小生成树边的集合。连通网v0v1v6v5v2v8v7v4v327463314182625252212132v0v1v6v5v2v8v7v4v3利用普里姆算法求解的最小生成树

例如：对连通网，从顶点v0

开始，用普里姆算法求最小生成树。（2）重复执行：

在所有从U到V的边中寻找代价最小的边(v0,v1)并入集合TE，v1并入U，U={v0,v1}。

在所有从U到V的边中寻找代价最小的边(v0,v6)并入集合TE，v6并入U，U={v0,v1,v6}。

在所有从U到V的边中寻找代价最小的边(v6,v8)并入集合TE，v8并入U，U={v0,v1,v6,v8}。

在所有从U到V的边中寻找代价最小的边(v8,v4)并入集合TE，v4并入U，U={v0,v1,v6,v8,v4}。

在所有从U到V的边中寻找代价最小的边(v4,v3)并入集合TE，v3并入U，U={v0,v1,v6,v8,v4,v3}。

在所有从U到V的边中寻找代价最小的边(v3,v2)并入集合TE，v2并入U，U={v0,v1,v6,v8,v4,v3,v2}。

在所有从U到V的边中寻找代价最小的边(v2,v7)并入集合TE，v7并入U，U={v0,v1,v6,v8,v4,v3,v2,v7}。

在所有从U到V的边中寻找代价最小的边(v8,v5)并入集合TE，v5并入U，U={v0,v1,v6,v8,v4,v3,v2,v7,v5}。

普里姆算法的关键：如何找到连接U和V-U的最小权值边来扩充生成树T。设当前T中有k个顶点，则所有满足u∈U及v∈V-U的边最多有k

(n-k)条。

利用MST性质构造候选最小权值边集：对应V-U中每个顶点，保留从该顶点到U中各顶点的最小权值边，取候选最小权值边集为V-U中n-k个顶点所关联的n-k条最小权值边的集合。

7.3图的连通性及其应用7.3.3最小生成树●普里姆算法设计7.3图的连通性及其应用7.3.3最小生成树●普里姆算法设计

为表示候选最小权值边集，需附设一个辅助数组closedge。对vi∈V-U，在辅助数组中存在一个分量closedge[i]，包括两个域：struct{ElemType adjvex; //该边依附的在U中的顶点

int lowcost; //该边上的权值}closedge[Vertex_Max];

当closedge[i].adjvex=k时，closedge[i].lowcost=w表明顶点vi

和顶点vk

之间的权值为w。

初始状态时U={v0}，有closedge[0].lowcost=0，表示顶点v0

已加入集合U中，其他的closedge[j].lowcost是顶点v0

到其余各顶点边权值。7.3图的连通性及其应用7.3.3最小生成树●普里姆算法设计

为表示候选最小权值边集，需附设一个辅助数组closedge。对vi∈V-U，在辅助数组中存在一个分量closedge[i]，包括两个域：

不断选取权值最小边(vi,vk)，每选一条边，就将closedge[k].lowcost置为0，表示顶点vk

已加入集合U中。struct{ElemType adjvex; //该边依附的在U中的顶点

int lowcost; //该边上的权值}closedge[Vertex_Max];

之后，修正lowcost域和adjvex域内容： closedge[j].lowcost=min{cost(vk,vj)|vk

U} closedge[j].adjvex=k算法7-77.3图的连通性及其应用7.3.3最小生成树●普里姆算法voidMiniSpanTree_Prim(MGraphG,ElemTypeu){//用普里姆算法从第u个顶点出发构造以邻接矩阵表示的连通网G的最小生成树T并输出各边k=LocateVex(G,u); //确定顶点u在图G中的位置for(j=0;j<G.vexnum;++j)

//数组初始化，{adjvex,lowcost}if(j!=k)closedge[j]={u,G.edges[k][j]};

closedge[k].lowcost=0; //初始，U={u}；for(i=1;i<G.vexnum;++i){

//选择其余G.vexnum-1个顶点k=Minedge(closedge); //选最小权值边，得到对应顶点序号kcout<<closedge[k].adjvex<<G.vexs[k]; //输出最小生成树的边closedge[k].lowcost=0; //将第k个顶点并入U集for(j=0;j<G.vexnum;++j) //新顶点并入U后重新选择最小权值边if(G.edges[k][j]<closedge[j].lowcost)closedge[j]={G.vexs[k],G.edges[k][j]};}}//MiniSpanTree_Prim7.3图的连通性及其应用7.3.3最小生成树●普里姆算法分析

假设连通网G中有n个顶点，算法中有两个for循环：

（1）第一个for循环“进行辅助数组初始化”，其频度为n；

（2）第二个for循环“选择其余G.vexnum-1个顶点”，其频度为n-1。

在第二个for循环中又内嵌了两个内循环：其一是选择最小权值边，得到对应顶点序号，执行次数为n-1；其二是调整辅助数组，执行次数为n。

因此算法的时间复杂度为O(n2)，与连通网中的边数无关，普里姆算法适用于求稠密网的最小生成树。7.3图的连通性及其应用7.3.3最小生成树●普里姆算法例7-1

对于图(a)所示连通网，图(b)~(f)给出了从顶点v0出发，用普里姆算法构造最小生成树的过程；其中，虚线内顶点属于顶点集U，粗边属于边集TE，cost表示候选最小权值边集，cost中黑体表示将要加入TE最短边。普里姆算法构造最小生成树的过程7.3图的连通性及其应用7.3.3最小生成树●普里姆算法例7-1

对于图(a)所示连通网，图(b)~(f)给出了从顶点v0出发，用普里姆算法构造最小生成树的过程；其中，虚线内顶点属于顶