非线性数据结构

非线性数据结构1本章导读图是又一种非线性数据结构。在图结构中，数据元素之间的关系是多对多的，即如果任选一个顶点作为初始顶点，则图中任意一个顶点有多个前驱顶点和多个后记顶点。本章主要讨论图的一些基本概念和基本操作，图的存储结构及图基本操作的算法实现，最后讨论图的最小生成树问题和最短路径问题。非线性数据结构全文共98页，当前为第1页。非线性数据结构2第8章图图的基本概念和抽象数据类型图的存储结构邻接矩阵图类图的遍历最小生成树最短路径主要知识点非线性数据结构全文共98页，当前为第2页。非线性数据结构38.1图的基本概念和抽象数据类型1.图的基本概念图是由顶点集合及顶点间的关系集合组成的一种数据结构。图G的定义是：

G=（V，E）其中，V={x|x∈某个数据元素集合}E={(x，y)|x，y∈V}或E={＜x，y＞|x，y∈V并且Path(x，y)}其中，（x，y）表示从x到y的一条双向通路，即（x，y）是无方向的；Path（x，y）表示从x到y的一条单向通路，即Path（x，y）是有方向的。非线性数据结构全文共98页，当前为第3页。非线性数据结构4基本术语：（1）顶点和边：图中的结点称作顶点，图中的第i个顶点记做vi。两个顶点vi和vj相关联称作顶点vi和vj之间有一条边，图中的第k条边记做ek，ek=（vi,vj）或＜vi,vj＞。（2）有向图和无向图：在有向图中，顶点对＜x,y＞是有序的，顶点对＜x,y＞称为从顶点x到顶点y的一条有向边，有向图中的边也称作弧；在无向图中，顶点对（x,y）是无序的，顶点对（x,y）称为与顶点x和顶点y相关联的一条边。（3）完全图：在有n个顶点的无向图中，若有n(n-1)/2条边，即任意两个顶点之间有且只有一条边，则称此图为无向完全图；在有n个顶点的有向图中，若有n(n-1)条边，即任意两个顶点之间有且只有方向相反的两条边，则称此图为有向完全图。非线性数据结构全文共98页，当前为第4页。非线性数据结构521342145G23G1例如：下图G1是有向图，G2是无向图非线性数据结构全文共98页，当前为第5页。非线性数据结构6（4）邻接顶点：在无向图G中，若（u,v）是E(G)中的一条边，则称u和v互为邻接顶点，并称边（u,v）依附于顶点u和v；在有向图G中，若＜u,v＞是E(G)中的一条边，则称顶点u邻接到顶点v，顶点v邻接自顶点u，并称边＜u,v＞和顶点u和顶点v相关联。013201234560120123(a)无向完全图(b)无向图(c)有向图(d)有向完全图非线性数据结构全文共98页，当前为第6页。非线性数据结构7（5）顶点的度：顶点v的度是与它相关联的边的条数，记作TD(v)。（6）路径：在图G=(V,E)中，若从顶点vi出发有一组边使可到达顶点vj，则称顶点vi到顶点vj的顶点序列为从顶点vi到顶点vj的路径。非线性数据结构全文共98页，当前为第7页。非线性数据结构8（7）权：有些图的边附带有数据信息，这些附带的数据信息称为权。带权的图也称作网络或网。2135467879610612715163BACDE60304575804035施工进度图

交通网络图

非线性数据结构全文共98页，当前为第8页。非线性数据结构9（8）路径长度：对于不带权的图，一条路径的路径长度是指该路径上的边的条数；对于带权的图，一条路径的路径长度是指该路径上各个边权值的总和。（9）子图：设有图G1={V1,E1}和图G2={V2,E2}，若V2V1且E2E1，则称图G2是图G1的子图。非线性数据结构全文共98页，当前为第9页。非线性数据结构10（10）连通图和强连通图：在无向图中，若从顶点vi到顶点vj有路径，则称顶点vi和顶点vj是连通的。如果图中任意一对顶点都是连通的，则称该图是连通图。图中的无向图a和b都是连通图。在有向图中，若对于任意一对顶点vi和顶点vj（vi≠vj）都存在路径，则称图G是强连通图。图中的有向图d是强连通图。（11）生成树：一个连通图的最小连通子图称作该图的生成树。有n个顶点的连通图的生成树有n个顶点和n-1条边。（12）简单路径和回路：若路径上各顶点v1,v2,…,vm,互不重复，则称这样的路径为简单路径；若路径上第一个顶点v1与最后一个顶点vm重合，则称这样的路径为回路或环。非线性数据结构全文共98页，当前为第10页。非线性数据结构11数据集合：由一组顶点集合｛vi

