图的定义和术语概要课件

第七章图第七章图

第七章图7.1图的定义和术语7.2图的存储结构7.3图的遍历7.4图的连通性问题7.5有向无环图及应用7.6最短路径第七章图第七章图本章介绍另一种非线性数据结构——图图：是一种多对多的结构关系，每个元素可以有零个或多个直接前趋；零个或多个直接后继；第七章图本章介绍另一种非线性数据结构——图第七章图

学习要点1．熟悉图的各种存储结构及其构造算法，了解实际问题的求解效率与采用何种存储结构和算法有密切联系；2．熟练掌握图的两种遍历：深度优先遍历和广度优先遍历的算法。在学习中应注意图的遍历算法与树的遍历算法之间的类似和差异。树的先根遍历是一种深度优先搜索策略，树的层次遍历是一种广度优先搜索策略3．理解课件中讨论的各种图的算法；

第七章图

学习要点7.1图的定义和术语一图的概念

图G由两个集合构成，记作G=<V,E>其中V是顶点的非空有限集合，E是边的有限集合，其中边是顶点的无序对或有序对集合。例G1=<V1,E1>V1={v1,v2,v3,v4,v5}E1={(v1,v2),(v1,v3),(v2,v3),(v2,v5),(v3,v4),(v3,v5)}G1图示无序对(vi,vj)：用表示顶点vi、vj的线段，称为无向边；

V5V1

V2

V4

V37.1图的定义和术语一图的概念例G1=<V1,E17.1图的定义和术语例G2=<V2,E2>V2={v1,v2,v3,v4}E2={<v1,v2>,<v1,v3>,<v3,v4>,<v4,v1>}G2图示有序对<vi,vj>：用以表示以vi起点、以vj为终点的有向线段，称为有向边或弧；无向图：在图G中，若所有边是无向边，则称G为无向图；有向图：在图G中，若所有边是有向边，则称G为有向图；混和图：在图G中，即有无向边也有有向边，则称G为混合图；

V1

V2

V3

V4V1称为弧尾(初始点)V3称为弧头(终端点)7.1图的定义和术语例G2=<V2,E2>G2图示有序7.1图的定义和术语图的应用举例例1交通图（公路、铁路）顶点：地点边：连接地点的公路交通图中的有单行道双行道，分别用有向边、无向边表示；例2电路图顶点：元件边：连接元件之间的线路例3通讯线路图顶点：地点边：地点间的连线例4各种流程图如产品的生产流程图顶点：工序边：各道工序之间的顺序关系

V5V1

V2

V4

