数据结构-第7章图-课件

数据结构课程的内容多对多（m:n)2020/12/21哥尼斯堡七桥问题

德国古城—哥尼斯堡—普雷格尔河—七桥问题：从任一桥头出发，依次走过每座桥，每座桥只走一次，最后回到出发点。

——一笔画问题2020/12/22精品资料你怎么称呼老师？如果老师最后没有总结一节课的重点的难点，你是否会认为老师的教学方法需要改进？你所经历的课堂，是讲座式还是讨论式？教师的教鞭“不怕太阳晒，也不怕那风雨狂，只怕先生骂我笨，没有学问无颜见爹娘……”“太阳当空照，花儿对我笑，小鸟说早早早……”2020/12/252020/12/267.1

基本术语7.2

存储结构7.3图的遍历7.4图的连通性7.5图的应用第7章图2020/12/277.1图的基本术语其中：V

是G的顶点集合，是有穷非空集；

E

是G的边集合，是有穷集。问：当E(G)为空时，图G存在否？答：还存在！但此时图G只有顶点而没有边。有向图：无向图：完全图：图G中的每条边都是有方向的；图G中的每条边都是无方向的；图G任意两个顶点都有一条边相连接；若

n个顶点的无向图有

n(n-1)/2条边,

称为无向完全图若

n个顶点的有向图有n(n-1)条边,称为有向完全图V=vertexE=edge图：记为G＝(

V,E

)v1v2v3v5v4v4v1v2v3v4有向边(u,v)称为弧，边的始点u叫弧尾，终点v叫弧头。2020/12/28例：判断下列4种图形各属什么类型？无向无向图(树)有向图有向n(n-1)/2条边n(n-1)条边G1的顶点集合为V(G1)={0,1,2,3}边集合为E(G1)={(0,1),(0,2),(0,3),(1,2),(1,3),(2,3)}完全图完全图2020/12/29证明：证明：若是完全有向图，则n个顶点中的每个顶点都有一条弧指向其它n-1个顶点,因此总边数=n(n-1)证明：从①可以直接推论出无向完全图的边数——因为无方向，两弧合并为一边，所以边数减半，总边数为n(n-1)/2。②完全无向图有n(n-1)/2条边。①完全有向图有n(n-1)条边。123412342020/12/210稀疏图：

稠密图：设有两个图G＝(V,E)和G’＝(V’,E’)。若V’

V且E’

E,则称图G’是图G的子图。子图：边较少的图。通常边数远少于nlogn边很多的图。无向图中，边数接近n(n-1)/2

有向图中，边数接近n(n-1)2020/12/211带权图：即边上带权的图。其中权是指每条边可以标上具有某种含义的数值（即与边相关的数）。连通图：在无向图中,若从顶点v1到顶点v2有路径,则称顶点v1与v2是连通的。如果图中任意一对顶点都是连通的,则称此图是连通图。非连通图的极大连通子图叫做连通分量。→带权图在有向图中,

若对于每一对顶点vi和vj,都存在一条从vi到vj和从vj到vi的路径,则称此图是强连通图。强连通图：网：DEABCFJLMGHIK非强连通图的极大强连通子图叫做强连通分量。2020/12/212生成树：是一个极小连通子图，它含有图中全部n个顶点，但只有n-1条边。若干棵生成树的集合，含全部顶点，但构成这些树的边或弧是最少的。有两类图形不在本章讨论之列：图的基本术语(续)v1v2v3v4如果在生成树上添加1条边，必定构成一个环。若图中有n个顶点，却少于n-1条边，必为非连通图。生成森林：2020/12/213邻接点：有向边(u,v)称为弧，边的始点u叫弧尾，终点v叫弧头。顶点v的入度是以v为终点的有向边的条数,记作ID(v);顶点v的出度是以v为始点的有向边的条数,记作OD(v)。若(u,v)是E(G)中的一条边，则称u与v互为邻接顶点。弧头和弧尾：入度和出度：问：当有向图中仅1个顶点的入度为0,其余顶点的入度均为1，此时是何形状？uv度：顶点v的度是与它相关联的边的条数。记作TD(v)。在有向图中,顶点的度等于该顶点的入度与出度之和。U的入度=?U的出度=?答：是树！而且是一棵有向树！2020/12/214简单路径：路径上各顶点v1,v2,...,vm均不互相重复。回路：若路径上第一个顶点v1与最后一个顶点vm重合，则称这样的路径为回路或环。路径：在图G＝(V,E)中,若从顶点

vi出发,沿一些边经过一些顶点

vp1,vp2,…,vpm，到达顶点vj。则称顶点序列

(vi

vp1

vp2...vpm

vj)

为从顶点vi到顶点

vj

的路径。它经过的边(vi,vp1)、(vp1,vp2)、...、(vpm,vj)应当是属于E的边。路径长度：非带权图的路径长度是指此路径上边的条数；带权图的路径长度是指路径上各边的权之和。图的术语（续）2020/12/215ADTGraph{数据对象V：数据关系R：基本操作P：}ADTGraph图的抽象数据类型V是具有相同特性的数据元素的集合，称为顶点集。R={VR}；VR={<v,w>|v,w∈V且P(v,w),

<v,w>表示从v到w的弧，

谓词P(v,w)定义了弧<v,w>的意义或信息}CreatGraph