｝和一组边集合{ej}组成。当为带权图时每条边上权wj构成权集合{wi}。操作集合：(1)初始化Initiate(G,n)(2)插入顶点InsertVertex(G,vertex)(3)插入边InsertEdge(G,v1,v2,weight)(4)删除边DeleteEdge（G,v1,v2)(5)删除顶点DeleteVertex(G,vertex)(6)第一个邻接结点GetFirstVex(G,v)(7)下一个邻接结点GetNextVex(G,intv1,v2)(8)遍历DepthFirstSearch(G)2.图的抽象数据类型非线性数据结构全文共98页，当前为第11页。非线性数据结构128.2图的存储结构图的存储结构主要有邻接矩阵和邻接表两种。1.图的邻接矩阵存储结构假设图G=(V,E)有n个顶点，即V={v0,v1,…,vn-1}，E可用如下形式的矩阵A描述，对于A中的每一个元素aij，满足：由于矩阵A中的元素aij表示了顶点vi和顶点vj之间边的关系，或者说，A中的元素aij表示了顶点vi和顶点vj（0≤j≤n-1）的邻接关系，所以矩阵A称作邻接矩阵。îíì>Î<Î=否则或若0,),(1EvvEvvajijiij非线性数据结构全文共98页，当前为第12页。非线性数据结构13无向图的邻接矩阵一定是对称矩阵有向图的邻接矩阵一般是非对称矩阵其中V表示了图的顶点集合，A表示了图的邻接矩阵21435úúúúúúûùêêêêêêëé=54321Vúúúúúúûùêêêêêêëé=0010100011100010100111110A(b)(a)BADCEúúúúúúûùêêêêêêëé=EDCBAVúúúúúúûùêêêêêêëé=0000000010100000000011110A(b)(a)非线性数据结构全文共98页，当前为第13页。非线性数据结构14带权图及其邻接矩阵其中V表示了图的顶点集合，A表示了图的邻接矩阵。对于带权图，邻接矩阵第i行中所有0<aij<∞的元素个数等于第i个顶点的出度，邻接矩阵第j列中所有0<aij<∞的元素个数等于第j个顶点的入度。214356úúúúúúúúûùêêêêêêêêë饥¥¥¥¥¥¥¥¥¥¥¥¥¥¥¥¥=080070807005040500304002030200Aúúúúúúúúûùêêêêêêêêëé=654321V(a)(b)402030507080非线性数据结构全文共98页，当前为第14页。非线性数据结构152.图的邻接表存储结构当图的边数少于顶点个数且顶点个数值较大时，图的邻接n×n矩阵的存储问题就变成了稀疏矩阵的存储问题，此时，邻接表就是一种较邻接矩阵更为有效的存储结构。BADCE(a)01234ABCDE0datasorce1432adjdestnext23411∧

∧

∧

∧

(b)4∧

非线性数据结构全文共98页，当前为第15页。非线性数据结构16数组的data域存储图的顶点信息，sorce域存储该顶点在数组中的下标序号，adj域为该顶点的邻接顶点单链表的头指针。第i行单链表中的dest域存储所有起始顶点为vi的邻接顶点vj在数组中的下标序号，next域为单链表中下一个邻接顶点的指针域。如果是带权图，单链表中需再增加cost域，用来存储边<vi,vj>的权值wij。非线性数据结构全文共98页，当前为第16页。非线性数据结构17存储空间：对于有n个顶点，e条边的无向图而言，若采取邻接表作为存储结构，则需要n个表头结点和2e个表结点。

无向图的度：在无向图的邻接表中，顶点vi的度恰好就是第i个边链表上结点的个数。

有向图的度：在有向图中，第i个边链表上顶点的个数是顶点vi的出度。要想求得该顶点的入度，则必须遍历整个邻接表。在所有单链表中查找邻接点域的值为i的结点并计数求和。非线性数据结构全文共98页，当前为第17页。非线性数据结构18由此可见，对于用邻接表方式存储的有向图，求顶点的入度并不方便，因此需要有一种解决的方法－逆邻接表法。对图中的每一顶点vi建立一个递邻接表，即对每个顶点vi建立一个所有以顶点vi为弧头的弧的表，这样求顶点vi的入度即是计算逆邻接表中第i个顶点的边链表中结点个数。

非线性数据结构全文共98页，当前为第18页。非线性数据结构198.3邻接矩阵图类1.邻接矩阵图类的设计和实现邻接矩阵图类实现如下：#include"SeqList.h" //包含动态数组结构的顺序表类

classAdjMWGraph{private: SeqListVertices; //顶点顺序表

intEdge[MaxVertices][MaxVertices]; //边权值数组

intnumOfEdges; //边的个数

voidDepthFirstSearch(constintv,intvisited[],voidVisit(VerTitem)); voidBroadFirstSearch(constintv,intvisited[],voidVisit(VerTitem));非线性数据结构全文共98页，当前为第19页。非线性数据结构20public: AdjMWGraph(constintsz=MaxVertices); //构造函数 ~AdjMWGraph(void){}; //析构函数

intNumOfVertices(void) //取顶点个数 {returnVertices.Size();} intNumOfEdges(void) //取边的个数 {returnnumOfEdges;} VerTGetValue(constintv); //取顶点数值

intGetWeight(constintv1,constintv2); //取边的权值

voidInsertVertex(constVerT&vertex); //插入顶点

voidInsertEdge(constintv1,constintv2,intweight);//插入边

voidDeleteVertex(constintv); //删除顶点

voidDeleteEdge(constintv1,constintv2); //删除边非线性数据结构全文共98页，当前为第20页。非线性数据结构21intGetFirstNeighbor(constintv); //取第一个邻接顶点intGetNextNeighbor(constintv1,constintv2);//取下一个邻接顶点

voidDepthFirstSearch(voidVisit(VerTitem)); //深度优先遍历voidBroadFirstSearch(voidVisit(VerTitem)); //广度优先遍历};非线性数据结构全文共98页，当前为第21页。非线性数据结构22AdjMWGraph::AdjMWGraph(constintsz):Vertices(sz)//构造函数{

for(inti=0;i<sz;i++) for(intj=0;j<sz;j++) { if(i==j)Edge[i][j]=0; elseEdge[i][j]=MaxWeight; } numOfEdges=0;}非线性数据结构全文共98页，当前为第22页。非线性数据结构23VerTAdjMWGraph::GetValue(constintv)//取顶点v的数值{

if(v<0||v>Vertices.Size()) { cout<<"参数v越界出错!"<<endl; exit(0); } returnVertices.GetData(v);}22非线性数据结构全文共98页，当前为第23页。非线性数据结构24intAdjMWGraph::GetWeight(constintv1,constintv2)//取起始顶点为v1、终止顶点为v2的边的权值{