V37.1图的定义和术语图的应用举例V5V1V2V47.1图的定义和术语三图的基本操作1CreateGraph(&G,V,VR);初始条件：V是图的顶点集，VR是图中弧的集合操作结果：按V和VR的定义构造图G2DestroyGraph(&G);初始条件：图G存在操作结果：销毁图G3LocateVex(G,u);初始条件：图G存在，u和G中顶点有相同特征操作结果：若G中存在顶点u，则返回该顶点在图中位置；否则返回其它信息。4GetVex(G,v);初始条件：图G存在，v是G中某个顶点操作结果：返回v的值5PutVex(&G,v,value);初始条件：图G存在，v是G中某个顶点操作结果：对v赋值value7.1图的定义和术语三图的基本操作7.1图的定义和术语6FirstAdjVex(G,v);初始条件：图G存在，v是G中某个顶点操作结果：返回v的第一个邻接顶点。若顶点在G中没有邻接顶点，则返回“空”。7NextAdjVex(G,v,w);初始条件：图G存在，v是G中某个顶点，w是v的邻接顶点。操作结果：返回v的（相对于w的）下一个邻接顶点。若w是v的最后一个邻接点，则返回“空”。8InsertVex(&G,v);初始条件：图G存在，v和图中顶点有相同特征。操作结果：在图G中增添新顶点v9DeleteVex(&G,v);初始条件：图G存在，v和图中顶点有相同特征操作结果：删除G中顶点v及相关的弧7.1图的定义和术语6FirstAdjVex(G,v7.1图的定义和术语10InsertArc(&G,v,w);初始条件：图G存在，v和w是G中两个顶点。操作结果：在G中增添弧<v,w>，若G是无向的，则还增添对称弧<w,v>11DeleteArc(&G,v,w);初始条件：图G存在，v和w是G中两个顶点。操作结果：在G中删除弧<v,w>，若G是无向的，则还删除对称弧<w,v>12DFSTraverse(G,v,Visit());初始条件：图G存在，v是G中某个顶点，Visit是顶点的应用函数。操作结果：从顶点v起深度优先遍历图G，对每个顶点调用函数Visit一次且仅一次。一旦visit()失败，则操作失败13BFSTraverse(G,v,Visit());初始条件：图G存在，v是G中某个顶点，Visit是顶点的应用函数。操作结果：从顶点v起广度优先遍历图G，对每个顶点调用函数Visit一次且一次。一旦visit()失败，则操作失败7.1图的定义和术语10InsertArc(&G,v7.1图的定义和术语图的基本术语1邻接点及关联边

邻接点：边的两个顶点

关联边：若边e=(v,u),则称顶点v、u关联边e（边e依附于顶点v,u)2顶点的度、入度、出度

顶点V的度=与V相关联的边的数目在有向图中：顶点V的出度=以V为起点有向边数

顶点V的入度=以V为终点有向边数顶点V的度=V的出度+V的入度设图G的顶点数为n，边数为e

图的所有顶点的度数和=2*e（每条边对图的所有顶点的度数和“贡献”2度）

e1

V1

V2

V3

V4

V5V1

V2

V4

V37.1图的定义和术语图的基本术语e1V1V2V33有向完全图、无向完全图有向完全图——n个顶点的有向图最大边数是n(n-1)无向完全图——n个顶点的无向图最大边数是n(n-1)/2权(weight)——与图的边或弧相关的数叫~网——带权的图叫~7.1图的定义和术语3有向完全图、无向完全图7.1图的定义和术语7.1图的定义和术语

路径、回路

无向图中的顶点序列v1,v2,…,vk,若(vi,vi+1)E(i=1,2,…k-1),v=v1,u=vk,

则称该序列是从顶点v到顶点u的路径；若v=u，则称该序列为回路；

有向图D=(V，E）中的顶点序列v1,v2,…,vk,若<vi,vi+1>E(i=1,2,…k-1),v=v1,u=vk,则称该序列是从顶点v到顶点u的路径；若v=u，则称该序列为回路；

例在图1中，V1,V2,V3,V4是V1到V4的路径；V1,V2,V3,V4,V1是回路；在图2中，V1,V3,V4是V1到V4的路径；V1,V3,V4,V1是回路；

V5V1

V2

V4

V3

V1

V2

V3

V4图1图27.1图的定义和术语路径、回路V5V1V2V47.1图的定义和术语连通图、（强连通图）

在无（有）向图G=<V,E>中，若对任何两个顶点v、u都存在从v到u的路径，则称G是连通图（强连通图）

V5

V6

V3

V1

V2

V4连通图非连通图

V5V1

V2

V4

V37.1图的定义和术语连通图、（强连通图）V5V6V7.1图的定义和术语子图

设有两个图G=（V，E）、G1=（V1，E1），若V1V，E1E，E1关联的顶点都在V1中，则称G1是G的子图；例图2、图3是图1的子图

V5V1

V2

V4

V3

V5V1

V2

V3

V5V1

V2

V4

V3图1图2图37.1图的定义和术语子图V5V1V2V4V37.1图的定义和术语连通分图（强连通分量）

无向图G的极大连通子图称为G的连通分量极大连通子图意思是：该子图是G连通子图，将G的任何不在该子图中的顶点加入，子图不再连通；有向图D的极大强连通子图称为D的强连通分量极大强连通子图意思是：该子图是D强连通子图，将D的任何不在该子图中的顶点加入，子图不再是强连通的；

V5

V6

V3

V1

V2

V4连通分图7.1图的定义和术语连通分图（强连通分量）V5V67.1图的定义和术语

V5V1

V2

V4

V3

V5V1

V2

V4

V38生成树（

包含无向图G所有顶点的的极小连通子图称为G生成树极小连通子图意思是：该子图是G的连通子图，在该子图中删除任何一条边，子图不再连通，若T是G的生成树当且仅当T满足如下条件T是G的连通子图T包含G的所有顶点T中无回路只有足以构成一棵树的n-1条边7.1图的定义和术语V5V1V2V4V3V5例213213有向完全图无向完全图356例245136图与子图例245136G1顶点2入度：1出度：3顶点4入度：1出度：0例157324G26顶点5的度：3顶点2的度：4例213213有向完全图无向完全图356例245136图与子例157324G26例245136G1路径：1，2，3，5，6，3路径长度：5简单路径：1，2，3，5回路：1，2，3，5，6，3，1简单回路：3，5，6，3路径：1，2，5，7，6，5，2，3路径长度：7简单路径：1，2，5，7，6回路：1，2，5，7，6，5，2，1简单回路：1，2，3，1例157324G26例245136G1路径：1，2，3，5，连通图例245136强连通图356例非连通图连通分量例245136连通图例245136强连通图356例非连通图连通分量例245第七章图7.2图的存储结构数组表示法邻接表第七章图7.2图的存储结构7.2图的存储结构

图是多对多的结构，比线性结构、树结构复杂，所以其存储结构也要复杂些。与线性结构、树结构一样，图的存储结构至少要保存两类信息： 1)顶点的数据2) 顶点间的关系顶点的编号

为了使图的存储结构与图一一对应，在讨论图的存储结构时，首先要给图的所有顶点编号。

本课程介绍两类图的存储结构

数组表示法 邻接表（邻接表，逆邻接表）

设G=<V,E>是图,V={v1,v2,v3,…

vn},设顶点的的角标为它的编号如何表示顶点间的关系？？7.2图的存储结构图是多对多的结构，比线7.2图的存储结构

邻接矩阵：G的邻接矩阵是满足如下条件的n阶矩阵：

一数组表示法数组表示法是图的一种顺序存储结构在数组表示法中，用邻接矩阵表示顶点间的关系A[i][j]=1若(vi,vi+1)E或<vi,vi+1>E0否则

V5V1

V2

V4

V301010010101011010001100011000000001000

V1

V2

V3

