工学山东科技大学数据结构课图

会计学1工学山东科技大学数据结构课图主要内容7.1图的定义和术语

7.2图的基本操作

7.3图的存储结构

7.4图的遍历

7.5生成树和最小生成树第1页/共119页7.1图的定义和术语一图的定义图G由两个集合构成，记作G=<V,E>其中V是顶点的非空有限集合，E是边的有限集合，其中边是顶点的无序对或有序对集合。G1=<V1,E1>V1={v0,v1,v2,v3,v4}E1={(v0,v1),(v0,v3),(v1,v2),(v1,v4),(v2,v3)(v2,v4)}无序对(vi,vj)：用连接顶点vi、vj的线段表示，称为无向边；

V0

V4

V3

V1

V2例G1图示第2页/共119页7.1图的定义和术语G2图示有序对<vi,vj>：用以为vi起点、以vj为终点的有向线段表示，称为有向边或弧；

V0

V1

V2

V3G2=<V2,E2>V2={v0v1,v2,v3}E2={<v0,v1>

,<v0,v2>,<v2,v3>,<v3,v0>}第3页/共119页图的应用举例：例1交通图（公路、铁路）顶点：地点边：连接地点的公路交通图中的有单行道双行道，分别用有向边、无向边表示；例2电路图顶点：元件边：连接元件之间的线路例3通讯线路图顶点：地点边：地点间的连线例4各种流程图如产品的生产流程图顶点：工序边：各道工序之间的顺序关系

V0

V4

V3

V1

V2

V0

V1

V2

V37.1图的定义和术语第4页/共119页二图的基本术语

V0

V4

V3

V1

V2

V0

V1

V2

V37.1图的定义和术语1)无向图（undigraph）：在图G中，若所有边是无向边，则称G为无向图；2)有向图（digraph）：在图G中，若所有边是有向边，则称G为有向图；混和图：在图G中，即有无向边也有有向边，则称G为混合图；3)无向完全图：任意两顶点间都有边的图称为无向完全图。在一个含有n个顶点的无向完全图中，有n(n-1)/2条边。4）有向完全图：任意两顶点之间都有方向互为相反的两条弧相连接的有向图称为有向完全图。在一个含有n个顶点的有向完全图中，有n(n-1)条弧。5）稠密图/稀疏图：若边数为e，顶点数为n，边数稀少到e<nlogn，则称该图为稀疏图，否则该图为稠密图。第5页/共119页6）顶点的度、入度、出度邻接点：边的两个顶点关联边：若边e=(v,u),则称顶点v、u关联边在无向图中：顶点V的度=与V相关联的边的数目，记作TD(V)

在有向图中：顶点V的出度=以V为起点有向边数，记作OD(V)

顶点V的入度=以V为终点有向边数，记作ID(V)

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

7.1图的定义和术语

V0

V4

V3

V1

V2

V0

V1

V2

V3TD(V0)=2TD(V1)=3TD(V2)=3TD(V3)=2TD(V4)=2ID(V0)=1OD(V0)=2TD(V0)=3ID(V1)=1OD(V1)=0TD(V1)=1ID(V2)=1OD(V2)=1TD(V2)=2ID(V3)=1OD(V3)=1TD(V3)=2第6页/共119页

7)边的权：在图的边或弧上表示数字，表示与该边相关的数据信息，这个数据信息就称该边的权（weight）。8）网（network）：边（或弧）上带权的图称为网。9）路径、回路

无向图G=（V，E）中的顶点序列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中，V0,V1,V2,V3是V0到V3的路径；V0,V1,V2,V3,V0是回路；在图2中，V0,V2,V3是V0到V3的路径；V0,V2,V3,V0是回路；无向图G1有向图G2

V0

V4

V3

V1

V2

V0

V1

V2

V3例7.1图的定义和术语第7页/共119页

10)简单路径和简单回路

在一条路径中,若除起点和终点外,所有顶点各不相同,则称该路径为简单路径； 由简单路径组成的回路称为简单回路；

在图1中，V0,V1,V2,V3是简单路径；V0,V1,V2,V4,V1不是简单路径；在图2中，V0,V2,V3,V0是简单回路；7.1图的定义和术语无向图G1有向图G2

V0

V4

V3

V1

V2

V0

V1

V2

V3例第8页/共119页11）子图

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

(b)、(c)是(a)的子图(a)(b)(c)

V0

V4

V3

V1

V2

V0

V4

V3

V1

V2

V0

V4

V3

V1

V27.1图的定义和术语第9页/共119页12）连通图（强连通图）在无（有）向图G=<V,E>中，若对任何两个顶点v、u都存在从v到u的路径，则称G是连通图（强连通图）

非连通图

连通图

强连通图

非强连通图

V0

V1

V2

V3

V0

V4