if(v1<0||v1>Vertices.Size()||v2<0||v2>Vertices.Size()) { cout<<"参数v1或v2越界出错!"<<endl; exit(0); } returnEdge[v1][v2];}voidAdjMWGraph::InsertVertex(constVerT&vertex)//插入顶点vertex{ //把顶点vertex插入到顺序表的当前表尾位置

Vertices.Insert(vertex,Vertices.Size());}非线性数据结构全文共98页，当前为第24页。非线性数据结构25voidAdjMWGraph::InsertEdge(constintv1,constintv2,intweight)//插入一条起始顶点为v1、终止顶点为v2、权值为weight的边{

if(v1<0||v1>Vertices.Size()||v2<0||v2>Vertices.Size()) { cout<<"参数v1或v2越界出错!"<<endl; exit(0); } Edge[v1][v2]=weight; //插入边

numOfEdges++; //边的个数加1}非线性数据结构全文共98页，当前为第25页。非线性数据结构26voidAdjMWGraph::DeleteVertex(constintv)//删除顶点v{ //删除所有包含顶点v的边

for(inti=0;i<Vertices.Size();i++) for(intj=0;j<Vertices.Size();j++) if((i==v||j==v)&&i!=j&&Edge[i][j]>0&&Edge[i][j]<MaxWeight) { Edge[i][j]=MaxWeight; //把该边的权值置为无穷大

numOfEdges--; //边的个数减1 }

Vertices.Delete(v); //删除顶点v}非线性数据结构全文共98页，当前为第26页。非线性数据结构27voidAdjMWGraph::DeleteEdge(constintv1,constintv2)//删除一条起始顶点为v1、终止顶点为v2的边{

if(v1<0||v1>Vertices.Size()|| v2<0||v2>Vertices.Size()||v1==v2) { cout<<"参数v1或v2出错!"<<endl; exit(0); }

if(Edge[v1][v2]==MaxWeight||v1==v2) { cout<<"该边不存在!"<<endl; exit(0); }

Edge[v1][v2]=MaxWeight; //把该边的权值置为无穷大

numOfEdges--; //边的个数减1}非线性数据结构全文共98页，当前为第27页。非线性数据结构28intAdjMWGraph::GetFirstNeighbor(constintv)//取顶点v的第一个邻接顶点。若存在返回该顶点的下标序号，否则返回-1{

if(v<0||v>Vertices.Size()) { cout<<"参数v1越界出错!"<<endl; exit(0); }

for(intcol=0;col<=Vertices.Size();col++) if(Edge[v][col]>0&&Edge[v][col]<MaxWeight)returncol; return-1;}非线性数据结构全文共98页，当前为第28页。非线性数据结构29intAdjMWGraph::GetNextNeighbor(constintv1,constintv2)//取顶点v1的邻接顶点v2后的邻接顶点//若存在返回该顶点的下标序号，否则返回-1{

if(v1<0||v1>Vertices.Size()||v2<0||v2>Vertices.Size()) { cout<<"参数v1或v2越界出错!"<<endl; exit(0); }

for(intcol=v2+1;col<=Vertices.Size();col++) if(Edge[v1][col]>0&&Edge[v1][col]<MaxWeight)returncol; return-1;}非线性数据结构全文共98页，当前为第29页。非线性数据结构302.邻接矩阵图类的测试例8-1以下图所示的带权有向图为例编写测试邻接矩阵图类的程序。ABCDE1040305020图的创建函数设计如下：structRowColWeight{ introw; //行下标

intcol; //列下标

intweight; //权值};图8-8非线性数据结构全文共98页，当前为第30页。非线性数据结构31voidCreatGraph(AdjMWGraph&G,DataTypeV[],intn,RowColWeightE[],inte)//在图G中插入n个顶点V和e条边E{ //在图G中插入n个顶点for(inti=0;i<n;i++)G.InsertVertex(V[i]);

//在图G中插入e条边

for(intk=0;k<e;k++)G.InsertEdge(E[k].row,E[k].col,E[k].weight);}非线性数据结构全文共98页，当前为第31页。非线性数据结构32测试程序设计如下：#include<iostream.h>#include<stdlib.h>

typedefcharVerT; //定义邻接矩阵图类中的VerTtypedefcharDataType; //定义顺序表类中的DataTypeconstintMaxVertices=100; //定义最大顶点个数constintMaxWeight=10000; //定义权值的无穷大

#include"AdjMWGraph.h" //包含邻接矩阵的图类#include"CreatAdjMWGraph.h“//包含邻接矩阵图的建函数非线性数据结构全文共98页，当前为第32页。非线性数据结构33