V47.2图的存储结构邻接矩阵：G的邻接矩阵是满足如下条7.2图的存储结构数组表示法顶点的存储：用一维数组存储（按编号顺序）顶点间关系：用二维数组存储图的邻接矩阵；012345m-1V1V2V3V4V5存储顶点的一维数组存储邻接矩阵的二维数组010101010101234mm+1m+2m+3m+47.2图的存储结构数组表示法0V1存储顶点的存储邻接矩阵7.2图的存储结构数组表示法类型定义#defineINFINITYINT_MAX#defineMAX_VERTEX_NUM20typedefenum{DG,DN,AG,AN}GraphKind;typedefstructArcCell{VRTypeadj;InfoType*info;}ArcCell,AdjMatrix[MAX_VERTEX_NUM][MAX_VERTEX_NUM]typedefstruct{VetexTypevexs[MAX_VERTEX_NUM];AdjMatrixarc;intvexnum,arcnum;GraphKindkind;}MGraph;7.2图的存储结构数组表示法类型定义7.2图的存储结构设G是Mgraph类型的变量，用于存储无向图，该图有n个顶点，e条边G的图示如下：G.vexsG.arcsG.vexnumG.arcnuG.kindV10neAG顶点数组存储邻接矩阵的二维数组7.2图的存储结构设G是Mgraph类型的变量，用于存7.2图的存储结构无向图数组表示法特点：1）无向图邻接矩阵是对称矩阵，同一条边表示了两次；2）顶点v的度：等于二维数组对应行（或列）中1的个数；3）判断两顶点v、u是否为邻接点：只需判二维数组对应分量是否为1；4）顶点不变，在图中增加、删除边：只需对二维数组对应分量赋值1或清0；5）设存储顶点的一维数组大小为m(m图的顶点数n),G占用存储空间：m+m2；G占用存储空间只与它的顶点数有关，与边数无关；适用于边稠密的图；对有向图的数组表示法可做类似的讨论

7.2图的存储结构无向图数组表示法特点：7.2图的存储结构邻接表邻接表是图的链式存储结构1无向图的邻接表顶点：通常按编号顺序将顶点数据存储在一维数组中；关联同一顶点的边：用线性链表存储

V5V1

V2

V4

V3例

01234m-1V1V2V3V4V513422110043该结点表示边（V1V2）,其中的1是V2在一维数组中的位置7.2图的存储结构邻接表V5V1V2V4V3例7.2图的存储结构图的邻接表类型定义#defineMAX_VERTEX_NUM20typedefstructArcNode{//边（弧）结点的类型定义intadjvex;//边（弧）的另一顶点的在数组中的位置structArcNode*nextarc;//指向下一条边（弧）结点的指针InfoType*info;}ArcNode;typedefstructVNode{//顶点结点和数组的类型定义VertexTypedata;//顶点信息ArcNode*finrstarc;//指向关联该顶点的边（弧）链表}VNode,AjList[MAX_VERTEX_NUM];typedefstruct{AdjListvertices;intvexnum,arcnum;//图的当前顶点数和弧数intkind;//图的种类标志}ALGraph;7.2图的存储结构图的邻接表类型定义7.2图的存储结构设G是ALGraph类型的变量，用于存储无向图G1，该图有n个顶点，e条边G的图示如下：

V5V1

V2

V4

V3无向图G1该结点表示边（V5,V2）,其中的1是V2在一维数组中的位置G.verticesG.vexnumG.arcnuG.kind

012

4m-1V1V2V3V4V5neAatafirstarcadjvexnextarc7.2图的存储结构设G是ALGraph类型的变量，用于7.2图的存储结构无向图的邻接表的特点1）在G邻接表中，同一条边对应两个结点；

2）顶点v的度：等于v对应线性链表的长度；3）判定两顶点v，u是否邻接：要看v对应线性链表中有无对应的结点4）在G中增减边：要在两个单链表插入、删除结点；

7.2图的存储结构无向图的邻接表的特点7.2图的存储结构D.verticesD.vexnumD.arcnuD.kind

V1V2V3V4neDG1230

V1

V2

V3

V4例2有向图的邻接表和逆邻接表1）有向图的邻接表顶点：用一维数组存储（按编号顺序）以同一顶点为起点的弧：用线性链表存储类似于无向图的邻接表，所不同的是：以同一顶点为起点的弧：用线性链表存储7.2图的存储结构D.verticesV1n12307.2图的存储结构2）有向图的逆邻接表顶点：用一维数组存储（按编号顺序）以同一顶点为终点的弧：用线性链表存储表类似于无向图的邻接表，所不同的是：以同一顶点为终点的弧：用线性链表存储D.verticesD.vexnumD.arcnuD.kind

V1V2V3V4neDG0023

V1

V2

V3

V47.2图的存储结构2）有向图的逆邻接表类似于无向图的邻接7.2图的存储结构

在不同的存储结构下，实现各种操作的效率可能是不同的。所以在求解实际问题时，要根据求解问题所需操作，选择合适的存储结构。7.2图的存储结构在不同的存储结构下，实第七章图7.3图的遍历一深度优先遍历二广度优先遍历

第七章图7.3图的遍历7.3图的遍历

图的遍历：从图的某顶点出发，访问图中所有顶点，并且每个顶点仅访问一次。图中可能有回路，遍历可能沿回路又回到已遍历过的结点。为避免同一顶点被多次访问，必须为每个被访问的顶点作一标志。为此引入一辅助数组，记录每个顶点是否被访问过。

有两种遍历方法（它们对无向图，有向图都适用）：深度优先遍历广度优先遍历7.3图的遍历图的遍历：从图的某7.3图的遍历一深度优先遍历从图中某顶点v出发：1）访问顶点v；

2）从v的未被访问的邻接点出发，继续对图进行深度优先遍历；例

图G中，以V1起点的的深度优先序列：（1）V1,V2,V4,V5,V8,V3,V6,V7,（2）V1,V2,V5,V8,V4,V3,V6,V7

V8

V7

V6

V5

V4

V3

V2