(&G,V,VR);

初始条件：V是图的顶点集，VR是图中弧的集合。操作结果：按V和VR的定义构造图G。注意：V的大小写含义不同！InsertVex

(&G,v);

初始条件：图G存在，v和图中顶点有相同特征。

操作结果：在图G中添加新顶点。…………（参见教材P156-257）2020/12/2167.2图的存储结构图的特点：链式存储结构：顺序存储结构：难！（多个顶点，无序可言，无法仅以顶点坐标表达相互关系）可用多重链表邻接矩阵(数组)表示法邻接表(链式)表示法十字链表表示法邻接多重表表示法但可用数组描述元素间关系。非线性结构（m:n）邻接矩阵邻接表十字链表邻接多重表各种表示法成立的原则：存入电脑后能惟一复原2020/12/217①建立一个顶点表和一个邻接矩阵。1.邻接矩阵（数组）表示法例1：邻接矩阵：A.Edge=（

v1v2

v3v4v5

）v1v2v3v4v501

0

1010

1

010

1

01110101011

10分析1：无向图的邻接矩阵是对称的；分析2：顶点i

的度＝第i

行(列)中1

的个数；特别：完全图的邻接矩阵中，对角元素为0，其余全1。顶点表：无向图的邻接矩阵如何表示？v1v2v3v5v4v4A记录各个顶点信息表示各个顶点之间关系②设图A=(V,E)有n

个顶点，则图的邻接矩阵是一个二维数组A.Edge[n][n]，定义为：00

0

0000

0000

0000000000000001

0

1010

1

010

1

0111

01010111

02020/12/218例2：有向图的邻接矩阵如何表示？分析1：有向图的邻接矩阵可能是不对称的。分析2：顶点vi的出度=第i行元素之和，OD(vi)=

A.Edge[i][j]

顶点vi的入度=第i列元素之和。ID(vi)=

A.Edge[j][i]

顶点的度=第i行元素之和+第i列元素之和,即：TD(vi

)=OD(vi)+ID(vi)v1v2v3v4A邻接矩阵：A.Edge=(

v1v2

v3v4)v1v2v3v400

0

000

000