voidmain(void){ AdjMWGraphg; chara[]={'A','B','C','D','E'}; RowColWeightrcw[]={{0,1,10},{0,4,20},{1,3,30},{2,1,40},{3,2,50}}; intn=5,e=5;

CreatGraph(g,a,n,rcw,e); //创建图

cout<<"顶点个数为："<<g.NumOfVertices()<<endl; cout<<"边的条数为："<<g.NumOfEdges()<<endl;

g.DeleteVertex(3); //删除顶点3

g.DeleteEdge(0,4); //删除边<0,4>

cout<<endl<<"顶点个数为："<<g.NumOfVertices(); cout<<endl<<"边的条数为："<<g.NumOfEdges()<<endl;}测试代码非线性数据结构全文共98页，当前为第33页。非线性数据结构348.4图的遍历1.图的深度和广度优先遍历算法图的遍历是访问图中的每一个顶点且每个顶点只被访问一次。算法设计需要考虑三个问题：（1）算法的参数要指定访问的第一个顶点；（2）要考虑遍历路径可能出现的死循环问题；（3）要使一个顶点的所有邻接顶点按照某种次序被访问。非线性数据结构全文共98页，当前为第34页。非线性数据结构35一、图的深度优先遍历算法。图的深度优先遍历算法是遍历时深度优先的算法，是一个递归算法。连通图的深度优先遍历递归算法为：（1）访问顶点v并标记顶点v为已访问；（2）查找顶点v的第一个邻接顶点w；（3）若顶点v的邻接顶点w存在，则继续执行，否则算法结束；（4）若顶点w尚未被访问则深度优先搜索递归访问顶点w；（5）查找顶点v的w邻接顶点的下一个邻接顶点w，转到步骤（3）。上述递归算法属于回溯算法非线性数据结构全文共98页，当前为第35页。非线性数据结构368ADGBEHCFI1236710114155149131216访问序列为：A、B、C、F、E、G、D、H、I。非线性数据结构全文共98页，当前为第36页。非线性数据结构37二、图的广度优先遍历算法图的广度优先遍历算法是一个分层搜索的过程，需要一个队列以保持访问过的顶点的顺序，以便按访问过的顶点的顺序来访问这些顶点的邻接顶点。连通图的广度优先遍历算法为：（1）访问初始顶点v并标记顶点v为已访问；（2）顶点v入队列；（3）当队列非空时则继续执行，否则算法结束；（4）出队列取得队头顶点u；（5）查找顶点u的第一个邻接顶点w；（6）若顶点u的邻接顶点w不存在，则转到步骤（3），否则循环执行，（6.1）若顶点w尚未被访问则访问顶点w并标记顶点w为已访问；（6.2）顶点w入队列；（6.3）查找顶点u的w邻接顶点后的下一个邻接顶点w，转到步骤（6）。非线性数据结构全文共98页，当前为第37页。非线性数据结构38ADGBEHCFI14657823访问序列为：A、B、E、D、C、G、F、H、I。非线性数据结构全文共98页，当前为第38页。非线性数据结构39V1V2V3V4V5V6V7V8深到底回退深到底V1V2V4V8V5（V2V8均已访问）深到底V3V6V7回退访问非线性数据结构全文共98页，当前为第39页。非线性数据结构40对图4广度优先搜索，访问顶点序列为：

V1V2V3V4V5V6V7V8V1V2V3V4V5V6V7V8非线性数据结构全文共98页，当前为第40页。非线性数据结构41三、非连通图的遍历对于非连通图，从图的任意一个顶点开始深度或广度优先遍历并不能访问图中的所有顶点。只能访问和初始顶点连通的所有顶点。但是，每一个顶点都作为一次初始顶点进行深度优先遍历或广度优先遍历，并根据顶点的访问标记来判断是否需要访问该顶点，就一定可以访问非连通图中的所有顶点。非线性数据结构全文共98页，当前为第41页。非线性数据结构42邻接矩阵存储结构图类的深度优先遍历成员函数如下：voidAdjMWGraph::DepthFirstSearch(constintv,intvisited[],voidVisit(VerTitem))//连通图G以v为初始顶点序号、访问操作为Visit()的深度优先遍历//数组visited标记了相应顶点是否已访问过，0表示未访问，1表示已访问{

Visit(GetValue(v)); //访问该顶点

visited[v]=1; //置已访问标记

intw=GetFirstNeighbor(v); //取第一个邻接顶点

while(w!=-1) //当邻接顶点存在时循环 {

if(!visited[w])DepthFirstSearch(w,visited,Visit);//递归

w=GetNextNeighbor(v,w); //取下一个邻接顶点 }}2.图的深度和广度优先遍历函数实现一、深度优先遍历非线性数据结构全文共98页，当前为第42页。非线性数据结构43二、非连通图的深度优先遍历voidAdjMWGraph::DepthFirstSearch(voidVisit(VerTitem))//非连通图G访问操作为Visit()的深度优先遍历{

int*visited=newint[NumOfVertices()];

for(inti=0;i<NumOfVertices();i++)visited[i]=0; //初始化访问标记

for(i=0;i<NumOfVertices();i++) if(!visited[i])DepthFirstSearch(i,visited,Visit); //深度优先遍历