V3

V1

V2

V0

V1

V2

V3

V0

V2

V3

V1

V5

V47.1图的定义和术语第10页/共119页13）连通分图（强连通分量）无向图G的极大连通子图称为G的连通分量极大连通子图意思是：该子图是G连通子图，将G的任何不在该子图中的顶点加入，子图不再连通；

连通分图非连通图

V0

V2

V3

V1

V5

V4

V0

V2

V1非连通分图7.1图的定义和术语第11页/共119页有向图D的极大强连通子图称为D的强连通分量极大强连通子图意思是：该子图是D强连通子图，将D的任何不在该子图中的顶点加入，子图不再是强连通的；强连通分量

V0

V1

V2

V3

V0

V2

V3

V17.1图的定义和术语第12页/共119页14)生成树包含无向图G所有顶点的的极小连通子图称为G的生成树极小连通子图意思是：该子图是G的连通子图，在该子图中删除任何一条边，子图不再连通，若T是G的生成树当且仅当T满足如下条件

T是G的连通子图

T包含G的所有顶点

T中无回路连通图G1G1的生成树

V0

V4

V3

V1

V2

V0

V4

V3

V1

V2

V0

V4

V3

V1

V27.1图的定义和术语第13页/共119页生成树：极小连通子图，它含有图中全部全部顶点，但是只有足以构成一棵树的n-1条边。一棵有n个顶点的生成树有且仅有n-1条边。无法将图中顶点排列成一个唯一的线性序列，任何一个顶点都可被看成是第一个顶点。任一个顶点的邻接点之间也不存在次序关系。第14页/共119页7.2图的基本操作图有以下基本操作：1）CreatGraph（G）：输入图G的顶点和边，建立图G的存储。2）DFSTraverse（G,V）：从图G的一个顶点V出发深度优先遍历图G。3）BFSTraverse（G,V）：从图G的一个顶点V出发广度优先遍历图G。第15页/共119页图的存储结构至少要保存两类信息：

1)顶点的数据

2)顶点间的关系约定:G=<V,E>是图,V={v0,v1,v2,…vn-1},设顶点的角标为它的编号

如何表示顶点间的关系？顶点的编号

？

V0

V4

V3

V1

V2

V0

V1

V2

V37.3图的存储表示第16页/共119页1邻接矩阵：G的邻接矩阵是满足如下条件的n阶矩阵：A[i][j]=1若(vi,vi+1)E或<vi,vi+1>E0否则01010010101011010001100011000000001000一邻接矩阵表示

V0

V4

V3

V1

V2

V0

V1

V2

V37.3图的存储表示第17页/共119页无向图邻接矩阵表示法特点：1）无向图邻接矩阵是对称矩阵，同一条边表示了两次；2）顶点v的度：等于二维数组对应行（或列）中1的个数；3）判断两顶点v、u是否为邻接点：只需判二维数组对应分量是否为1；4）顶点不变，在图中增加、删除边：只需对二维数组对应分量赋值1或清0；5）设图的顶点数为n,存储图用一维数组,数组元素有m个（m>=n),则G占用存储空间：m+n2；G占用存储空间只与它的顶点数有关，与边数无关；适用于边稠密的图；对有向图的数组表示法可做类似的讨论

01010010101011010001100邻接矩阵表示法的空间代价只与图的顶点数有关

V0

V4

V3

V1

V27.3图的存储表示第18页/共119页图的基本操作：1）求无向图某顶点vi的度(或有向图中vi的出度)。A[i][0]到A[i][n-1]中的非0个数，即数组A中第i行的非0元素的个数；2）求有向图某顶点vi的入度。：A[0][i]到A[n-1][i]中的非0个数，即数组A中第i列的非0元素的个数；3）检测图中的总边数。扫描整个数组A，统计出数组中非0元素的个数。无向图的总边数为非0元素个数的一半，而有向图的总弧数为非0元素个数；

V0

V4

V3

V1

V2

V0

V1

V2

V3010100101010110100011000110000000010007.3图的存储表示第19页/共119页邻接矩阵表示法对求顶点的度很方便。在无向图中：顶点的度数=矩阵中对应该顶点的行或列中非零元素的个数。在有向图中：顶点的出度=矩阵中对应该顶点的行中非零元素的个数。顶点的入度=矩阵中对应该顶点的列中非零元素的个数。第20页/共119页V1V3V2V4V1V3V2V4

V1V2V3V4

V1

0010

V20001

V30001

V41000

V1V2V3V4

V1

0111

V21001

V31000

V41100入度出度11112101度数3212第21页/共119页V1V3V2V4

V1V2V3V4

V1∞

∞2∞

V2∞

∞

∞8

V3

∞

9

∞6

V44∞

∞

∞