0000000注：在有向图的邻接矩阵中，第i行含义：以结点vi为尾的弧(即出度边）；第i列含义：以结点vi为头的弧(即入度边）。顶点表：01

1

000

000

0

01

1

00001

1

000

000

0

01

1

0002020/12/219容易实现图的操作，如：求某顶点的度、判断顶点之间是否有边（弧）、找顶点的邻接点等等。n个顶点需要n*n个单元存储边(弧);空间效率为O(n2)。例3：有权图（即网络）的邻接矩阵如何表示？定义：A.Edge[i][j]=Wij

<vi,vj>或（vi,vj）∈VR∞无边（弧）v1v2v3v4Nv5v65489755613以有向网为例：邻接矩阵：∞

∞

∞∞

∞

∞∞

∞

∞∞

∞

∞∞

∞

∞∞

∞

∞∞

∞

∞∞

∞

∞∞

∞

∞∞

∞

∞∞

∞

∞∞

∞

∞N.Edge=(

v1v2

v3v4v5v6

)邻接矩阵法优点：邻接矩阵法缺点：顶点表：

5

7

4

8

9

5

6

5

3

1

∞

5

∞

7

∞

∞∞

∞

4

∞

∞

∞

8

∞

∞

∞∞

9∞

∞

5∞

∞

6∞

∞

∞

5

∞

∞

3

∞

∞∞

1

∞v1v2v3v4v5v6对稀疏图而言尤其浪费空间。2020/12/220注：用两个数组分别存储顶点表和邻接矩阵#defineINFINITYINT_MAX

//最大值∞#defineMAX_VERTEX_NUM20

//假设的最大顶点数Typedefenum{DG,DN,AG,AN}GraphKind;

//有向/无向图，有向/无向网图的邻接矩阵在机内如何表示？

（参见教材P161）对于n个顶点的图或网，空间效率=O(n2)Typedefstruct

ArcCell{//弧（边）结点的定义VRTypeadj;//顶点间关系，无权图取1或0；有权图取权值类型InfoType*info;//该弧相关信息的指针}ArcCell,AdjMatrix[MAX_VERTEX_NUM][MAX_VERTEX_NUM];Typedefstruct{

//图的定义VertexTypevexs[MAX_VERTEX_NUM];//顶点表，用一维向量即可(n)AdjMatrixarcs;//邻接矩阵n*nIntVernum,arcnum;//顶点总数n，弧（边）总数eGraphKindkind;//图的种类标志}Mgraph;

2020/12/221StatusCreateUDN(Mgraph&G){

//无向网的构造，用邻接矩阵表示scanf(&G.vexnum,&G.arcnum,&IncInfo);//输入总顶点数n、总弧数e和信息for(i=0;i<G.vexnum,;++i)scanf(&G.vexs[i]);//输入n个顶点值，存入一维向量例：用邻接矩阵生成无向网的算法（参见教材P162）对于n个顶点e条弧的网，建网时间效率=O(n+n2+e*n)for(i=0;i<G.vexnum;++i)//对邻接矩阵n*n个单元初始化，adj=∞,info=NULLfor(j=0;j<G.vexnum;++j)G.arcs[i][j]={INFINITY,NULL};for(k=0;k<G.arcnum;++k){

//给邻接矩阵有关单元赋初值(循环次数＝弧数escanf(&v1,&v2,&w);//输入弧的两顶点以及对应权值i=LocateVex(G,v1);j=LocateVex(G,v2);//找到两顶点在矩阵中的位置(n次)G.arcs[i][j].adj=w;//输入对应权值If(IncInfo)Input(*G.arcs[i][j].info);//如果弧有信息则填入G.arcs[i][j]=G.arcs[j][i]；//无向网是对称矩阵

}

returnOK;}//

CreateUDN2020/12/2222.邻接表（链式）表示法①对每个顶点vi建立一个单链表，把与vi有关联的边的信息（即度或出度边）链接起来，表中每个结点都设为3个域:②每个单链表还应当附设一个头结点（设为2个域），存vi信息；adjvexnextarcinfodatafirstarc表结点头结点邻接点域，表示vi邻接点的位置链域，指向下一个边或弧的结点数据域，与边有关信息（如权值）数据域，存储顶点vi信息链域，指向单链表的第一个结点③每个单链表的头结点另外用顺序存储结构存储。2020/12/223例1：无向图的邻接表如何表示？v1v2v3v5v4v4邻接表01234^1334^142^0例2：有向图的邻接表如何表示？v1v2v3v4V4V3^V2V12^3^0^1邻接表(出边)V4V3V2V1^3^0^2^0逆邻接表(入边)请注意：邻接表不惟一！因各个边结点的链入顺序是任意的。v1v2v3v4v523^142^0v1邻接点v4的位置此无权图未开第3分量2020/12/224例3：已知某网的邻接（出边）表，请画出该网络。8064125当邻接表的存储结构形成后，图便唯一确定！2020/12/225分析1:

对于n个顶点e条边的无向图，邻接表中除了n个头结点外，只有2e个表结点,空间效率为O(n+2e)。若是稀疏图(e<<n2)，则比邻接矩阵表示法O(n2)省空间。邻接表存储法的特点：分析2:

在有向图中，邻接表中除了n个头结点外，只有e个表结点,空间效率为O(n+e)。若是稀疏图，则比邻接矩阵表示法合适。—它其实是对邻接矩阵法的一种改进怎样计算无向图顶点的度？邻接表的缺点：怎样计算有向图顶点的出度？怎样计算有向图顶点的入度？怎样计算有向图顶点Vi的度：需遍历全表邻接表的优点：TD(Vi)=单链表中链接的结点个数OD(Vi)＝单链出边表中链接的结点数ID(Vi)＝邻接点为Vi的弧个数TD(Vi)=OD(Vi)+ID(Vi)空间效率高；容易寻找顶点的邻接点；判断两顶点间是否有边或弧，需搜索两结点对应的单链表，没有邻接矩阵方便。2020/12/226讨论：邻接表与邻接矩阵有什么异同之处？1.联系：邻接表中每个链表对应于邻接矩阵中的一行，链表中结点个数等于一行中非零元素的个数。2.区别：①对于任一确定的无向图，邻接矩阵是唯一的（行列号与顶点编号一致），但邻接表不唯一（链接次序与顶点编号无关）。②邻接矩阵的空间复杂度为O(n2),而邻接表的空间复杂度为O(n+e)。3.用途：邻接矩阵多用于稠密图的存储（e接近n(n-1)/2)；而邻接表多用于稀疏图的存储（e<<n2)2020/12/227图的邻接表在机内如何表示？

（参见教材P163）#defineMAX_VERTEX_NUM20//假设的最大顶点数空间效率为O(n+2e)或O(n+e)时间效率为O(n+e*n)TypedefstructVNode{//顶点结构VertexTypedata;//顶点信息ArcNode*firstarc;//指向依附该顶点的第一条弧的指针}VNode,AdjList[MAX_VERTEX_NUM];Typedefstruct{//图结构AdjListvertics;//应包含邻接表intvexnum,arcnum;//应包含顶点总数和弧总数intkind;//还应说明图的种类（用标志）}ALGraph;