delete[]visited;}非线性数据结构全文共98页，当前为第43页。非线性数据结构44三、广度优先遍历#include"SeqQueue.h" //包含静态数组结构的顺序队列类voidAdjMWGraph::BroadFirstSearch(constintv,intvisited[],voidVisit(VerTitem))//连通图G以v为初始顶点序号、访问操作为Visit()的广度优先遍历//数组visited标记了相应顶点是否已访问过，0表示未访问，1表示已访问{

VerTu,w; SeqQueuequeue; //定义队列

Visit(GetValue(v)); //访问该顶点

visited[v]=1; //置已访问标记

queue.Append(v); //顶点v入队列

while(queue.NotEmpty()) //队列非空时循环 {

u=queue.Delete(); //出队列

w=GetFirstNeighbor(u);//取顶点u的第一个邻接顶点非线性数据结构全文共98页，当前为第44页。非线性数据结构45while(w!=-1) //邻接顶点存在时 {

if(!visited[w]) //若该顶点没有访问过 {

Visit(GetValue(w)); //访问该顶点

visited[w]=1; //置已访问标记

queue.Append(w); //顶点w入队列 } //取顶点u的邻接顶点w的下一个邻接顶点

w=GetNextNeighbor(u,w); } }}非线性数据结构全文共98页，当前为第45页。非线性数据结构46四、非连通图的广度优先遍历voidAdjMWGraph::BroadFirstSearch(voidVisit(VerTitem))//非连通图G访问操作为Visit()的广度优先遍历{

int*visited=newint[NumOfVertices()];

for(inti=0;i<NumOfVertices();i++)visited[i]=0; for(i=0;i<NumOfVertices();i++) if(!visited[i])BroadFirstSearch(i,visited,Visit);

delete[]visited;}非线性数据结构全文共98页，当前为第46页。非线性数据结构47五、程序举例例8-2以图8-8所示的带权有向图为例，编写测试上述图的深度优先和广度优先遍历成员函数的程序。测试程序设计如下：#include<iostream.h>#include<stdlib.h>

typedefcharVerT; //定义邻接矩阵图类中的VerTtypedefcharDataType; //定义顺序表类中的DataTypeconstintMaxVertices=100; //定义最大顶点个数constintMaxQueueSize=100; //定义队列的最大个数constintMaxWeight=10000; //定义权值的无穷大

#include"AdjMWGraph.h" //包含邻接矩阵的图类#include"CreatAdjMWGraph.h" //包含邻接矩阵图的创建函数

voidPrintchar(charitem) //访问操作函数{

cout<<item<<"";}非线性数据结构全文共98页，当前为第47页。非线性数据结构48voidmain(void){ AdjMWGraphg; chara[]={'A','B','C','D','E'}; RowColWeightrcw[]={{0,1,10},{0,4,20},{1,3,30},{2,1,40},{3,2,50}}; intn=5,e=5;

CreatGraph(g,a,n,rcw,e);

cout<<"深度优先搜索序列为：";

g.DepthFirstSearch(Printchar); cout<<endl<<"广度优先搜索序列为：";

g.BroadFirstSearch(Printchar);}测试代码非线性数据结构全文共98页，当前为第48页。非线性数据结构498.5最小生成树1.基本概念一个有n个顶点的连通图的生成树是原图的极小连通子图，它包含原图中的所有n个顶点，并且有保持图连通的最少的边。注意：（1）若在生成树中删除一条边就会使该生成树因变成非连通图而不再满足生成树的定义；（2）若在生成树中增加一条边就会使该生成树中因存在回路而不再满足生成树的定义；（3）一个连通图的生成树可能有许多；（4）有n个顶点的无向连通图，无论它的生成树的形状如何，一定有且只有n-1条边。非线性数据结构全文共98页，当前为第49页。非线性数据结构501V2V3V4V5V6V1V2V3V4V5V6V1V2V3V4V5V6V(a)(b)(c)无向图和它的不同的生成树非线性数据结构全文共98页，当前为第50页。非线性数据结构51最小生成树的实用例子很多例1：N台计算机之间建立通讯网顶点表示computer边表示通讯线权值表示通讯线的代价（通讯线长度，computer间距离等）要求：①n台计算机中的任何两台能通过网进行通讯；②使总的代价最小。--求最小生成树[T]非线性数据结构全文共98页，当前为第51页。非线性数据结构52

最小生成树的实用例子例2：邮递员送信线路[T]顶点表示投递点边表示街道权值表示街道的长度要求：①完成n个投递点的投递；②使总路径长度最短,即求最小生成树[T]非线性数据结构全文共98页，当前为第52页。非线性数据结构53如果无向连通图是一个带权图，那么它的所有生成树中必有一棵边的权值总和最小的生成树，我们称这棵生成树为最小代价生成树，简称最小生成树。构造有n个顶点的无向连通带权图的最小生成树必须满足以下三条：（1）构造的最小生成树必须包括n个顶点；（2）构造的最小生成树中有且只有n-1条边；（3）构造的最小生成树中不存在回路。典型的构造方法有两种，一种称作普里姆（Prim）算法，另一种称作克鲁斯卡尔（Kruskal）算法。非线性数据结构全文共98页，当前为第53页。非线性数据结构542.普里姆算法一、算法思想假设G=(V,E)为一个带权图，其中V为带权图中顶点的集合，E为带权图中边的权值集合。设置两个新的集合U和T，其中U用于存放带权图G的最小生成树的顶点的集合，T用于存放带权图G的最小生成树的权值的集合。普里姆算法思想是：令集合U的初值为U={u0}（即假设构造最小生成树时从顶点u0开始），集合T的初值为T={}。从所有顶点u∈U和顶点v∈V-U的带权边中选出具有最小权值的边(u,v)，将顶点v加入集合U中，将边(u,v)加入集合T中。如此不断重复，当U=V时则最小生成树构造完毕。此时集合U中存放着最小生成树顶点的集合，集合T中存放着最小生成树边的权值集合。非线性数据结构全文共98页，当前为第54页。非线性数据结构55ACBGEFD50604552423065504070ACBGEFDACBGEFD50ACBGEFD5040ACBGEFD505040ACBGEFD50305040ACBGEFD5042305040ACBGEFD504542305040(a)(b)(c)(d)(e)(f)(g)(h)图8-10