V1由于没为有规定访问邻接点的顺序，深度优先序列不是唯一的这是序列（1）在遍历过程中所经过的路径注：为简单起见，只讨论非空连通图的遍历7.3图的遍历一深度优先遍历例图G中，以V1起点的7.3图的遍历深度优先遍历(设图为非空连通图）从图中某顶点v出发：1）访问顶点v；

2）从v的未被访问的邻接点出发，继续对图进行深度优先遍历；

先序遍历（DLR）

若二叉树非空

（1）访问根结点；（2）先序遍历左子树；

（3）先序遍历右子树；如果将图顶点的邻接点看作二叉树结点的左、右孩子深度优先遍历与先序遍历是不是很类似？

V8

V7

V6

V5

V4

V3

V2

V17.3图的遍历深度优先遍历(设图为非空连通图）先序遍历7.3图的遍历深度优先遍历算法voidDFS(GraphG,intv,Status(*Visit(intv)){//从第v个顶点出发，递归地深度优先遍历图G。//v是顶点在一维数组中的位置，假设G是非空图visited[v]=TRUE;Visit(v);//访问第v个顶点for(w=FirstAdjVex(G,v);w;w=NextAdjVex(G,v,w))if(!visited[w])DFS(G,w);//对v的尚未访问的邻接顶点w递归调用DFSBooleanvisited[MAX_VERTEX_NUM]//访问标志数组,全局变量，初始值：所有分量全为False(0)//visited[v]=TRUE表示顶点v已被访问visited01234m-1000007.3图的遍历深度优先遍历算法Booleanvisit7.3图的遍历先序遍历递归算法

voidPreOrderTraverse(BiTreeT,Status(*Visit)(TElemTypee)){

//本算法先序遍历以T为根结点指针的二叉树。

if(T){//若二叉树为空，结束返回

Visit(T->data)；

PreOrderTraverse(T->lchild,Visit);

PreOrderTraverse(T->rchild,Visit);

}//PreOrderTraverse如果将图顶点的邻接点看作二叉树结点的左、右孩子深度优先遍历算法与先序遍历算法的结构是不是很像？深度优先遍历算法voidDFS(GraphG,intv,Status(*Visit(intv)){//从第v个顶点出发，递归地深度优先遍历图G。//v是顶点在一维数组中的位置，假设G是非空图visited[v]=TRUE;Visit(v);//访问第v个顶点for(w=FirstAdjVex(G,v);w;w=NextAdjVex(G,v,w))if(!visited[w])DFS(G,w);//对v的尚未访问的邻接顶点w递归调用DFS7.3图的遍历先序遍历递归算法

voidPreOr7.3图的遍历广度优先遍历（类似于树的按层遍历）

从图中某顶点v出发：1）访问顶点v；2）访问v的所有未被访问的邻接点w1,w2,

…wk；3）依次从这些邻接点出发，访问它们的所有未被访问的邻接点;依此类推，直到图中所有访问过的顶点的邻接点都被访问；例

图G中，以V1起点的的广度优先序列：（1）V1,V2,V3,V4,V5,V6,V7,V8（2）V1,V3,V2,V6,V7,V4,V5,V8

V8

V7

V6

V5

V4

V3

V2

V1这是序列（1）在遍历过程中所经过的路径由于没为有规定访问邻接点的顺序，广度优先序列不是唯一的7.3图的遍历广度优先遍历（类似于树的按层遍历）V87.3图的遍历广义优先遍历算法从图中某顶点v出发：1）访问顶点v；（容易实现）2）访问v的所有未被访问的邻接点w1,w2,

…wk；（容易实现）3）依次从这些邻接点（在步骤2）访问的顶点）出发，访问它们的所有未被访问的邻接点;依此类推，直到图中所有访问过的顶点的邻接点都被访问；为实现3），需要保存在步骤(2）中访问的顶点，而且访问这些顶点邻接点的顺序为：先保存的顶点，其邻接点先被访问。在广度优先遍历算法中，需设置一队列Q，保存已访问的顶点，并控制遍历顶点的顺序。7.3图的遍历广义优先遍历算法在广度优先遍历算法中，需设7.3图的遍历voidBFSTraverse(GraphG,intv,Status(*Visit)(intv)){//从v出发，广度优先遍历连通图G。v是顶点在一维数组中的位置，使用辅助队列Q和访问标志数组visited。for(u=0;u<G.vexnum;++u)visited[u]=FALSE;InitQueue(Q);//建空的辅助队列QVisited[v]=TRUE;Visit(v)，EnQueue(Q,v)//访问v,v入队While(!QueueEmpty(Q)){DeQueue(Q,u);//队头元素出队,并赋值给u//访问u所有未被访问的邻接点for(w=FirstAdjVex(G,u);w;w=NextAdjVex(G,u,w))if(!visited[w]){//若w尚未访问Visited[w]=TRUE;Visit(w);EnQueue(Q,w);}//if}//while}//BFSTraverse7.3图的遍历voidBFSTraverse(Grap7.3图的遍历非连通图的遍历上面介绍了连通图的深度优先遍历算法，对非连通图,可从每个连通分量选一起点，调用遍历算法（如DFS）完成各连通分量的深度先遍历。例图G的深度优先序列：V1,V2,V3,V4,V5,V6,广度优先序列V1,V2,V3,V4,V5,V6,

V3

V1

V2

V4

V5

V6

V3

V1

V2

V4

V5

V6深度优先遍历所经过的路径广度优先遍历所经过的路径7.3图的遍历非连通图的遍历V3V1V2V4V7.4.1图的连通性问题--

无向图的连通分量和生成树

生成树定义：所有顶点均由边连接在一起，但不存在回路的图叫~深度优先生成树与广度优先生成树生成森林：非连通图每个连通分量的生成树一起组成非连通图的~7.4图的连通性7.4图的连通性7.4.1图的连通性问题--

无向图的连通分量和生成树说明一个图可以有许多棵不同的生成树所有生成树具有以下共同特点：生成树的顶点个数与图的顶点个数相同生成树是图的极小连通子图一个有n个顶点的连通图的生成树有n-1条边生成树中任意两个顶点间的路径是唯一的在生成树中再加一条边必然形成回路含n个顶点n-1条边的图不一定是生成树GHKI7.4.1图的连通性问题--无向图的连通分量和生成树GHV1V2V4V5V3V7V6V8例深度遍历：V1V2V4V8V5V3V6V7V1V2V4V5V3V7V6V8深度优先生成树V1V2V4V5V3V7V6V8广度优先生成树V1V2V4V5V3V7V6V8V1V2V4V5V3V7V6V8广度遍历：V1V2V3V4V5V6V7V8V1V2V4V5V3V7V6V8例深度遍历：V1V2例ABLMCFDEGHKIJABLMCFJDEGHKI深度优先生成森林例ABLMCFDEGHKIJABLMCFJDEGHKI深度优voidDFSTree(GraphG,intv,CSTree*T){/*从第v个顶点出发深度优先遍历图G，建立以*T为根的生成树*/visited[v]=TRUE;first=TRUE;for(w=FirstAdjVex(G,v);w;w=NextAdjVex(G,v,w))if(!visited[w]){p=(CSTree)malloc(sizeof)CSNode));/*分配孩子结点*/*p={GetVex(G,w),NULL,NULL};if(first)/*w是v的第一个未被访问的邻接顶点，作为根的左孩子结点*/{T->lchild=p;first=FALSE;}else{/*w是v的其它未被访问的邻接顶点，作为上一邻接顶点的右兄弟*/q->nextsibling=p;}q=p;DFSTree(G,w,&q);/*从第w个顶点出发深度优先遍历图G，建立生成子树*q*/}}voidDFSTree(GraphG,intv,C7.4图的连通性7.4.3最小生成树n个城市之间,最多可能设置n(n-1)/2条线路,而连通n个城市只需要n-1条线路.

最小(代价)生成树的定义.

一棵生成树的代价.7.4图的连通性7.4.3最小生成树507.4图的连通性最小生成树MST的性质:

假设N=(V,{E})是一个连通网,U是顶点集V的一个非空子集.若(u,v)是一条具有最小权值(代价)的边,其中u属于U,v属于V-U,则必存在一棵包含边(u,v)的最小生成树.7.4图的连通性最小生成树MST的性质:517.4图的连通性算法一：（普里姆算法）

假设N=(V,{E})是连通网,TE是N上最小生成树中边的集合.算法从U={u0}(u0属于V),TE={}开始,重复执行下述操作:

在所有u属于U,v属于V-U的边(u,v)属于E中找一条代价最小的边(u0,v0)并入集合TE,同时v0并入U,直至U=V为止.

此时TE中必有n-1条边,则T=(V,{TE})为N的最小生成树.7.4图的连通性算法一：（普里姆算法）52

为实现这个算法需要附设一个辅助数组closedge,以记录从U到V-U具有最小代价的边.

对每个顶点vi属于V-U,在辅助数组中存在一个相应分量closedge[i-1],它包括两个域,

其中lowcost存储该边上的权.显然:closedge[i-1].lowcost=Min{cost(u,vi)|u属于U}

vex域存储该边依附的在U中的顶点.7.4图的连通性为实现这个算法需要附设一个辅助数组closed53普里姆算法构造最小生成树的过程v2v4v6v3v1v5v1v4v6v5v2v3651534626(a)1425357.4图的连通性普里姆算法构造最小生成树的过程v2v4v6v3v1v5v1v54普里姆算法voidMiniSpanTree_PRIM（MGraphG，VertexTypeu）{//用普里姆算法从第u个顶点出发构造网G的最小生成树T，

//输出T的各条边。

//记录从顶点集U到V-U的代价最小的边的辅助数组定义：struct{VertexTypeadjvex；VRTypelowcost；}closedge[MAX_VERTEX_NUM];7.4图的连通性普里姆算法7.4图的连通性55k=LocateVex（G，u）；for（j=0；j<G.vexnum；++j）//辅助数组初始化

if（j！=k）closedge[j]={u，G.arcs[k][j].adj}；//{adjvex，lowcost}closedge[k].lowcost=0；//初始，U={u}for（i=1；i<G.vexnum；++i）{//选择其余G.vexnum-1个顶点

k=minimum（closedge）；//求出T的下一个结点：第k顶点

//此时closedge[k].lowcost=

//MIN{closedge[vi].lowcost|closedge[vi].lowcost>0，vi∈V-U}printf（closedge[k].adjvex，G.vexs[k]）；//输出生成树的边

closedge[k].lowcost=0；//第k顶点并入U集

for（j=0；j<G.vexnum；++j）

if（G.arcs[k][j].adj<closedge[j].lowcost）

//新顶点并入U后重新选择最小边

closedge[j]={G.vexs[k]，G.arcs[k][j].adj}；}}//MiniSpanTree7.4图的连通性k=LocateVex（G，u）；7.4图的连通性56算法二：（克鲁斯卡尔算法）

为使生成树上边的权值之和最小，显然，其中每一条边的权值应该尽可能地小。克鲁斯卡尔算法的做法就是：先构造一个只含n个顶点的子图SG，然后从权值最小的边开始，若它的添加不使SG中产生回路，则在SG上加上这条边，如此重复，直至加上n-1条边为止。7.4图的连通性算法二：（克鲁斯卡尔算法）7.4图的连通性57克鲁斯卡尔算法构造最小生成树的过程v2v4v6v3v1v5v1v4v6v5v2v3651534626(a)1425357.4图的连通性克鲁斯卡尔算法构造最小生成树的过程v2v4v6v3v1v5v58一般来讲，由于普里姆算法的时间复杂度为O(n2)，则适于稠密图；而克鲁斯卡尔算法需对e条边按权值进行排序，其时间复杂度为O(eloge)，则适于稀疏图。7.4图的连通性一般来讲，7.4图的连通性597.4图的连通性

“最小生成树”主要是针对“无向图”而言的，请思考它主要能解决哪些实际生活中遇到的问题？7.4图的连通性“最小生成树”主要是针对“无向图607.6最短路径

7.6.1从某个源点到其余各顶点的最短路径问题提出用带权的有向图表示一个交通运输网，图中：顶点——表示城市边——表示城市间的交通联系权——表示此线路的长度或沿此线路运输所花的时间或费用等问题：从某顶点出发，沿图的边到达另一顶点所经过的路径中，各边上权值之和最小的一条路径——最短路径

7.6最短路径

7.6.1从某个源点到其余各顶点的最短路7.6最短路径

7.6.1从某个源点到其余各顶点的最短路径给定带权有向图G和源点v,求从v到G中其余各顶点的最短路径例:求v0到其余顶点的最短路径V1V5V2V4V0V35501001060201030始点终点最短路径路径长度

v0v1

无

v2(v0,v2)10v3(v0,v4,v3)50v4(v0,v4)30v5(v0,v4,v3,v5)607.6最短路径

7.6.1从某个源点到其余各顶点的最短路

迪杰斯特拉(Dijkstra)算法(1)设置两个顶点的集合T和S;集合S存放已找到最短路径的顶点集合T存放当前还未找到最短路径的顶点(2)初始状态时,S只包含源点v0;(3)从T中选取某个顶点vi(要求vi到v0的路径长度最短)加入到S中,;(4)S中每加入一个顶点vi,都要修改顶点v0到T中剩余顶点的最短路径长度值;它们的值为原来值与新值的较小者;新值是vi的最短路径长度值加上vi到该顶点的路径长度(5)不断重复(3)和(4),直到S包含全部顶点;

迪杰斯特拉(Dijkstra)算法(1)设置两个顶点的集合V1V5V2V4V0V35501001060201030迪杰斯特拉(Dijkstra)算法举例带权邻接矩阵为:1030100550102060V1V5V2V4V0V35501001060201030迪杰最短路径的求解过程终点v1v2v3v4v5vi步骤11030100v2(v0,v2)(v0,v4)(v0,v5)步骤2

6030100v4(v0,v2,v3)(v0,v4)(v0,v5)步骤35090v3(v0,v4,v3)(v0,v4,v5)步骤4

60v5(v0,v4,v3,v5)步骤5

无最短路径的求解过程终点v1v7.6最短路径

7.6.2每一对顶点间的最短路径给定带权有向图G,求G中每个顶点到其余各顶点的最短路径例:求有向网G的每一对顶点的最短路径V0V2V1624113有向网G041160230邻接矩阵7.6最短路径

7.6.2每一对顶点间的最短路径给定带权Floyd算法(1)递推产生一个矩阵序列A0,A1,...,Ak,...An其中Ak[i,j]表示从顶点vi到vj的路径上所经过的顶点序号不大于k的最短路径长度(2)初始时,A0为邻接矩阵.(3)Ak+1[i,j]=min{Ak[i,j],Ak[i,k+1]+Ak[k+1,j]}(0<=k<=n-1)041160230A0=04650237

0A2=04660230A1=Floyd算法(1)递推产生一个矩阵序列A0,A1,...,例ACB264311041160230初始：路径：ABACBABCCA046602370加入V2：路径：ABABCBABCCACAB0411602370加入V1：路径：ABACBABCCACAB046502370加入V3：路径：ABABCBCABCCACAB例ACB2643110411初始：路径：AB7.5有向无环图及其应用一个无环的有向图叫做有向无环图简称DAG图有向树DAG图有向图7.5有向无环图及其应用一个无环的有向图叫做有向无环图简称有向无环图是

--------描述含有公共子式的表达式的有效工具.((a+b)*(b*(c+d))+(c+d)*e)*((c+d)*e)*****+++++abbcccddd用二叉树描述表达式ee****+++abbcd用DAG描述表达式e有向无环图是

--------描述含有公共子式的表达式的有效有向无环图也是---------

描述一项工程或系统的进行过程的有效工具C12C10C11C9C1C2C3C4C6C5C7C8有向无环图也是---------

描述一项工程或系统的进行过7.5.1拓扑排序

AOV-网(ActivityOnVertex)顶点－－活动弧－－活动间的优先关系AOV－网不应该出现有向环上例的拓扑排序序列之一：C1,C9,C2,C4,C10,C11,C3,C12,C6,C5,C7,C87.5.1拓扑排序

AOV-网(ActivityOnV7.5.2关键路径

AOE-网(ActivityOnEdge)AOE－网是带权的有向无环网顶点－－事件或状态弧－－活动及发生的依次关系权－－活动持续的时间源点－－入度为０的顶点（只有一个）汇点－－出度为０的顶点（只有一个）V4V1V3V8V2V7V9V6V5a1=6a2=4a3=5a4=1a5=1a6=2a7=9a8=7a9=4a10=2a11=47.5.2关键路径

AOE-网(ActivityOnAOE-网要研究的问题完成整项工程至少需要多少时间？哪些活动是影响整个工程进度的关键？关键路径：路径长度最长的路径（从源点到汇点）e(i)表示活动ai的最早开始时间l(i)表示活动ai的最迟开始时间(不推迟整个工期)

e(i)=l(i)的活动叫做关键活动,关键路径上的活动都是关键活动.ve(j)表示事件vj的最早发生时间vl(j)表示事件vj的最迟发生时间(不推迟整个工期)AOE-网要研究的问题完成整项工程至少需要多少时间？e(i)e(i),l(i),ve(j),vl(j)的关系若活动ai由弧<j,k>表示,其持续的时间记为dut(<j,k>),则

e(i)=ve(j)l(i)=vl(k)-dut(<j,k>)VjVkai求ve(j)和vl(j)分两步进行:(1)从ve(0)=0开始向前递推:ve(j)=max{ve(i)+dut(<i,j>)}

iViVjaiViVjai(2)vl(n-1)=ve(n-1)开始向后递推:

vl(i)=min{vl(j)-dut(<i,j>)}

je(i),l(i),ve(j),vl(j)的关系若活动a求AOE网的关键路径举例V4V1V3V8V2V7V9V6V5a1=6a2=4a3=5a4=1a5=1a6=2a7=9a8=7a9=4a10=2a11=4求AOE网的关键路径举例V4V1V3V8V2V7V9V6V5V1V8V2V7V9V5a1=6a4=1a7=9a8=7a10=2a11=4整个工期为18关键路径有两条:(V1,V2,V5,V7,V9),(V1,V2,V5,V8,V9)关键活动有六个:a1,a4,a7,a8,a10,a11V1V8V2V7V9V5a1=6a4=1a7=9a8=7a1第七章图第七章图

第七章图7.1图的定义和术语7.2图的存储结构7.3图的遍历7.4图的连通性问题7.5有向无环图及应用7.6最短路径第七章图第七章图本章介绍另一种非线性数据结构——图图：是一种多对多的结构关系，每个元素可以有零个或多个直接前趋；零个或多个直接后继；第七章图本章介绍另一种非线性数据结构——图第七章图

学习要点1．熟悉图的各种存储结构及其构造算法，了解实际问题的求解效率与采用何种存储结构和算法有密切联系；2．熟练掌握图的两种遍历：深度优先遍历和广度优先遍历的算法。在学习中应注意图的遍历算法与树的遍历算法之间的类似和差异。树的先根遍历是一种深度优先搜索策略，树的层次遍历是一种广度优先搜索策略3．理解课件中讨论的各种图的算法；

第七章图

学习要点7.1图的定义和术语一图的概念

图G由两个集合构成，记作G=<V,E>其中V是顶点的非空有限集合，E是边的有限集合，其中边是顶点的无序对或有序对集合。例G1=<V1,E1>V1={v1,v2,v3,v4,v5}E1={(v1,v2),(v1,v3),(v2,v3),(v2,v5),(v3,v4),(v3,v5)}G1图示无序对(vi,vj)：用表示顶点vi、vj的线段，称为无向边；

V5V1

V2

V4

V37.1图的定义和术语一图的概念例G1=<V1,E17.1图的定义和术语例G2=<V2,E2>V2={v1,v2,v3,v4}E2={<v1,v2>,<v1,v3>,<v3,v4>,<v4,v1>}G2图示有序对<vi,vj>：用以表示以vi起点、以vj为终点的有向线段，称为有向边或弧；无向图：在图G中，若所有边是无向边，则称G为无向图；有向图：在图G中，若所有边是有向边，则称G为有向图；混和图：在图G中，即有无向边也有有向边，则称G为混合图；

V1

V2

V3

V4V1称为弧尾(初始点)V3称为弧头(终端点)7.1图的定义和术语例G2=<V2,E2>G2图示有序7.1图的定义和术语图的应用举例例1交通图（公路、铁路）顶点：地点边：连接地点的公路交通图中的有单行道双行道，分别用有向边、无向边表示；例2电路图顶点：元件边：连接元件之间的线路例3通讯线路图顶点：地点边：地点间的连线例4各种流程图如产品的生产流程图顶点：工序边：各道工序之间的顺序关系

V5V1

V2

V4

V37.1图的定义和术语图的应用举例V5V1V2V47.1图的定义和术语三图的基本操作1CreateGraph(&G,V,VR);初始条件：V是图的顶点集，VR是图中弧的集合操作结果：按V和VR的定义构造图G2DestroyGraph(&G);初始条件：图G存在操作结果：销毁图G3LocateVex(G,u);初始条件：图G存在，u和G中顶点有相同特征操作结果：若G中存在顶点u，则返回该顶点在图中位置；否则返回其它信息。4GetVex(G,v);初始条件：图G存在，v是G中某个顶点操作结果：返回v的值5PutVex(&G,v,value);初始条件：图G存在，v是G中某个顶点操作结果：对v赋值value7.1图的定义和术语三图的基本操作7.1图的定义和术语6FirstAdjVex(G,v);初始条件：图G存在，v是G中某个顶点操作结果：返回v的第一个邻接顶点。若顶点在G中没有邻接顶点，则返回“空”。7NextAdjVex(G,v,w);初始条件：图G存在，v是G中某个顶点，w是v的邻接顶点。操作结果：返回v的（相对于w的）下一个邻接顶点。若w是v的最后一个邻接点，则返回“空”。8InsertVex(&G,v);初始条件：图G存在，v和图中顶点有相同特征。操作结果：在图G中增添新顶点v9DeleteVex(&G,v);初始条件：图G存在，v和图中顶点有相同特征操作结果：删除G中顶点v及相关的弧7.1图的定义和术语6FirstAdjVex(G,v7.1图的定义和术语10InsertArc(&G,v,w);初始条件：图G存在，v和w是G中两个顶点。操作结果：在G中增添弧<v,w>，若G是无向的，则还增添对称弧<w,v>11DeleteArc(&G,v,w);初始条件：图G存在，v和w是G中两个顶点。操作结果：在G中删除弧<v,w>，若G是无向的，则还删除对称弧<w,v>12DFSTraverse(G,v,Visit());初始条件：图G存在，v是G中某个顶点，Visit是顶点的应用函数。操作结果：从顶点v起深度优先遍历图G，对每个顶点调用函数Visit一次且仅一次。一旦visit()失败，则操作失败13BFSTraverse(G,v,Visit());初始条件：图G存在，v是G中某个顶点，Visit是顶点的应用函数。操作结果：从顶点v起广度优先遍历图G，对每个顶点调用函数Visit一次且一次。一旦visit()失败，则操作失败7.1图的定义和术语10InsertArc(&G,v7.1图的定义和术语图的基本术语1邻接点及关联边

邻接点：边的两个顶点

关联边：若边e=(v,u),则称顶点v、u关联边e（边e依附于顶点v,u)2顶点的度、入度、出度

顶点V的度=与V相关联的边的数目在有向图中：顶点V的出度=以V为起点有向边数

顶点V的入度=以V为终点有向边数顶点V的度=V的出度+V的入度设图G的顶点数为n，边数为e

图的所有顶点的度数和=2*e（每条边对图的所有顶点的度数和“贡献”2度）

e1

V1

V2

V3

V4

V5V1

V2

V4

V37.1图的定义和术语图的基本术语e1V1V2V33有向完全图、无向完全图有向完全图——n个顶点的有向图最大边数是n(n-1)无向完全图——n个顶点的无向图最大边数是n(n-1)/2权(weight)——与图的边或弧相关的数叫~网——带权的图叫~7.1图的定义和术语3有向完全图、无向完全图7.1图的定义和术语7.1图的定义和术语

路径、回路

无向图中的顶点序列v1,v2,…,vk,若(vi,vi+1)E(i=1,2,…k-1),v=v1,u=vk,

则称该序列是从顶点v到顶点u的路径；若v=u，则称该序列为回路；

有向图D=(V，E）中的顶点序列v1,v2,…,vk,若<vi,vi+1>E(i=1,2,…k-1),v=v1,u=vk,则称该序列是从顶点v到顶点u的路径；若v=u，则称该序列为回路；

例在图1中，V1,V2,V3,V4是V1到V4的路径；V1,V2,V3,V4,V1是回路；在图2中，V1,V3,V4是V1到V4的路径；V1,V3,V4,V1是回路；

V5V1

V2

V4

V3

V1

V2

V3

V4图1图27.1图的定义和术语路径、回路V5V1V2V47.1图的定义和术语连通图、（强连通图）

在无（有）向图G=<V,E>中，若对任何两个顶点v、u都存在从v到u的路径，则称G是连通图（强连通图）

V5

V6

V3

V1

V2

V4连通图非连通图

V5V1

V2

V4

V37.1图的定义和术语连通图、（强连通图）V5V6V7.1图的定义和术语子图

设有两个图G=（V，E）、G1=（V1，E1），若V1V，E1E，E1关联的顶点都在V1中，则称G1是G的子图；例图2、图3是图1的子图

V5V1

V2

V4

V3

V5V1

V2

V3

V5V1

V2

V4

V3图1图2图37.1图的定义和术语子图V5V1V2V4V37.1图的定义和术语连通分图（强连通分量）

无向图G的极大连通子图称为G的连通分量极大连通子图意思是：该子图是G连通子图，将G的任何不在该子图中的顶点加入，子图不再连通；有向图D的极大强连通子图称为D的强连通分量极大强连通子图意思是：该子图是D强连通子图，将D的任何不在该子图中的顶点加入，子图不再是强连通的；

V5

V6

V3

V1

V2

V4连通分图7.1图的定义和术语连通分图（强连通分量）V5V67.1图的定义和术语

V5V1

V2

V4

V3

V5V1

V2

V4

V38生成树（

包含无向图G所有顶点的的极小连通子图称为G生成树极小连通子图意思是：该子图是G的连通子图，在该子图中删除任何一条边，子图不再连通，若T是G的生成树当且仅当T满足如下条件T是G的连通子图T包含G的所有顶点T中无回路只有足以构成一棵树的n-1条边7.1图的定义和术语V5V1V2V4V3V5例213213有向完全图无向完全图356例245136图与子图例245136G1顶点2入度：1出度：3顶点4入度：1出度：0例157324G26顶点5的度：3顶点2的度：4例213213有向完全图无向完全图356例245136图与子例157324G26例245136G1路径：1，2，3，5，6，3路径长度：5简单路径：1，2，3，5回路：1，2，3，5，6，3，1简单回路：3，5，6，3路径：1，2，5，7，6，5，2，3路径长度：7简单路径：1，2，5，7，6回路：1，2，5，7，6，5，2，1简单回路：1，2，3，1例157324G26例245136G1路径：1，2，3，5，连通图例245136强连通图356例非连通图连通分量例245136连通图例245136强连通图356例非连通图连通分量例245第七章图7.2图的存储结构数组表示法邻接表第七章图7.2图的存储结构7.2图的存储结构

图是多对多的结构，比线性结构、树结构复杂，所以其存储结构也要复杂些。与线性结构、树结构一样，图的存储结构至少要保存两类信息： 1)顶点的数据2) 顶点间的关系顶点的编号

为了使图的存储结构与图一一对应，在讨论图的存储结构时，首先要给图的所有顶点编号。

本课程介绍两类图的存储结构

数组表示法 邻接表（邻接表，逆邻接表）

设G=<V,E>是图,V={v1,v2,v3,…

vn},设顶点的的角标为它的编号如何表示顶点间的关系？？7.2图的存储结构图是多对多的结构，比线7.2图的存储结构

邻接矩阵：G的邻接矩阵是满足如下条件的n阶矩阵：

一数组表示法数组表示法是图的一种顺序存储结构在数组表示法中，用邻接矩阵表示顶点间的关系A[i][j]=1若(vi,vi+1)E或<vi,vi+1>E0否则

V5V1

V2

V4

V30101