TypedefstructArcNode{//弧结构intadjvex;//该弧所指向的顶点位置structArcNode*nextarcs;//指向下一条弧的指针InfoArc*info;//该弧相关信息的指针}ArcNode；图的邻接表生成算法作为自测题2020/12/228

它是有向图的另一种链式结构。

思路：将邻接矩阵用链表存储，是邻接表、逆邻接表的结合。1、开设弧结点，设5个域（每段弧是一个数据元素）2、开设顶点结点，设3个域（每个顶点也是一个数据元素）tailvexheadvexhlinktlinkinfodata:顶点信息Firstin:以顶点为弧头的第一条弧结点Firstout:以顶点为弧尾的第一条弧结点dataFirstinFirstout顶点结点弧结点3.十字链表表示法tailvex:弧尾顶点位置headvex:弧头顶点位置hlink:弧头相同的下一弧位置tlink:弧尾相同的下一弧位置info:弧信息n个顶点的集合怎样储存？仍用顺序存储结构2020/12/229v1v2v3v4202^^33^03^^1例：画出有向图的十字链表。十字链表优点：容易操作，如求顶点的入度、出度等。FirstoutFirstindata顶点结点infotlinkhlinkheadvextailvex弧结点0v11v22v33v40123010^^2此无权图未开第4分量空间复杂度和建表的时间复杂度都与邻接表相同。2020/12/230#defineMAX_VERTEX_NUM20十字链表存储结构描述：TypedefstructArcBox{//弧结点结构，5分量inttailvex,headvex;structArcBox*hlink,tlink;InfoType*info;}ArcBox;TypedefstructVexNode{//顶点结构,3分量VertexTypedata;ArcBox*firstin,*firstout;}VexNode;Typedefstruct{//图结构,整体概念VexNodexlist[MAX_VERTEX_NUM];//表头向量intvexnum,arcnum;}OLGraph;2020/12/231这是无向图的另一种存储结构，当对边操作时建议采用此种结构存储。1、设立边结点，6个域（每条边是一个数据元素）2、设立顶点结点，2个域（每个顶点也是一个数据元素）markivexilinkjvexjlinkinfo边结点data:存储顶点信息Firstedge:依附顶点的第一条边结点dataFirstedge顶点结点4.邻接多重表表示法mark：标志域ivex，jvex:边依附的两个顶点位置ilink:指向下一条依附顶点i的边位置jlink;指向下一条依附顶点j的边位置info:边信息n个顶点的集合怎样储存？仍用顺序存储结构2020/12/232121^4232^43^4^v1v2v3v5v4v4例：画出无向图的邻接多重表邻接多重表优点：容易操作，如求顶点的度等。0v11v22v33v44v501234Firstedgedata顶点结点markinfojlinkjvexilinkivex边结点空间复杂度和建表的时间复杂度都与邻接表相同。01^…03此无权图未开第6分量2020/12/233一、深度优先搜索二、广度优先搜索

7.3图的遍历遍历定义：从已给的连通图中某一顶点出发，沿着一些边，访遍图中所有的顶点，且使每个顶点仅被访问一次，就叫做图的遍历，它是图的基本运算。遍历实质：找每个顶点的邻接点的过程。图的特点：图中可能存在回路，且图的任一顶点都可能与其它顶点相通，在访问完某个顶点之后可能会沿着某些边又回到了曾经访问过的顶点。解决思路：可设置一个辅助数组visited[n]，用来标记每个被访问过的顶点。它的初始状态为0，在图的遍历过程中，一旦某一个顶点i

被访问，就立即改visited[i]为1，防止它被多次访问。图常用的遍历：怎样避免重复访问？2020/12/234一、深度优先搜索(

DFS

)基本思想：——仿树的先序遍历过程。Depth_FirstSearchv1v1v2v3v8v7v6v4v5DFS结果例1：→→→→→→→v2v4v8v5v3v6v7例2：v2→v1→v3→v5→DFS结果v4→v6起点起点遍历步骤应退回到V8，因为V2已有标记2020/12/235深度优先搜索（遍历）步骤：详细归纳：在访问图中某一起始顶点

v

后，由

v出发，访问它的任一邻接顶点

w1；再从

w1出发，访问与

w1邻接但还未被访问过的顶点

w2；然后再从

w2出发，进行类似的访问，…如此进行下去，直至到达所有的邻接顶点都被访问过的顶点

u为止。接着，退回一步，退到前一次刚访问过的顶点，看是否还有其它未被访问的邻接顶点。

如果有，则访问此顶点，之后再从此顶点出发，进行与前述类似的访问；

如果没有，就再退回一步进行搜索。重复上述过程，直到连通图中所有顶点都被访问过为止。简单归纳：访问起始点v;

若v的第1个邻接点没访问过，深度遍历此邻接点；若当前邻接点已访问过，再找v的第2个邻接点重新遍历。2020/12/236讨论1：计算机如何实现DFS？123456100000020000003000000400000050000006000000000000123456010000110000111000111010111110111111DFS结果邻接矩阵A辅助数组visited[n]起点——开辅助数组visited[n]！例：123456101110021000103100010410000150110006000100v2→→→→→v1v3v5v4v6请注意逐级回退是递归概念2020/12/237for(j=1;j<=n;j++)if(A[v,j]&&!visited[j])DFS1(A,n,j);return;}//DFS1讨论2：