普里姆算法构造最小生成树的过程演示非线性数据结构全文共98页，当前为第55页。非线性数据结构56abcdegf课堂练习195141827168213ae12dcbgf7148531621所得生成树权值和=14+8+3+5+16+21=67非线性数据结构全文共98页，当前为第56页。非线性数据结构57二、普里姆函数设计普里姆函数应有两个参数，一个参数是图G，定义为邻接矩阵存储结构图类的对象；另一个参数是通过函数得到的最小生成树的顶点数据和相应顶点的边的权值数据closeVertex。其数据类型定义为如下结构体：structMinSpanTree{ VerTvertex; intweight;};其中，vertex域用来保存最小生成树每条边的弧头顶点数据，weight域用来保存最小生成树的相应边的权值。非线性数据结构全文共98页，当前为第57页。非线性数据结构58普里姆函数设计：voidPrim(AdjMWGraph&G,MinSpanTreecloseVertex[])//用普里姆算法建立带权图G的最小生成树closeVertex{ intn=G.NumOfVertices(),minCost; int*lowCost=newint[n]; inti,j,k;

for(i=1;i<n;i++) //初始化

lowCost[i]=G.GetWeight(0,i);

//从顶点0出发构造最小生成树

closeVertex[0].vertex=G.GetValue(0); //保存顶点0

lowCost[0]=-1; //标记顶点0

for(i=1;i<n;i++) { //寻找当前最小权值的边所对应的弧头顶点k minCost=MaxWeight;//MaxWeight为定义的最大权值非线性数据结构全文共98页，当前为第58页。非线性数据结构59for(j=1;j<n;j++){ if(lowCost[j]<minCost&&lowCost[j]>0) { minCost=lowCost[j]; k=j; }}

closeVertex[i].vertex=G.GetValue(k);//保存弧头顶点k closeVertex[i].weight=minCost; //保存相应的权值

lowCost[k]=-1; //标记顶点k //根据加入集合U的顶点k修改lowCost中的数值

for(intj=1;j<n;j++) { if(G.GetWeight(k,j)<lowCost[j]) lowCost[j]=G.GetWeight(k,j); } }非线性数据结构全文共98页，当前为第59页。非线性数据结构60设计说明：（1）函数中定义一个临时数组lowCost，数组元素lowCost[v]中保存了集合U中顶点ui与集合V-U中顶点vj的所有边中当前具有最小权值的边(u,v)。（2）集合U的初值为U={序号为0的顶点}。lowCost的初始值为邻接矩阵数组中第0行的值，这样初始时lowCost中就存放了从集合U中顶点0到集合V-U中各个顶点的权值。（3）每次从lowCost中寻找具有最小权值的边，根据lowCost的定义，这样的边其弧头顶点必然为集合U中的顶点，其弧尾顶点必然为集合V-U中的顶点。当选到一条这样的边(u,v)，就保存其顶点数据和权值数据到参数closeVertex中，并将lowCost[v]置为-1，表示顶点v加入了集合U中。非线性数据结构全文共98页，当前为第60页。非线性数据结构61（4）当顶点v从集合V-U加入到集合U后，若存在一条边(u,v)，u是集合U的顶点，v是集合V-U的顶点，且边(u,v)较原先lowCost[v]的代价更小，则用这样的权值修改原先lowCost[v]中的相应权值。（5）以图8-10（a）所示的无向连通带权图为例，调用普里姆函数时数组lowCost的动态变化过程如图示。非线性数据结构全文共98页，当前为第61页。非线性数据结构620-115023456lowCost60∞

∞

∞

∞

0-11-123654405660∞

∞

0-11-123504-1570660∞