2846网及其邻接矩阵9便于找一个图中某个顶点的邻接点序列第22页/共119页邻接表

邻接表是图的链式存储结构：即对图中每个顶点建立一个单链表，第i个单链表中的结点表示依附于该顶点Vi的边（或弧）1无向图的邻接表顶点：通常按编号顺序将顶点数据存储在一维数组中；关联同一顶点的边：用线性链表存储该结点表示边（ViVj）,其中的1是Vj在一维数组中的位置例

V0

V4

V3

V1

V22

01234m-1V0V1V2V3V413422110034下标编号link7.3图的存储表示第23页/共119页图的邻接表类型定义structnode//边（弧）结点的类型定义{intvertex;//边（弧）的另一顶点的在数组中的位置

structnode*link;//指向下一条边（弧）结点的指针};typedefstructNODE；NODEadjlist[MAX];//邻接点链表的头指针所对应的数组7.3图的存储表示第24页/共119页无向图的邻接表的特点

1）在G邻接表中，同一条边对应两个结点；

2）顶点v的度：等于v对应线性链表的长度；

3）判定两顶点v，u是否邻接：要看v对应线性链表中有无对应的结点

4）在G中增减边：要在两个单链表插入、删除结点；

5）设存储顶点的一维数组大小为m(m图的顶点数n),图的边数为e，G占用存储空间为：m+2*e。G占用存储空间与G的顶点数、边数均有关；适用于边稀疏的图

01234m-1V0V1V2V3V413422110043邻接表的空间代价与图的边及顶点数均有关

V0

V4

V3

V1

V227.3图的存储表示第25页/共119页2有向图的邻接表和逆邻接表1）有向图的邻接表顶点：用一维数组存储（按编号顺序）以同一顶点为起点的弧：用线性链表存储类似于无向图的邻接表，所不同的是：以同一顶点为起点的弧：用线性链表存储下标编号link

V0V1V2V31230

0123m-1例

V0

V1

V2

V37.3图的存储表示第26页/共119页2）有向图的逆邻接表顶点：用一维数组存储（按编号顺序）以同一顶点为终点的弧：用线性链表存储V0V1V2V3

0123m-10023

类似于有向图的邻接表，所不同的是：以同一顶点为终点弧：用线性链表存储例

V0

V1

V2

V37.3图的存储表示第27页/共119页

建立邻接表的算法建立无向邻接表

intcreate(NODE*adjlist[]){NODE*p;intnum,i,v1,v2;scanf(“%d\n”,&num);//读入结点数

for(i=0;i<num;i++)//初始化空关系图

{adjlist[i].link=NULL;adjlist[i].vertex=i;}7.3图的存储表示第28页/共119页for(;;){scanf(“%dto%d\n”,&v1,&v2);//读入一条边

if(v1<0||v2<0)break;//数据输入的终止条件

p=(NODE*)malloc(sizeof(NODE));p->vertex=v2;p->link=adjlist[v1].link;adjlist[v1].link=p;//插入在链表首部

p=(NODE*)malloc(sizeof(NODE));p->vertex=v1;p->link=adjlist[v2].link;adjlist[v2].link=p;}return(num);//返回图的结点数}7.3图的存储表示第29页/共119页（3）十字链表V1V2V3V401v1v2∧v3v4012302∧2023∧∧30∧31∧32∧∧tailvexheadvexhlinktlinkinfodatafirstinfirstout第30页/共119页弧头相同的弧在同一链表上，弧尾相同的弧在同一链表上。十字链表也可以看成是邻接矩阵的链表存储结构。第31页/共119页（4）邻接多重表V1V3V2V4

1

2

3

4211∧134∧4∧2∧邻接表第32页/共119页V1V2V4V5v1v2v3v4v5342120∧0∧V30123421∧431∧v1v2v3v4v501012340∧3∧212341∧2∧4∧mark顶点位置下一邻边第33页/共119页邻接多重表中，所有依附于同一顶点的边串联在同一链表中。由于每条边依附于两个顶点，则每个边结点同时链接在两个链表中。与邻接表的区别：用来表示同一条边的结点个数不同。在存储量问题上，存储容量大致相同。第34页/共119页

在不同的存储结构下，实现各种操作的效率可能是不同的。所以在求解实际问题时，要根据求解问题所需操作，选择合适的存储结构。7.3图的存储表示第35页/共119页

图的遍历：从图的某顶点出发，访问图中所有顶点，并且每个顶点仅访问一次。在图中，访问部分顶点后，可能又沿着其他边回到已被访问过的顶点。为保证每一个顶点只被访问一次，必须对顶点进行标记，一般用一个辅助数组visit[MAX]作为对顶点的标记，当顶点vi未被访问，visit[i]值为0；当vi已被访问，则visit[i]值为1。

图的遍历与树的遍历有什么不同？

有两种遍历方法（它们对无向图，有向图都适用）深度优先遍历广度优先遍历7.4图的遍历第36页/共119页

一、深度优先遍历从图中某顶点v出发：1）访问顶点v；

2）依次从v的未被访问的邻接点出发，继续对图进行深度优先遍历；直至图中所有和v有路径相通的顶点都被访问到；3）若此时图中尚有顶点未被访问，则另选图中一个未被访问的顶点作起始点，重复上述过程。直至图中所有顶点都被访问到。

V0,V1,V3,V7,V4,V2,V5,V6,

由于没有规定访问邻接点的顺序，深度优先序列不是唯一的这是序列（1）在遍历过程中所经过的路径例求图G以V0起点的的深度优先序列：V0,V1,V4,V7,V3,V2,V5,V6

V0

V7

V6

V5

V4

V3

V2

V1

V0

V1

V3

V2

V7

V6

V5

V47.4图的遍历第37页/共119页如果将图顶点的邻接点看作二叉树结点的左、右孩子深度优先遍历与先序遍历是不是很类似？深度优先遍历从图中某顶点v出发：（1）访问顶点v；

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

先序遍历（DLR）若二叉树非空

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

（3）先序遍历右子树；

V0

V7

V6

V5

V4

V3

V2

V17.4图的遍历第38页/共119页结点定义typedefstructnode{intvertex;//边（弧）的另一顶点在数组中的位置

structnode*link;//指向下一条边（弧）结点的指针};typedefstructNODE；NODEadjlist[MAX];//邻接点链表的头指针所对应的数组辅助数组

intvisit[MAX];//顶点标志数组,全局变量

NODE*ptr[MAX];//顶点链表指针数组visit01234m-100000深度优先遍历算法7.4图的遍历第39页/共119页voiddepthfirst(NODEadjlist[],intnum){inti;for(i=0;i<num;i++){ptr[i]=adjlist[i].link;//记住每个顶点链表的第一个结点的地址

visit[i]=0;//给每个结点一个未访问标记

}for(i=0;i<num;i++)if(visit[i]==0)dfs(i);//调用以顶点vi为出发点的深度优先遍历图G的算法

}图G的深度优先遍历算法