DFS算法如何编程？DFS1(A,n,v){visit（v）;visited[v]=1;——可以用递归算法！//A[n][n]为邻接矩阵，v为起始顶点(编号）//访问（例如打印）顶点vA[v,j]＝1有邻接点visited[n]=0未访问过//访问后立即修改辅助数组标志//从v所在行从头搜索邻接点（教材上DFS递归算法见P169）2020/12/238讨论3：在图的邻接表中如何进行DFS？DFS结果00000123辅助数组visited[n]1000110011101111例：—照样借用visited[n]！起点0123注意：在邻接表中，并非每个链表元素（表结点）都被扫描到,因此遍历速度很快。v0→→→v1v2v32020/12/239讨论4：

邻接表的DFS算法如何编程？（书上没有，仅供参考）//访问后立即修改辅助数组标志——仍用递归算法Intvisited[];//初始化辅助数组,元素均为0

VoidDFS(List,v,p)//设p为v的头指针{visit(v);//访问起点

visited[v]=1;//起点已访问,0变1

while(p->link)//当存在起点的第一个邻接点时

{p=p->link;

v=p->data;

if(!visited[v])DFS(List,v,p);//进行递归

}

return;

}2020/12/240DFS算法效率分析:（设图中有n个顶点，e条边）如果用邻接矩阵来表示图，遍历图中每一个顶点都要从头扫描该顶点所在行，因此遍历全部顶点所需的时间为O(n2)。如果用邻接表来表示图，虽然有2e

个表结点，但只需扫描e个结点即可完成遍历，加上访问n个头结点的时间，因此遍历图的时间复杂度为O(n+e)。结论：稠密图适于在邻接矩阵上进行深度遍历；稀疏图适于在邻接表上进行深度遍历。2020/12/241二、广度优先搜索(

BFS

)基本思想：——仿树的层次遍历过程。Breadth_FirstSearchv1v1v2v3v8v7v6v4v5BFS结果例1：→→→→v2v3→v4v5→v6v7→v8例2：v3→BFS结果v4

→v5→起点遍历步骤起点v2→v1→v6→v9→v8→v72020/12/242广度优先搜索（遍历）步骤：简单归纳：在访问了起始点v之后，依次访问v的邻接点；然后再依次（顺序）访问这些点（下一层）中未被访问过的邻接点；直到所有顶点都被访问过为止。广度优先搜索是一种分层的搜索过程，每向前走一步可能访问一批顶点，不像深度优先搜索那样有回退的情况。因此，广度优先搜索不是一个递归的过程，其算法也不是递归的。2020/12/243讨论1：计算机如何实现BFS？邻接表宽度优先搜索要借助队列！例：起点辅助队列v2已访问过了V2入队visited[n]仍需要BFS遍历结果2020/12/244while(rear!=front){

//队不空时

front=(front+1)%n;v=q[front];//访问过的顶点出队p=List[v].firstarc;//P指向第1个邻接点while(!p){if(!Visited[adjvex(p)])//未到表尾，且邻接域未访问过，{Visit(adjvex(p));Visited[adjvex(p)]=1;//则先输出再改标记，

rear=(rear+1)%n;q[rear]=adjvex(p)}//最后再入队p=nextarc(p);}

//指向单链表中下一个邻接点

}return}//BFS1讨论2：