0-11-123-14-1530642520-11-123-14-15-1642520-11-123-14-15-16-1450-11-123-14-15-16-1-1(a)(b)(c)(d)(e)(f)(g)lowCostlowCostlowCostlowCostlowCostlowCost非线性数据结构全文共98页，当前为第62页。非线性数据结构63函数主要是一个两重循环，其中每一重循环的次数均为顶点个数n，所以该算法的时间复杂度为O(n2)。三、测试程序例8-3以图8-10（a）所示的无向连通带权图为例设计测试上述Prim函数的程序。测试程序非线性数据结构全文共98页，当前为第63页。非线性数据结构643.克鲁斯卡尔算法克鲁斯卡尔算法是一种按照带权图中边的权值的递增顺序构造最小生成树的方法。克鲁斯卡尔算法思想是：设无向连通带权图G=(V,E)，其中V为顶点的集合，E为边的集合。设带权图G的最小生成树T由顶点集合和边的集合构成，其初值为T=(V,{})，即初始时最小生成树T只由带权图G中的顶点集合组成，各顶点之间没有一条边。这样，最小生成树T中的各个顶点各自构成一个连通分量。然后，按照边的权值递增的顺序考察带权图G中的边集合E中的各条边，①若被考察的边的两个顶点属于T的两个不同的连通分量，则将此边加入到最小生成树T，同时把两个连通分量连接为一个连通分量；②若被考察的边的两个顶点属于T的同一个连通分量，则将此边舍去。如此下去，当T中的连通分量个数为1时，T中的该连通分量即为带权图G的一棵最小生成树非线性数据结构全文共98页，当前为第64页。非线性数据结构65ACBGEFD30ACBGEFD3040ACBGEFD423040ACBGEFD45423040ACBGEFD5045423040ACBGEFD504542305040(a)(b)(c)(d)(e)(f)克鲁斯卡尔算法构造最小生成树的过程演示非线性数据结构全文共98页，当前为第65页。非线性数据结构66abcdegf195141827168213ae12dcbgf7148531621课堂练习：7121819非线性数据结构全文共98页，当前为第66页。非线性数据结构67补充:有向无环图的应用1、拓扑排序（TopologicalSort）

AOV-网：用顶点表示活动，用弧表示活动间的优先关系的有向无环图，称为顶点表示活动的网（ActivityOnVertexNetwork），简称为AOV-网。

如下：表7-2课程关系，用顶点表示课程，弧表示先决条件，则表7-2可用一个有向无环图表示。非线性数据结构全文共98页，当前为第67页。非线性数据结构68表7-2课程关系非线性数据结构全文共98页，当前为第68页。非线性数据结构69拓扑序列：在有向图G=（V，{E}）中，

V中顶点的线性序列（vi1,,vi1,,vi3,…，vin）称为拓扑序列。此序列必须满足：对序列中任意两个顶点vi、vj，在G中有一条从vi到vj的路径，则在序列中vi必排在vj之前。

如前图的一个拓扑序列为：C1,C2,C3,C4,C5,C8,C9,C7,C6。

非线性数据结构全文共98页，当前为第69页。非线性数据结构70AOV-网的特性如下：

若vi为vj的先行活动，vj为vk的先行活动，则vi必为vk的先行活动，即先行关系具有可传递性。AOV-网的拓扑序列不是唯一的。

对图7.21的另一个拓扑序列为：C1,C2,C3,C8,C4,C5,C9,C7,C6非线性数据结构全文共98页，当前为第70页。非线性数据结构71求拓扑排序的基本思想：（1）从有向图中选一个无前驱的顶点输出；（2）将此顶点和以它为起点的弧删除；（3）重复（1）、（2），直到不存在无前驱的顶点；（4）若此时输出的顶点数小于有向图中的顶点数，则说明有向图中存在回路，否则输出的顶点的顺序即为一个拓扑序列。

例如图7.22所示的AOV－网，其拓扑序列为：v1,v6,v4,v3,v2,v5或v1,v3,v2,v6,v4,v5非线性数据结构全文共98页，当前为第71页。非线性数据结构72

V1

V6

V2

V4

V3

V5图7.22AOV-网v1,v6,v4,v3,v2,v5v1,v3,v2,v6,v4,v5分析其执行过程非线性数据结构全文共98页，当前为第72页。非线性数据结构73abcghdfeabhcdgfe课堂练习：求出上图的一个拓扑序列。非线性数据结构全文共98页，当前为第73页。非线性数据结构742、关键路径AOE-网：在有向图中，用顶点表示事件，用弧表示活动，弧的权值表示活动所需要的时间。我们把用这种方法构造的有向无环图叫做边表示活动的网（ActivityOnEdgeNetwork）,简称AOE-网。

AOE-网用在工程计划和管理中，人们最关心的是：哪些活动是影响工程进度的关键活动？至少需要多长时间能完成整个工程？非线性数据结构全文共98页，当前为第74页。非线性数据结构75源点：存在唯一的、入度为零的顶点，叫源点。汇点：存在唯一的、出度为零的顶点，叫汇点。关键路径：从源点到汇点的最长路径的长度即为完成整个工程任务所需的时间，该路径叫做关键路径。关键活动：关键路径上的活动叫做关键活动。

在AOE-网中的基本概念：如图7.24所示的AOE-网。v0为源点，表示整个工程可以开始，v8为汇点，表示整个工程结束。非线性数据结构全文共98页，当前为第75页。非线性数据结构76410235678a1=6a2=4a3=5a5=1a6=2a9=4a4=1a10=2a11=4a8=7a7=9图7.24AOE-网v0为源点v8为汇点非线性数据结构全文共98页，当前为第76页。非线性数据结构77abcdefghk64521187244例如:整个工程完成的时间为：从有向图的源点到汇点的最长路径。源点汇点6174非线性数据结构全文共98页，当前为第77页。非线性数据结构78几个重要的定义：事件vi的最早发生时间ve(i)：从源点到顶点vi的最长路径的长度，叫做事件vi的最早发生时间。求ve(i)时可从源点开始，按拓扑顺序向汇点递推：ve(0)=0；