V0

V2

V3

V1

V5

V4深度优先遍历7.4图的遍历第40页/共119页voiddfs(intv){intw;printf(“%d,“,v);visit[v]=1;//访问此结点

while(ptr[v]！=NULL）

{w=ptr[v]->vertex;取结点的邻接顶点wif(visit[w]==0;)dfs(w);ptr[v]=ptr[v]->link;//记住顶点v的邻接顶点位置，

}该邻接点在w之后

}从第v个顶点出发，递归地深度优先遍历图G。7.4图的遍历第41页/共119页调用深度优先遍历算法的主函数

main(){NODEadjlist[MAX];intnum;num=create(adjlist);/*建立图G的邻接表*/depthfirst(adjlist,num);/*调用对图G深度优先搜索算法*/}深度优先遍历算法7.4图的遍历第42页/共119页

V0

V7

V6

V5

V4

V3

V2

V1

01234567V0V1V2V3V4V5V6V71201157730642652437.4图的遍历第43页/共119页如果将图顶点的邻接点看作二叉树结点的左、右孩子深度优先遍历算法与先序遍历算法的结构是不是很像？深度优先遍历算法voiddfs(intv){intw;printf(“%d,“,v);visit[v]=1;//访问此结点

while(ptr[v]！=NULL）

{w=ptr[v]->vertex;取结点的邻接顶点wif(visit[w]==0;)dfs(w);ptr[v]=ptr[v]->link;//记住顶点v的邻接点位置，

}该邻接点在w之后

}

先序遍历递归算法

voidprev(NODE*root)

{if(root!=NULL)

{printf(“%d,”,root->data)；

//访问此结点

prev(root->lch);//访问孩子结点

prev(root->rch);

}}比较7.4图的遍历第44页/共119页图中某未访问过的顶点vi出发：1）访问顶点vi；2）访问vi的所有未被访问的邻接点w1,w2,…wk

；3）依次从这些邻接点出发，访问它们的所有未被访问的邻接点;依此类推，直到图中所有访问过的顶点的邻接点都被访问；二、广度优先遍历（类似于树的按层遍历）

V0

V7

V6

V5

V4

V3

V2

V1V0

V1

V3

V2

V7

V6

V5

V4这是序列（1）在遍历过程中所经过的路径由于没有规定访问邻接点的顺序，广度优先序列不是唯一的例求图G的以V0起点的的广度优先序列:V0,V1,V2,V3,V4,V5,V6,V77.4图的遍历第45页/共119页从图中某顶点vi出发：1）访问顶点vi；（容易实现）2）访问vi的所有未被访问的邻接点w1,w2,…wk

；（容易实现）3）依次从这些邻接点（在步骤2）访问的顶点）出发，访问它们的所有未被访问的邻接点;依此类推，直到图中所有访问过的顶点的邻接点都被访问；为实现3），需要保存在步骤(2）中访问的顶点，而且访问这些顶点邻接点的顺序为：先保存的顶点，其邻接点先被访问。广度优先遍历算法在广度优先遍历算法中，需设置一队列Q，保存已访问的顶点，并控制遍历顶点的顺序。

V0

V7

V6

V5

V4

V3

V2

V17.4图的遍历第46页/共119页广度优先遍历从图中某顶点v出发：1）访问顶点v；2）访问v的所有未被访问的邻接点w1,w2,…wk

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

V0

V7

V6

V5

V4

V3

V2

V1QV1V2V3V0V4V5V6V7V0V1V2V3V4V5V6V77.4图的遍历第47页/共119页在广度优先遍历算法中，需设置一队列

Q，保存已访问的顶点，并控制遍历顶点的顺序intvisit[MAX];intqueue[MAX],front=0,rear=0;

7.4图的遍历第48页/共119页voidbft(intv)//从v出发，广度优先遍历图G。

{intw;NODE*p;visit[v]=1;printf(“%d,”,v);

enter(v);//enter(v)为入队列函数

while((v=leave())!=NULL);//leave()为出队列函数

{p=adjlist[v].link;//p指向出队列顶点v的第一个邻接点

while(p!=NULL){w=p->vertex;//遍历v所指的整个链表

if(visit[w]==0)//如果w未被访问过

{printf(“%d,”,w);//访问wvisit[w]=1;enter(w);访问后，w入队

}p=p->link;}}}7.4图的遍历第49页/共119页main(){intnum;num=create(adjlist);breadfirst(num);//调用对图G广度遍历图算法

}voidbreadfirst(intnum){int;for(i=0;i<num;i++)visit[i]=0;//给所有顶点一个未被访问标记

for(i=0;i<num;i++)if(visit[i]==0)bft(i);//调用以顶点vi为出发点的是广度优先遍历图G的算法

}第50页/共119页

01234567V0V1V2V3V4V5V6V7120115773064265243第51页/共119页

V0

V2

V3

V1

V5

V4

V0

V2

V3

V1

V5

V4深度优先遍历广度优先遍历两种遍历的比较7.4图的遍历第52页/共119页7.5生成树和最小生成树7.5.1

无向图的连通分量和生成树深度遍历P159图G3，得到的序列为：ALMJBFCDEGKHI第53页/共119页生成树生成树是一个连通图G的一个极小的连通子图。包含图G的所有顶点，但只有n-1条边，并且是连通的。生成树可由遍历过程中所经过的边组成。深度优先遍历得到的生成树称为深度优先生成树；广度优先遍历得到的生成树称为广度优先生成树。

V0

V7

V6

V5

V4

V3

V2

V1

V3

V0

V7

V6

V5

V4

V2

V1深度优先生成树广度优先生成树7.5生成树和最小生成树第54页/共119页

要在n个城市间建立交通网，要考虑的问题如何在保证n点连通的前题下最节省经费?V2V0V3V5V4如何求连通图的最小生成树?？7.5.2最小生成树（最小支撑树）

若有一个连通的无向图G，有n个顶点，并且它的边是有权值的。在G上构造生成树G’

,最小生成树n-1条边的权值之和最小的G’

。7.5生成树和最小生成树第55页/共119页MST性质：假设N=(V,{E})是一个连通网，若(u,v)是一条具有最小权值（代价）的边，则必存在一棵包含边(u,v)的最小生成树。普里姆算法克鲁斯卡尔算法第56页/共119页普鲁姆算法基本步骤设G=（V，E）为一个具有n个顶点的带权的连通网络，T=（U，TE）为构造的生成树。（1）初始时，U={u0}，TE=；（2）在所有uU、vV-U的边（u,v）中选择一条权值最小的边，不妨设为（u,v)；（3）(u,v)加入TE，同时将u加入U；（4）重复(2)、（3），直到U=V为止；(1)普鲁姆算法V2V0V3V5V4V136521655467.5生成树和最小生成树第57页/共119页V2V0V3V5V42V0V3V5V4V112V2V0V3V5V4V114V2V0V3V5V4V1142V2V0V3V5V4V11452V3V0V3V5V4V11453U={V0}U={V0,V2}U={V0,V2,V5}U={V0,V2,V5,V3}U={V0,V2,V5,V3,V1}U={V0,V2,V5,V3,V1,V4}第58页/共119页有关数据的存储结构无向连通网络:G

为选择权值最小的边:置一个一维数组：closest[]，对iV-Uclosest[i]=j(jU)(j,i)是一条边，且是i到U中各顶点“权最小边”Lowcost[i]：用来保存连接i到U中各顶点“权最小边”的权。

普鲁姆算法涉及的数据和操作：数据：无向连通网络操作:选择权值最小的边，不妨设为（u,v)(u,v)加入TE，u加入UV2V0V3V5V4V-UviUV-Uvivj7.5生成树和最小生成树第59页/共119页V2V0V3V5V40000000615maxmax

iclosest[i]lowcost[i]

012345iclosest[i]lowcost[i]

01234502002

205

056

4U={v0}U={v0,v2}V2V0V3V5V4U对iV-Uclosest[i]=j(jU)(j,i)是一条边，且是i到U中各顶点“权最小边”Lowcost[i]：用来保存连接i到U中各顶点“权最小边”的权。V-U={v1,V2,V3,V4,V5}V-U={v1,V3,V4,V5}7.5生成树和最小生成树第60页/共119页

000000

06

1

5maxmax

lowcost{0}

020022

05056

4

closestlowcost{0,2}

020522

050

2

60

closestlowcost{0,2,5}

020522

0

5

0060

closestlowcost{0,2,5,3}

020512

0000

3

0closestlowcost{0,2,5,3,1}

020512

000000

closestlowcost{0,2,5,3,1,4}iclosest

012345U7.5生成树和最小生成树第61页/共119页普里姆算法图采用邻接矩阵表示，邻接矩阵所对应的二维数组是cost[MAX][MAX],则

(1)初始化(U={0}),closest[i]=0;lowcost[i]=cost[0][i];lowcost[0]=0;(i=1,2,3,…n-1;)(2)每次扫描数组lowcost[i]，找出值最小且不为0的lowcost[k]，得到最小生成树的一条边（closest[k],k]),将其输出。（3）令lowcost[k]=0,将k并入U中（4）修改数组closest[i]和lowcost[i]（lowcost[i]！=0及i∈V-U（5）重复（2）（3）（4），直到U=V（或循环n-1次）结束