BFS算法如何编程？BFS1(List,n,v){//List为邻接表，v为起点，Q[n]为辅助队列

Visit(v);Visited[v]=1;//访问（例如打印）顶点v并修改标志——层次遍历应当用队列！（教材上BFS算法见P170）front=n-1;rear=0;//队列指针初始化q[rear]=v;//起始点入队2020/12/245BFS算法效率分析:DFS与BFS之比较：空间复杂度相同，都是O(n)(借用堆栈或队列装n个顶点）；时间复杂度只与存储结构（邻接矩阵或邻接表）有关，而与搜索路径无关。如果使用邻接表来表示图，则BFS循环的总时间代价为d0+d1+…+dn-1=O(e)，其中的di是顶点i的度。如果使用邻接矩阵，则BFS对于每一个被访问到的顶点，都要循环检测矩阵中的整整一行（n个元素），总的时间代价为O(n2)。（设图中有n个顶点，e条边）2020/12/2467.4图的连通性问题1.求图的生成树2.求最小生成树2020/12/2471.求图的生成树（或生成森林）生成树：是一个极小连通子图，它含有图中全部顶点，但只有n-1条边。生成森林：由若干棵生成树组成，含全部顶点，但构成这些树的边是最少的。思考1：若对连通图进行遍历，得到的是什么？

——得到的将是一个极小连通子图，即图的生成树！由深度优先搜索得到的生成树，称为深度优先搜索生成树。由广度优先搜索得到的生成树，称为广度优先搜索生成树。思考2：若对非连通图进行遍历，得到的是什么？

——得到的将是各连通分量的生成树，即图的生成森林！2020/12/248例1：画出下图的生成树DFS生成树v0v1v2v4v4v3邻接表01234^1334^142^0v4v3v2v1v023^142^0v0v2v1v4v3BFS生成树v0v1v3v2v4无向连通图2020/12/249其实由邻接矩阵或邻接表也能直接画出生成森林DEABCFJLMGHIK例2：画出下图的生成森林（或极小连通子图）求解步骤：Step1:先求出邻接矩阵或邻接表；Step2:写出DFS或BFS结果序列；Step3:画出对应子图或生成森林。这是一个无向非连通图（参见教材P170-171例）下面选用邻接表方式来求深度优先搜索生成森林生成森林的定义（对有向或无向图均适用）：是若干棵生成树的集合，含全部顶点，但构成这些树的边或弧是最少的。2020/12/2501155M12L11K10J9I8H7G6F5E4D3C2B1A012^^0^120^0^4^378^106^6^1011^126^709^1219^111^1229^47^10811DEGHIK子图1：再写出DFS结果ABMJLCFDEGHKIABCFJLM先写出邻接表（或邻接矩阵）：子图2：子图3：最小连通！怎样找3个根？2020/12/251DEGHIK子图(或连通分量)ABCFJLMABCFJLMDEGHIK生成森林2020/12/2522.求最小生成树首先明确：使用不同的遍历图的方法，可以得到不同的生成树；从不同的顶点出发，也可能得到不同的生成树。按照生成树的定义，n个顶点的连通网络的生成树肯定有n个顶点和仅仅n-1条边。即有权图构造最小生成树的准则必须只使用该网络中的边来构造最小生成树；必须使用且仅使用n-1条边来联结网络中的n个顶点；不能使用产生回路的边。目标：在网络的多个生成树中，寻找一个各边权值之和最小的生成树。2020/12/253欲在n个城市间建立通信网，则n个城市应铺n-1条线路；但因为每条线路都会有对应的经济成本，而n个城市可能有n(n-1)/2条线路，那么，如何选择n–1条线路使总费用最少？典型用途：先建立数学模型：顶点———表示城市，有n个；边————表示线路，有n–1条；边的权值—表示线路的经济代价；连通网——表示n个城市间的通信网。显然此连通网是一棵生成树！问题抽象：

n个顶点的生成树很多，需要从中选一棵代价最小的生成树，即该树各边的代价之和最小。此树便称为最小生成树MST。MinimumcostSpanningTree2020/12/254讨论：如何求得最小生成树？最小生成树（MST）的性质如下：若U集是V的一个非空子集，若(u0,v0)是一条最小权值的边，其中u0U，v0V-U；则：(u0,v0)必在最小生成树上。设想一下：先把权值最小的边归入生成树内，逐个递增，舍去回路边，则得到的很可能就是最小生成树！求MST有多种算法，但最常用的是以下两种：Kruskal（克鲁斯卡尔）算法Prim（普里姆）算法Kruskal算法特点：将边归并，适于求稀疏网的最小生成树。Prime算法特点:

将顶点归并，与边数无关，适于稠密网。2020/12/255Kruskal算法示例：对边操作，归并边146523156554636215432135246Kruskal算法效率分析：Kruskal算法的时间效率＝O（elog2e）Kruskal算法是归并边，适用于稀疏图（用邻接表）56普利姆（Prim）算法示例：归并顶点1465231565546362364251Prim算法效率分析：Prim算法的时间效率＝O（n2）Prim算法是归并顶点，适用于稠密网。2020/12/257

图5-4-5构造最小生成树过程中辅助数组中各分量的值图5-4-5构造最小生成树过程中辅助数组中各分量的值2020/12/2587.5有向无环图及其应用1.拓扑排序2.求关键路径2020/12/2591拓扑排序在工程实践中，一个工程项目往往由若干个子项目组成，这些子项目间往往有多种关系：①先后关系，即必须在一子项目完成后，才能开始实施另一个子项目；②子项目之间无次序要求，即两个子项目可以同时进行，互不影响。在工厂中，一件设备的生产包括许多工序，各工序之间也存在这两种关系。学校里某个专业的课程学习，有些课程是基础课，它们可以独立于其它课程，即无前导课程；有些课程必须在一些课程学完后才能开始学。2020/12/260这些类似的问题都可以用有向图来表示，我们把这些子项目、工序、课程看成一个个顶点称之为活动(Activity)。如果从顶点Vi到Vj之间存在有向边<Vi，Vj>,则表示活动i必须先于活动j进行。这种图称做顶点表示活动的网络(ActivityOnVertexnetwork,简称AOV网络)。例如表5-6-1是某校计算机专业的课程及其相互之间的关系，它对应的AOV网络如图5-6-1所示。2020/12/261表5-6-1某专业课程设置2020/12/262图5-6-1（a）AOV网络2020/12/263在AOV网络中，如果顶点Vi的活动必须在顶点Vj的活动以前进行，则称Vi为Vj的前趋顶点，而称Vj为Vi的后继顶点。这种前趋后继关系有传递性。AOV网络中一定不能有有向环路。例如在图5-6-1（b）那样的有向环路中，V2是V3的前趋顶点，V1是V2的前趋顶点，V3又是V1的前趋顶点，环路表示顶点之间的先后关系进入了死循环。因此，对给定的AOV网络首先要判定网络中是否存在环路，只有有向无环路网络在应用中才有实际意义。2020/12/264图5-6-1（b）有向环路2020/12/265所谓“拓扑排序”就是将AOV网络中的各个顶点(各个活动)排列成一个线性有序序列，使得所有要求的前趋、后继关系都能得到满足。由于AOV网络中有些顶点之间没有次序要求，它们在拓扑有序序列中的位置可以任意颠倒，所以拓扑排序的结果一般并不是唯一的。通过拓扑排序还可以判断出此AOV网络是否包含有有向环路，若有向图G所有顶点都在拓扑排序序列中，则AOV网络必定不包含有有向环路。2020/12/266拓扑排序方法(1)在AOV网中选择一个没有前驱（即入度为0）的顶点，并把它输出；(2)从网络中删去该顶点和从该顶点发出的所有有向边；(3)重复执行上述两步，直到网中所有的顶点都被输出(此时，原AOV网络中的所有顶点和边就都被删除掉了)。如果进行到某一步，无法找到无前趋的顶点，则说明此AOV网络中存在有向环路，遇到这种情况，拓扑排序就无法进行了。2020/12/267C1C10C11C6C2C12C4C8C3C7C5C9拓扑有序序列：（C1，C2，C3，C4，C5，C7，C9，C10，C11，C6，C12，C8）（C9，C10，C11，C6，C1，C12，C4，C2，C3，C5，C7，C8）2020/12/26810c121c232c341c452c561c672c7^82c8^90c9101c10111c11123c12^c2c3^c5c5^c7^c8^c10c12^c6^c3c7c11c4c8^c12^c12^010102112020/12/269图5-6-2AOV网及拓扑序列的产生过程a

b

c

d

e

f（a）AOV网；(b)输出v0后；（c）输出v5后；（d）输出v3后；（e）输出v2后；（f）输出v1后。这样得到的一个拓扑排序序列为：v0,v5,v3,v2,v1,v42020/12/270为了实现拓扑排序，针对上述两个步骤，采用邻接表作为有向图的存储结构，并且在表结点中增设一个入度，存放顶点的入度。例如图5-6-2种的AOV网的邻接表如图5-6-3（a）所示。这样，入度域为零的表结点及时无前驱的顶点，删除该顶点及它为尾的弧的操作，则可以转换为将它的所有弧头顶点的入度减1来实现2020/12/271作业名称作业时间（h）紧前作业A（型砂准备）B（造型）C（砂型烘干）D（芯砂准备）E（芯骨浇铸）F（芯骨装配）G（造四个I号泥芯）H（造四个II号泥芯）I（II号泥芯干燥2444.77.226.244.3—

A

B——ED,FD,FH2020/12/272ABCDEFGHI2020/12/273两个事件之间只能画一条箭线，表示一项作业。若两项或两项以上作业同时开始或结束，就要引进虚事件和虚作业，虚作业不消耗资源。2020/12/274

3．各项作业之间的关系及它们在网络图上的表达方式如下：

作业a结束后可以开始b和c，见图(a)；

作业c在a和b均结束后才能开始，见图(b)；2020/12/275

a、b两项作业均结束后可以开始c和d，见图(c)；

作业c在a结束后即可进行，但作业d必须同时在a和b结束后才能开始，见图(d)。2020/12/276作业代号计划完成时间紧前作业作业代号计划完成时间紧前作业ABCDEF510114415——————BAC,DGHIJK2135251520B,EB,EB,EF,G,IF,G表7—12020/12/277CBEDAX2X1KGIH0FJ02020/12/2782.关键路径关键路径法是采用边表示活动(ActivityOnEdge)的网络，简称为AOE网络。AOE网络是一个带权的有向无环路图，其中，每个顶点代表一个事件(Event)，事件说明某些活动或某一项活动的完成，即阶段性的结果。离开某顶点的各条边所代表的活动，只有在该顶点对应的事件出现后才能开始。权值表示活动持续的时间。2020/12/279图5-6-4一个AOE网络2020/12/280AOE网络通常利用AOE网络可以研究以下两个问题：(1)完成整个工程至少需要多少时间？(2)哪些活动是影响工程进度的关键？2020/12/281关键路径完成工程所需的时间就是从开始点起进行到结束点止所需的时间。路径长度是指沿路径各边的权值之和，也就是这些边所代表的活动所需时间之和。完成整个工程所需的时间取决于从开始点到结束点的最长路径长度，此长度最大的路径叫做关键路径。分析关键路径的目的是辨别哪些是关键活动，以便争取提高关键活动的效率，缩短整个工期。2020/12/282在描述关键路径的算法时，设活动ai由弧<j,k>表示，要确定如下几个相关的量：(1)事件Vj的最早出现时间和活动的最早开始时间：从源点V1到某顶点Vj的最长路径长度叫作事件j的最早出现时间，表示成Ve[j]。顶点Vj的最早出现时间Ve[j]决定了从Vj指出的各条边所代表活动的最早开始时间，因为事件j不出现，它后面的各项活动就不能开始。我们以e[i]表示活动ai的最早开始时间。显然e[i]=Ve[j]。(2)活动ai的最迟开始时间：在不影响整个工程按时完成的前提下，此项活动最迟的必须开始时间，表示成L[i]。只要某活动ai有L[i]=e[i]的关系，我们就称ai为关键活动。关键活动只允许在一个确定的时间开始，再早，它前面的事件还没出现，尚不能开始；再晚，又会延误整个工程的按时完成。由于完成整个工程所需的时间是由关键路径上各边权值之和所决定的，显然关键路径上各条边所对应的活动都是关键活动。2020/12/283(3)事件j的最迟出现时间：即事件j在不延误整个工程的前提下允许发生的最迟时间，表示为VL[j]。对某条指向顶点Vj的边所代表的活动ai可得到：

L[i]=VL[j]-(活动ai所需时间)也就是活动ai必须先于它后面事件的最迟出现时间开始，提前的时间为进行此活动所需的时间。下图所示为活动开始时间与事件出现时间的关系。确定关键路径的方法就是要确定e[i]=L[i]的关键活动！2020/12/284假设以w[j,k]表示有向边<j,k>的权，即此边对应的活动所需的时间，为了求AOE网络中活动ai的最早开始时间e[i]和活动ai的最迟开始时间L[i]，先要求得顶点Vk的事件Vk的最早出现时间Ve[k]和最迟出现时间VL[k]。2020/12/285事件最早出现时间Ve（j）和最迟出现时间Vl（j）Ve[k]和VL[k]可以采用下面的递推公式计算：(1)向汇点递推由源点的Vv[1]=0开始，利用公式：向汇点的方向递推，可逐个求出各顶点的ev。式中p表示所有指向顶点的边的集合，如图6.22所示。2020/12/286图7-6-6集合p此式的意义为：从指向顶点Vk的各边的活动中取最晚完成的一个活动的完成时间作为Vk的最早出现时间Ve[k]。2020/12/287(2)向源点递推由上一步的递推，最后总可求出汇点的最早出现时间ev[n]。因汇点就是结束点，最迟出现时间与最早出现时间相同，即Lv[n]=ev[n]。从汇点的最迟出现时间Lv[n]开始，利用下面公式：

向源点的方向往回递推，可逐个求出各顶点的最迟出现时间Lv。式中s表示所有由Vj点指出的边的集合，如图6.23所示。

2020/12/288图5-6-7集合s此公式的意义为：由从Vj顶点指出的各边所代表的活动中取需最早开始的一个开始时间作为Vj的最迟出现时间。2020/12/289无论是向汇点递推还是向源点递推，都必须按一定的顶点顺序进行。对所有的有向边，向汇点递推是先求出尾顶点的ev值，再求头顶点的ev值；向源点递推则相反，先求头顶点的Lv值，再求尾顶点的Lv值。为此，可利用上节介绍的拓扑排序得到的顶点次序进行向汇点的递推，向源点的递推按相反的顺序进行即可，不必再重新排序。2020/12/2907.5.2关键路径算法(1)输入e条有向边<j,k>，建立AOE网络的存储结构；(2)从源点出发，令ev[1]=0，按拓扑排序的序列求其余各顶点的最早出现时间ev[i](2≤i≤n)。若拓扑排序序列中的顶点个数小于网络中的顶点数n，则说明网络中存在环路，算法中止执行；否则执行(3)；(3)从汇点Vn出发，令Lv[n]=ev[n]，按逆拓扑排序的序列求其余各顶点的最迟出现时间Lv[i](n-1≥i≥1)；(4)根据各顶点的ev和Lv值求每条有向边ai的最早开始时间e[i]和最迟开始时间L[i]。若某有向边ai满足e[i]=L[i],则为关键活动

2020/12/291AOE网：带权的有向图，其中，顶点表示事件，弧表示活动，权表示活动持续的时间。

关键路径：AOE-网中有些活动可以并行的进行，所以完成工程的最短时间是从开始点到完成点的最长路径的长度（这里所说的长度是指路径上各个活动持续时间之和，不是路径上弧的数目）。路径长度最长的路径叫做关键路径。最早发生时间：假设开始点是V1，从V1到Vi的最长的路径的长度叫做事件Vi的最早发生时间。最迟开始时间：不推迟整个工程完成的前提下，活动ai最迟必须开始进行的时间。关键活动：l（i）=e（i）的活动。回顾基本概念并练习：2020/12/292v1v3v8v9v7v2v6v4v5a3=5a6=2a9=4a11=4a10=2a8=7a4=1a1=6a2=4a5=1a7=9如何求关键路径？如图所示：关键：

求出各个事件最早出现时间ve（j）和最迟发生时间vl（j）。

再判断各活动e（i）是否等于l（i）！2020/12/2931求事件最早出现时间v1v3v8v9v7v2v6v4v5a3=5a6=2a9=4a11=4a10=2a8=7a4=1a1=6a2=4a5=1a7=9064571418716从ve（0）=0开始向后推.Ve（j）=Max{ve（i）+dut（〈i,j〉）}