ve(i)=Max{ve(k)＋dut(<k,i>)}<k,i>∈T,1≤i≤n-1;其中，T为所有以i为头的弧<k,i>的集合，dut（<k,i>）表示与弧<k,i>对应的活动的持续时间。非线性数据结构全文共98页，当前为第78页。非线性数据结构79事件vi的最晚发生时间vl(i)：在保证汇点按其最早发生时间发生这一前提下，事件vi的最晚发生时间。在求出ve(i)的基础上，可从汇点开始，按逆拓扑顺序向源点递推，求出vl(i)：vl(n-1)=ve(n-1)；

vl(i)=Min{vl(k)＋dut(<i,k>)}<i,k>∈S,0≤i≤n-2;其中，S为所有以i为尾的弧<i,k>的集合，dut（<i,k>）表示与弧<i,k>对应的活动的持续时间。

非线性数据结构全文共98页，当前为第79页。非线性数据结构80活动ai的最早开始时间e(i)：如果活动ai对应的弧为<j,k>，则e(i)等于从源点到顶点j的最长路径的长度，即：e(i)=ve(j)

活动ai的最晚开始时间l(i)：如果活动ai对应的弧为<j,k>，其持续时间为dut（<j,k>）则有：l(i)=vl(k)-dut（<j,k>）

活动ai的松弛时间（时间余量）：ai的最晚开始时间与ai的最早开始时间之差：l(i)-e(i)。显然，松弛时间（时间余量）为0的活动为关键活动。

非线性数据结构全文共98页，当前为第80页。非线性数据结构81求关键路径的基本步骤：（1）对图中顶点进行拓扑排序，在排序过程中按拓扑序列求出每个事件的最早发生时间ve(i)；（2）按逆拓扑序列求每个事件的最晚发生时间vl(i)；（3）求出每个活动ai的最早开始时间e(i)和最晚发生时间l(i)；

(4)找出e(i)=l(i)的活动ai，即为关键活动。

注意哟非线性数据结构全文共98页，当前为第81页。非线性数据结构82图7.24非线性数据结构全文共98页，当前为第82页。非线性数据结构83计算结果非线性数据结构全文共98页，当前为第83页。非线性数据结构84

0

1

4

8

6

7a1a7a8a11a10a4图7.25关键路径课后作业：教材245页第3题非线性数据结构全文共98页，当前为第84页。非线性数据结构858.6最短路径1.基本概念路径长度:一条路径上所经过的边的数目带权路径长度:路径上所经过边的权值之和最短路径:(带权)路径长度(值)最小的那条路径最短路径长度或最短距离:其(带权)路径长度

图8-13（a）有向带权图；（b）邻接矩阵EFDBCA825301810715úúúúúúúúûùêêêêêêêêë饥¥¥¥¥¥¥¥¥¥¥¥¥¥¥¥¥¥¥¥0181004070158023050(a)(b)4非线性数据结构全文共98页，当前为第85页。非线性数据结构862.从一个顶点到其余各顶点的最短路径一、狄克斯特拉算法思想按路径长度递增的顺序逐步产生最短路径，狄克斯特拉算法的思想是：设置两个顶点的集合S和T，集合S中存放已找到最短路径的顶点，集合T中存放当前还未找到最短路径的顶点。初始状态时，集合S中只包含源点，设为v0，然后从集合T中选择到源点v0路径长度最短的顶点u加入到集合S中，集合S中每加入一个新的顶点u都要修改源点v0到集合T中剩余顶点的当前最短路径长度值，集合T中各顶点的新的当前最短路径长度值，为原来的当前最短路径长度值与从源点过顶点u到达该顶点的路径长度中的较小者。此过程不断重复，直到集合T中的顶点全部加入到集合S中为止。非线性数据结构全文共98页，当前为第86页。非线性数据结构87EFDBCA51810715EFDBCA530(a)EFDBCA530715EFDBCA5301810715EFDBCA851810715EFDBCA8510715(b)(c)(d)(e)(f)狄克斯特拉算法求从顶点A到其余各顶点最短路径的过程非线性数据结构全文共98页，当前为第87页。非线性数据结构88源点终点最短路径路径长度V0V2V0，V210V3V0，V2，V325V1

V0，V2，V3，V145V4V0，V445V5无最短路径表7.3v0到其他顶点的最短路径V150

20

1010

30V0V4V2V3V545

15

353

15

20非线性数据结构全文共98页，当前为第88页。非线性数据结构89二、狄克斯特拉函数设计参数设计：函数共有4个参数，其中2个为输入参数，分别为带权图G和源点序号v0；2个为输出参数，分别为distance[]和path[]，distance[]用来存放得到的从源点v0到其余各顶点的最短距离数值，path[]用来存放得到的从源点v0到其余各顶点的最短路径上到达目标顶点的前一顶点下标。狄克斯特拉函数设计：voidDijkstra(AdjMWGraph&G,intv0,intdistance[],intpath[])//带权图G从下标v0顶点到其他顶点的最短距离distance//和相应的目标顶点的前一顶点下标path{ intn=G.NumOfVertices(); int*s=newint[n]; //s用来存放n个顶点的标记

intminDis,i,j,u;非线性数据结构全文共98页，当前为第89页。非线性数据结构90

//初始化

for(i=0;i<n;i++) { distance[i]=G.GetWeight(v0,i); s[i]=0; //初始均标记为0

if(i!=v0&&distance[i]<MaxWeight)path[i]=v0; //初始的目标顶点的前一顶点均