7.5生成树和最小生成树第62页/共119页普里姆算法viudPRIM(intcost[][N],intstart_v){intclosest[N],lowcost[N],i,j,k,min;for(i=0;j<N;i++){lowcost[i]=cost[start_v][i];closest[i]=start_v;}for(i=1;i<N;i++)//循环n-1次，每次求出最小生成树的一条边

{min=MAX;for(j=0;j<N;j++)if(lowcost[j]!=0&&lowcost[j]<min){min=lowcost[j];k=j;}//找出值最小的lowcost[k]printf(“%d,%d:%d\n”,closest[k],k,lowcost[k]);lowcost[k]=0;//将k并入U中

for(j=0;j<N;j++)//修改lowcost[]和closest[]if(cost[k][j]!=0&&cost[k][j]<lowcost[j]){lowcost[j]=cost[k][j];closest[j]=k;}}}7.5生成树和最小生成树第63页/共119页基本步骤设G=（V，E）为一个具有n个顶点的带权的连通网络，最小生成树的初始状态为有n个顶点但无边的非连通图T=（V，）。（1）将E中的边按权值的递增顺序排序，选择权值最小的边，若与相关的顶点落在T中不同的连通分量上，则将其加入T中，否则，将其弃舍。（2）循环至所有顶点在同一的连通分量上。如何识别一条边所相关的顶点是否落在同一个连通分量上？可将一个连通分量的所有顶点看成一个集合，当从E中取出一条边（xi,xj）时，若xi,xj在同一集合u中，则将该边弃舍；否则，则将该边加入到T中，并将xj所在的集合v并入集合u中。（2）克鲁斯卡尔算法V2V0V3V5V4V136521655467.5生成树和最小生成树第64页/共119页需要引入辅助数组sets[]（1）初始化：图G中的n个顶点，构成n个连通分量，顶点xi对应的连通分量用集合i表示，所以sets[i]=i,即表示第i个顶点在集合i中。（2）依次取出E中的边（按边权值递增顺序），设取出的边为（xi,xj）。（3）判断：若sets[i]=sets[j],则表示xi和xj在同一集合中，返回（2）；否则，转到（4）。（4）将边（xi,xj）并入T，同时将xj所在的集合v（与xj连通的顶点）并入xi所在的集合u（与xi连通的顶点），即：由v=sets[j]和u=sets[i]，扫描辅助数组sets[]，若sets[k]=v,则令sets[k]=u。返回（2）。（5）重复（2）、（3）、（4），取出n-1条边。012345012345

下标setsV2V0V3V5V4V136521655467.5生成树和最小生成树第65页/共119页V2V0V3V5V4V13652165546012345012345

下标sets012345012345

下标sets031001111V2V0V3V5V4V1123457.5生成树和最小生成树第66页/共119页V2V0V3V5V4V13652165546012345012345

下标sets012345012345

下标setsV2V0V3V5V4V17.5生成树和最小生成树第67页/共119页V2V0V3V5V4V13652165546012345012345

下标sets010345012345

下标setsV2V0V3V5V4V117.5生成树和最小生成树第68页/共119页V2V0V3V5V4V13652165546012345012345

下标sets010343

012345

下标setsV2V0V3V5V4V1127.5生成树和最小生成树第69页/共119页V2V0V3V5V4V13652165546012345012345

下标sets010313012345

下标setsV2V0V3V5V4V11237.5生成树和最小生成树第70页/共119页V2V0V3V5V4V13652165546012345012345

下标sets010310012345

下标setsV2V0V3V5V4V112347.5生成树和最小生成树第71页/共119页V2V0V3V5V4V13652165546012345012345

下标sets010010012345

下标setsV2V0V3V5V4V112347.5生成树和最小生成树第72页/共119页V2V0V3V5V4V13652165546012345012345

下标sets011010012345

下标setsV2V0V3V5V4V1123457.5生成树和最小生成树第73页/共119页V2V0V3V5V4V13652165546012345012345

下标sets111010012345

下标setsV2V0V3V5V4V1123457.5生成树和最小生成树第74页/共119页V2V0V3V5V4V13652165546012345012345

下标sets111

110012345

下标setsV2V0V3V5V4V1123457.5生成树和最小生成树第75页/共119页V2V0V3V5V4V13652165546012345012345

下标sets111

111

012345

下标setsV2V0V3V5V4V1123457.5生成树和最小生成树第76页/共119页克鲁斯卡尔算法中，数据结构定义为：

structnode{intbegin,end;//边的相关顶点编号

intcost;};//边的权值

typedefstructnodeEDGE;EDGEedges[MAX];//存放边的数组，排好序的

intnum;//数组中实际存放的边数

intkruskal(EDGEedges[],intnum){intsets[N],t,i,j,k,u,v;for(i=0;i<N;i++)sets[i]=i;//初始化

k=0;t=0;7.5生成树和最小生成树第77页/共119页克鲁斯卡尔算法：

while((t<N)&&(k<num)){i=edges[k].begin;j=edges[k].end;k++;

//按顺序取出一条边

u=sets[i];v=sets[j];

//xi在集合u中,xj在集合v中

if(u!=v)

//xi,xj不在同一集合中

{printf(“%d,%d:%d\n”,u,v,edges[k].cost);t++;for(i=0;i<N;i++)

if(sets[i]==v)set[i]=u;

//xi在集合的v并入在集合的u中

}}

if(t==N-1)return(1);elsereturn(0);}7.5生成树和最小生成树第78页/共119页作业：1、写出图的深度优先遍历算法和广度优先遍历算法。写出下图的深度优先遍历序列和广度优先遍历序列。ABLMV1IEKHCFGDJ第79页/共119页2、分别用普里姆算法和克鲁斯卡尔算法画出下图中的网的最小生成树生成过程。V2V0V3V5V480页/共119页7.5

有向无环图及其应用在工程实践中，一个工程项目往往由若干个子项目组成，这些子项目间往往有多种关系：①先后关系，即必须在一子项目完成后，才能开始实施另一个子项目；②子项目之间无次序要求，即两个子项目可以同时进行，互不影响。在工厂中，一件设备的生产包括许多工序，各工序之间也存在这两种关系。学校里某个专业的课程学习，有些课程是基础课，它们可以独立于其它课程，即无前导课程；有些课程必须在一些课程学完后才能开始学。2023/1/1982第81页/共119页AOV网络这些类似的问题都可以用有向图来表示，我们把这些子项目、工序、课程看成一个个顶点称之为活动(Activity)。如果从顶点Vi到Vj之间存在有向边<Vi，Vj>,则表示活动i必须先于活动j进行。这种图称做顶点表示活动的网络(ActivityOnVertexnetwork,简称AOV网络)。例如某校计算机专业的课程及其相互之间的关系，它对应的AOV网络如下页图所示。2023/1/1983第82页/共119页

某专业课程设置2023/1/1984第83页/共119页

课程设置的AOV网络2023/1/1985第84页/共119页

有向无环图描述在AOV网络中，如果顶点Vi的活动必须在顶点Vj的活动以前进行，则称Vi为Vj的前趋顶点，而称Vj为Vi的后继顶点。这种前趋后继关系有传递性。AOV网络中一定不能有有向环路。例如在下页图那样的有向环路中，V2是V3的前趋顶点，V1是V2的前趋顶点，V3又是V1的前趋顶点，环路表示顶点之间的先后关系进入了死循环。因此，对给定的AOV网络首先要判定网络中是否存在环路，只有有向无环路网络在应用中才有实际意义。一个无环的有向图称为有向无环图，它是一类较有向树更一般的特殊有向树。2023/1/1986第85页/共119页

有向环路举例2023/1/1987第86页/共119页

拓扑排序所谓“拓扑排序”就是将AOV网络中的各个顶点(各个活动)排列成一个线性有序序列，使得所有要求的前趋、后继关系都能得到满足。由于AOV网络中有些顶点之间没有次序要求，它们在拓扑有序序列中的位置可以任意颠倒，所以拓扑排序的结果一般并不是唯一的。通过拓扑排序还可以判断出此AOV网络是否包含有有向环路，若有向图G所有顶点都在拓扑排序序列中，则AOV网络必定不包含有有向环路。2023/1/1988第87页/共119页

拓扑排序方法(1)在网络中选择一个没有前趋(入度为0)的顶点，并把它输出；(2)从网络中删去该顶点和从该顶点发出的所有有向边；(3)重复执行上述两步，直到网中所有的顶点都被输出(此时，原AOV网络中的所有顶点和边就都被删除掉了)。如果进行到某一步，无法找到无前趋的顶点，则说明此AOV网络中存在有向环路，遇到这种情况，拓扑排序就无法进行了。2023/1/1989第88页/共119页

拓扑排序过程AOV网络2023/1/1990输出V3后第89页/共119页输出V4后2023/1/1991输出V2后输出V1后输出V5后输出拓扑序列为：34215第90页/共119页

关键路径法关键路径法是采用边表示活动(ActivityOnEdge)的网络，简称为AOE网络。AOE网络是一个带权的有向无环路图，其中，每个顶点代表一个事件(Event)，事件说明某些活动或某一项活动的完成，即阶段性的结果。离开某顶点的各条边所代表的活动，只有在该顶点对应的事件出现后才能开始。权值表示活动持续的时间。2023/1/1992第91页/共119页

一个AOE网络2023/1/1993第92页/共119页AOE网络通常利用AOE网络可以研究以下两个问题：(1)完成整个工程至少需要多少时间？(2)哪些活动是影响工程进度的关键？2023/1/1994第93页/共119页

关键路径完成工程所需的时间就是从开始点起进行到结束点止所需的时间。路径长度是指沿路径各边的权值之和，也就是这些边所代表的活动所需时间之和。完成整个工程所需的时间取决于从开始点到结束点的最长路径长度，此长度最大的路径叫做关键路径。分析关键路径的目的是辨别哪些是关键活动，以便争取提高关键活动的效率，缩短整个工期。2023/1/1995第94页/共119页求关键路径的算法描述在描述关键路径的算法时，设活动ai由弧<j,k>表示，要确定如下几个相关的量：(1)事件Vj的最早出现时间和活动的最早开始时间：从源点V1到某顶点Vj的最长路径长度叫作事件j的最早出现时间，表示成ve[j]。顶点Vj的最早出现时间ve[j]决定了从Vj指出的各条边所代表活动的最早开始时间，因为事件j不出现，它后面的各项活动就不能开始。我们以e[i]表示活动ai的最早开始时间。显然e[i]=ve[j]。2023/1/1996第95页/共119页求关键路径的算法描述(续)(2)活动ai的最迟开始时间：在不影响整个工程按时完成的前提下，此项活动最迟的必须开始时间，表示成L[i]。只要某活动ai有L[i]=e[i]的关系，我们就称ai为关键活动。关键活动只允许在一个确定的时间开始，再早，它前面的事件还没出现，尚不能开始；再晚，又会延误整个工程的按时完成。由于完成整个工程所需的时间是由关键路径上各边权值之和所决定的，显然关键路径上各条边所对应的活动都是关键活动。2023/1/1997第96页/共119页求关键路径的算法描述(续)(3)事件j的最迟出现时间：即事件j在不延误整个工程的前提下允许发生的最迟时间，表示为vl[j]。对某条指向顶点Vk的边所代表的活动ai可得到：

L[i]=vl[k]-(活动ai所需时间)

也就是活动ai必须先于它后面事件的最迟出现时间开始，提前的时间为进行此活动所需的时间。下图所示为活动开始时间与事件出现时间的关系。2023/1/1998VjaiVk第97页/共119页求关键路径的算法描述(续)确定关键路径的方法就是要确定e[i]=L[i]的关键活动。假设以w[j,k]表示有向边<j,k>的权，即此边对应的活动所需的时间，为了求AOE网络中活动ai的最早开始时间e[i]和活动ai的最迟开始时间L[i]，先要求得顶点Vk的最早出现时间ve[k]和最迟出现时间vl[k]。2023/1/1999第98页/共119页ve[k]和vl[k]可以采用下