数据结构基础（第五版） 课件 第06章 图

第6章图主要内容6.1图的定义和基本操作6.2图的存储表示6.3图的遍历6.4图的连通性6.5最短路径6.6有向无环图及其应用小结2重难点（1）图的存储结构邻接矩阵邻接表逆邻接表十字链表邻接多重表——无向图/无向网图的遍历算法深度优先遍历DFS广度优先遍历BFS3无向图/无向网有向图/有向网有向图/有向网重难点（2）求最小生成树Prim算法Kruskal算法求单源最短路径(Dijkstra算法)有向无环图的应用对AOV网进行拓扑排序求AOE网的关键路径46.1图的定义和基本操作图(Graph)是一种比树形结构更复杂的非线性结构。在图形结构中，每个结点都可以有多个直接前驱和多个直接后继。图G由两个集合V和E组成，记为G＝(V,E)。其中，V是顶点的非空有限集；E是边的有限集；边是V中顶点的有序或无序偶对。56.1图的定义和基本操作无向图：如果每条边都没有方向，则称该图为无向图。6边(Vi,Vj)或(Vj,Vi)顶点Vi与Vj互为邻接点G=(V,E)V={V1,V2,V3,V4}E={(V1,V2),(V1,V3),(V1,V4),(V2,V3),(V2,V4)}V1V3V4V2ViVj6.1图的定义和基本操作有向图：在一个图中，如果每条边都有方向，则称该图为有向图。7弧<Vi,Vj>弧尾(起始点)Vj邻接自Vi，Vj为Vi的邻接点Vi邻接到Vj，Vi为Vj的逆邻接点弧头(终端点)G=(V,E)V={V1,V2,V3,V4}E={<V1,V2>,<V2,V1>,<V1,V3>,<V4,V2>,<V1,V4>}V1V3V4V2ViVj6.1图的定义和基本操作设图中顶点数为n，边数为e，则8有向图：0≤e≤n(n-1)无向图：0≤e≤n(n-1)/2

V1V3V4V2注意：在图的定义中不包含重复边和端点是同一个顶点的边；V1VnViV2…………V1VnViV2…………6.1图的定义和基本操作完全图无向图中，如果任意两顶点都有一条直接边相连，则称该图为无向完全图。可以证明，在一个含有n个顶点的无向完全图中，有n(n-1)/2条边。有向完全图：e=n(n-1)无向完全图：e=n(n-1)/29V1V2V3V4V1V2V3V4e＝12e＝66.1图的定义和基本操作稠密图、稀疏图边数很多的图为稠密图；边数很少的图为稀疏图。顶点的度在无向图中，一个顶点拥有的边数，称为该顶点的度，记为TD(v)。顶点V的度TD(V)：关联于顶点V的边或弧的数目有向图顶点V的入度ID(V)：以顶点V为弧头的边数有向图顶点V的出度OD(V)：以顶点V为弧尾的边数106.1图的定义和基本操作一个顶点的度等于顶点的入度+出度，即：TD(v)=ID(v)＋OD(v)。11V1V3V2V4V5V1V3V2V4在图G1中有：TD(v1)=2TD(v2)=3TD(v3)=3TD(v4)=2TD(v5)=2在图G2中有：ID(v1)=1OD(v1)=2TD(v1)=3ID(v2)=1OD(v2)=0TD(v2)=1ID(v3)=1OD(v3)=1TD(v3)=2ID(v4)=1OD(v4)=1TD(v4)=2无向图G1有向图G26.1图的定义和基本操作

12

V1V3V2V4V5e=(2+3+3+2+2)/2=66.1图的定义和基本操作带权的图称之为网顶点带权的图，称为AOV网(ActivityOnVertex)，每个顶点带有相应的权值。边(或弧)带权的图，一般称为AOE网(ActivityOnEdge)，每条边(或弧)带有相应的权值。136V1V2V4V6V5V3310383141542有向带权图V1V3V4V2123875无向带权图6.1图的定义和基本操作

14V1V3V2V4V56.1图的定义和基本操作回路在一条路径中，如果起始点和终止点是同一顶点，则称其为回路或者环。简单路径如果一条路径上，所有顶点除起始点和终止点外彼此都不同，则称该路径为简单路径。简单回路除起始点和终止点外，其他顶点不重复出现的回路称为简单回路，或者简单环。156.1图的定义和基本操作子图：设有两个图G=(V,E)，G’=(V’,E’),若V’V且E’E，则称G’为G的子图。16V1V3V4V2GV1V2G’G’’V1V4V2G’’’V16.1图的定义和基本操作

17图(a)图(b)图(c)6.1图的定义和基本操作弱连通图如果有向图G去掉每条边的方向后，得到的无向图是连通的，则称G是弱连通图。单向连通图如果G中任意两个顶点之间至少一个可达另一个，则称G是单向连通图。18V1V3V4V2G6.1图的定义和基本操作强连通如果Vi到Vj有路径，Vj到Vi也有路径，称Vi到Vj是强连通的。强连通图有向图G中任意两个顶点之间都是强连通的。强连通分量有向图G的极大强连通子图，称为G的一个强连通分量。19V1V3V4V2G6.1图的定义和基本操作有向图G的连通性：强连通图一定是单向连通图；单向连通图一定是弱连通图。20V1V4V2V3强连通图V1V4V2V3单向连通图V1V4V2V3弱连通图v1、v4无法到达6.1图的定义和基本操作21非强连通图G3G3的两个强连通分量V1V3V4V2V1V3V4V2V3V1V4V26.1图的定义和基本操作图论中对树的定义：无回路的连通图22（n个顶点，n-1条边）6.1图的定义和基本操作无向连通图的生成树设G(V，E)是具有n个顶点的无向连通图，G的生成树是G的一个极小连通子图，它包含了G的n个顶点及构成树的n-1条边。23V1V7V4V3V5V6V2V1V7V4V3V5V6V2V1V7V4V3V5V6V26.1图的定义和基本操作无向连通图的生成树连通图G的一个子图，如果是一棵包含G的所有顶点的树，则该子图称为G的生成树。所谓极小是指边数最少。由于n个顶点的连通图至少有n-1条边，而所有包含n-1边及n个顶点的连通图都是无回路的树，所以生成树是无回路的树。若在生成树中去掉任何一条边，都会使之变为非连通图。若在生成树上任意添加一条边，就必定出现回路。246.1图的定义和基本操作creatGraph(G)输入图G的顶点和边，建立图G的存储。

dfsTraverse(G,v)在图G中，从顶点v出发深度优先遍历图G。bfsTraverse(G,v)在图G中，从顶点v出发广度优先遍历图G。256.2图的存储表示图的存储图中的顶点和边，在内存中的表示形式；图的存储结构比较多，对于图的存储结构的选择，取决于具体的应用和需要进行的运算。图的常用存储结构邻接矩阵邻接表逆邻接表十字链表邻接多重表——无向图/无向网26无向图/无向网有向图/有向网有向图/有向网6.2图的存储表示——邻接矩阵

27

6.2图的存储表示——邻接矩阵图的邻接矩阵存储用一维数组vexs[N]，存放图的顶点数据用矩阵edges[N][N]，存放图中边的信息，n为顶点数，e为边数描述如下：28#defineN20//假设最大顶点数为20typedefcharVertexType;typedef

struct{

VertexType

vexs[N];

int

edges[N][N];

int

n,e;}AdjMatrix;6.2图的存储表示——邻接矩阵无向图的邻接矩阵存放顶点的一维数组G.vexs=存放边的矩阵(二维数组)G.edges=

290123456V1V2V3V4V5V6V7012345600111000110001112100000131000000401000105010010060110000V1V2V3V4V5V6V7V1V7V4V3V5V6V26.2图的存储表示——邻接矩阵无向图邻接矩阵的特点：对称矩阵顶点Vi的度等于第i行非零元个数，或第i列非零元个数：矩阵的非零元总数，等于边数的2倍30

6.2图的存储表示——邻接矩阵有向图的邻接矩阵存放顶点的一维数组G.vexs=存放弧的矩阵(二维数组)G.edges=

3101234567V1V2V3V4V5V6V7V801234567001110000100101100200000100300100110400000001500001010600000001700000000V4为弧尾V4为弧头V1V7V4V3V5V6V2V86.2图的存储表示——邻接矩阵

32

6.2图的存储表示——邻接矩阵有向网的邻接矩阵示例：3368314592ADCBG.edges=G.vexs=6.2图的存储表示——邻接矩阵有向网的邻接矩阵示例：34ABCD012301230∞1∞41∞∞92235∞83∞∞6∞G.edges=G.vexs=68314592ADCB6.2图的存储表示——邻接表邻接表邻接表(AdjacencyList)是一种将顺序存储与链式存储相结合的存储方法邻接表表示法类似于树的孩子链表表示法，是图最重要的存储方法之一。在邻接表表示中有如下两种结点结构如果边有权值，则边结点的结构变为35图的边结点图的顶点结点网的边结点6.2图的存储表示——邻接表邻接表的结构体类型定义如下：36#defineN10//假设最大顶点数为10typedef

struct_EdgeNode{

intadjVex;

//邻接顶点的下标

struct_EdgeNode*next;//指向下一个邻接边结点的指针}EdgeNode;

//定义边结点类型typedef

struct{

VertexTypevertex;

//顶点标志或信息

EdgeNode*firstEdge;//保存第一个边结点的地址}VertexNode;

//定义顶点结点类型typedef

struct{

VertexNodenodes[N];//顶点数组

int

n,e;

//顶点数和边数}AdjList;

//定义邻接表类型AdjList6.2图的存储表示——邻接表邻接表的结构体类型定义如下：37#defineN10//假设最大顶点数为10typedef

struct_EdgeNode{

intadjVex;

//邻接顶点的下标

struct_EdgeNode*next;//指向下一个邻接边结点的指针}EdgeNode;

//定义边结点类型typedef

struct{

VertexTypevertex;

//顶点标志或信息

EdgeNode*firstEdge;//保存第一个边结点的地址}VertexNode,

AdjList[N];//定义顶点结点类型typedef

struct{

AdjListnodes;//顶点数组

int

n,e;

//顶点数和边数}AdjList;

//定义邻接表类型AdjList6.2图的存储表示——邻接表C语言复习——数组类型的别名若有如下定义:typedefintIntArray[10];则:IntArrayb,c;完全等价于intb[10],c[10];38data0V11V22V33V44V55V66V789n7e86.2图的存储表示——邻接表

39V1V7V4V3V5V6V2nodes1∧321∧5∧4∧601∧0645∧0∧21firstEdgeadjVexnextEdge边结点的结构体6.2图的存储表示——邻接表有向图的邻接表40V1V7V4V3V5V6V2V8data0V11V22V33V44V55V66V77V8∧8n8e14adjvexnextArc1∧32∧7∧6∧54firstArc54∧2∧726∧5nodes弧结点的结构体6.2图的存储表示——邻接表

41data0V1∧1V22V33V44V55V66V77V88n8e146.2图的存储表示——邻接表有向图的逆邻接表42nodes1∧32∧0∧5∧01firstArc01∧3∧53∧74V1V7V4V3V5V6V2V8adjVexnextArc边结点的结构体6.2图的存储表示——邻接表

436.2图的存储表示——邻接表有向网的邻接表44ADCB68314592data0A1B2C3D4n4e8nodesfirstArc1143∧9223∧305183∧62∧adjVexnextArcweight邻接顶点的下标边的权值下个弧结点的地址6.2图的存储表示——十字链表

45tailVexheadVexhLinktLinkweight十字链表的弧结点结构6.2图的存储表示——十字链表

46datafirstInfirstOut十字链表的顶点结点结构#defineN10typedef

struct_ArcNode{

inttailVex,headVex;

//弧尾和弧头顶点的下标

struct_ArcNode*tLink;//指向同弧尾的下一个弧结点

struct_ArcNode*hLink;//指向同弧头的下一个弧结点

intweight;

//弧的权值信息}ArcNode;

//定义弧结点的类型typedef

struct{

VertexTypevertex;//顶点标志或信息

ArcNode*firstIn;

//指向第一个弧头结点

ArcNode*firstOut;//指向第一个弧尾结点}VexNode;

//定义顶点结点的类型typedef

struct{

VexNodenodes[N];

//顶点数组

int

vexNum,arcNum;//顶点数和弧数}OrthoList;

//定义十字链表的类型6.2图的存储表示——十字链表476.2图的存储表示——十字链表48弧头顶点的下标弧尾顶点的下标弧尾顶点的下一个弧结点地址6.2图的存储表示——邻接多重表无向图邻接表结构的缺点每条边都存在两个顶点，并且这两个顶点分别位于两个链表中，这给无向图的某些操作带来了不便。例如，当插入或删除一条边时，必须找到表示同一条边的两个边结点，并分别对其操作，比较繁琐。邻接多重表(AdjacentMultiList)的每条边都用一个边结点表示，其边结点和顶点结点的结构分别如图所示。49邻接多重表的边结点结构邻接多重表的顶点结点结构6.2图的存储表示——邻接多重表50#defineN10typedef

struct_EdgeNode{

intiVex,jVex;

//边两端顶点的下标

struct_EdgeNode*iLink;//优先指向同iVex端点的下一个边结点

struct_EdgeNode*jLink;//优先指向同jVex端点的下一个边结点

doubleweight;

//边的权值信息}EdgeNode;

//定义边结点的类型typedef

struct{

VertexTypevertex;

//顶点标志

EdgeNode*firstEdge;//指向第一个邻接边结点的指针}VexNode;

//定义顶点结点的类型typedef

struct{

VexNodenodes[N];

//顶点数组

intvexNum,edgeNum;//顶点数和边数}AdjMultiList;

//定义邻接多重表的类型邻接多重表的边结点结构邻接多重表的顶点结点结构6.2图的存储表示——邻接多重表516.3图的遍历图的遍历从某一顶点出发，对图中的所有顶点都访问一次，而且只访问一次。图的(顶点)遍历方法深度优先搜索DFS广度优先搜索BFS526.3图的遍历图的遍历比较复杂，主要表现在四个方面：（1）图中每个结点的地位都是相同的，没有一个“自然”的起始结点，图中任意一个顶点都可作为访问的起始结点。（2）非连通图中，从一个顶点出发，只能访问它所在的连通分量上的所有顶点，因此需要考虑如何访问图中其余的连通分量。（3）如果有回路存在，一个顶点被访问后，可能沿回路又访问到该顶点，但是顶点不能重复访问。（4）图中一个顶点可以和其它多个顶点相连，当这个顶点访问过后，要考虑如何选取下一个要访问的顶点。536.3.1深度优先搜索(DFS)深度优先遍历/搜索(Depth-FirstSearch,简称为DFS)，类似于树的先根遍历，是树的先根遍历的推广。DFS的遍历过程：从图G中选某个顶点V作为出发点；访问V；依次从V的尚未被访问的邻接点出发，调用递归函数深度优先遍历图G，直至与V相通的顶点都被访问完；如果此时图G中还有顶点未曾被访问，则从这些未被访问的顶点中，再选一个顶点V，转2，继续遍历；否则遍历结束。546.3.1深度优先搜索(DFS)55出发点DFS访问序列：V1V2V5V6V7V3V4V1V7V4V3V5V6V26.3.1深度优先搜索(DFS)56出发点DFS访问序列：V3V2V4V9V1V6V5V1V2V4V3V6V5V8V7V9V8V76.3.1深度优先搜索(DFS)DFS遍历算法由于图中可能存在回路，所以在遍历时，可能会遇到已经被访问过的顶点。为了避免同一个顶点被多次访问，需要专门设置一个数组intvisited[N]，用于标记已经访问过的顶点。visited[]数组的下标与顶点数组平行57visited[i]=

6.3.1深度优先搜索(DFS)基于邻接表存储结构，进行一次深度优先遍历(遍历一个连通分量)58voiddfs(AdjListg,intv,intvisited[]){

ArcNode*p;

intw;

visited[v]=1;

printf("%2c",g.nodes[v].data);//访问v

p=g.nodes[v].firstArc;

//p先指向v后链表中的第一个结点

while(p!=NULL)

{

w=p->adjVex;

//用w保存邻接顶点的下标

if(0==visited[w])

//如果w号顶点尚未访问

dfs(g,w,visited); //则以w为起始，递归

p=p->next;

}}6.3.1深度优先搜索(DFS)基于邻接表存储结构，深度优先搜索遍历整个图g59调用dfs一次，只能访问到与v有路径相通的所有顶点。voiddfsTraverse(AdjListg){

intvisited[V_MAX]={0};//顶点的访问标志全部设为0

intv;

for(v=0;v<g.vexNum;v++)

{

//若顶点v尚未访问，则以v为起始，调用递归函数dfs()

if(0==visited[v])

dfs(g,v,visited);

}}6.3.1深度优先搜索(DFS)60出发点DFS访问序列：V1V9V7V2V5V6V4datafirstArcV8V387V76V65V54V43V92V21V108∧311∧5054∧6∧41∧81∧60∧7∧0∧2V3V8V1V7V4V9V5V6V2V8V3nodes6.3.1深度优先搜索(DFS)61datafirstArc8∧V87V76V65V54V43V32V21V101∧32∧7∧524∧5∧64∧725∧6nodesDFS访问序列：V1V2V3V6V5V8V7V4出发点V1V7V4V3V5V6V2V86.3.1深度优先搜索(DFS)

626.3.2广度优先遍历BFS广度优先遍历BFS，类似于树的层次遍历。BFS的遍历过程：从图g的某个顶点v出发，访问v；依次访问v的未被访问的所有邻接点；再按照“先被访问顶点的邻接点先访问”的次序，依次访问这些邻接点的邻接点，直至图中所有已被访问顶点的邻接点都被访问到；如果图中还有顶点未曾被访问，则另选一个未被访问的顶点v作为出发点，重复上述过程，直至图中所有的顶点都被访问完。636.3.2广度优先遍历BFS64BFS访问序列：V3V2V1V6V4V5V9V8V7V1V2V4V3V6V5V8V7V96.3.2广度优先遍历BFS65BFS访问序列：V1V2V4V5V6V7V8出发点V3V1V7V4V3V5V6V2V8datafirstArc8∧V87V76V65V54V43V32V21V101∧32∧7∧524∧5∧64∧725∧6nodes6.3.1广度优先搜索(BFS)基于邻接表存储结构，进行广度优先遍历66voidbfsTraverse(AdjListg)//4--广度优先遍历{

SeqQueuequeue;

intvisited[V_MAX]={0};//顶点的访问标志全部设为0

ArcNode*p;

intv,u=-1,w;

initQueue(queue);//初始化队列为空

for(v=0;v<g.vexNum;v++)

{

//如果顶点v尚未访问，则先访问并标记，并将其进队

if(0==visited[v])

{

printf("%2c",g.nodes[v].data);//访问

visited[v]=1;

//标记

inQueue(queue,v);

//进队

while(!queueIsEmpty(queue))//如果队列不为空

{

//出队一个元素给u，然后访问和u邻接的所有顶点

outQueue(queue,u);

//p先指向u之后弧结点链表中的第一个弧结点

p=g.nodes[u].firstArc;

while(p!=NULL)

{

w=p->adjVex;//w为邻接顶点的下标

//若w尚未访问，则访问并标记，并将其进队

if(0==visited[w])

{

//先访问w，将其标记为已访问并进队

printf("%2c",g.nodes[w].data);

visited[w]=1;

inQueue(queue,w);

}

p=p->next;

}

}}

}

}

//

endif//

end

for

//

endbfsTraverse6.3.2广度优先遍历BFS广度优先遍历(BFS)的分析每个顶点至多进一次队列。遍历的过程，实质是通过边或弧找邻接点的过程。广度优先遍历(BFS)和深度优先遍历(DFS)两者的时间复杂度是相同的；两者不同之处仅仅在于对顶点访问的顺序不同。686.4图的连通性无向图的连通分量和生成树在对无向图进行遍历时，对于连通图，仅需从图中任一顶点出发，进行深度优先或广度优先搜索，便可访问到图中所有顶点。对非连通图，则需从多个顶点出发进行搜索，每次从一个新的起始点出发进行搜索，得到的顶点访问序列，恰为各个连通分量的顶点集。696.4图的连通性70AEBFCD两次调用DFS（分别从顶点A和顶点D出发），得到的顶点访问序列为：ABFE和D

C。这两个顶点集合分别加上所有依附于这些顶点的边，便构成了上述非连通图的两个连通分量。6.4图的连通性判定一个无向图是否为连通图，或有几个连通分量，可设一个计数变量count，初始时取值为0，在深度优先遍历算法中，每调用一次DFS，就给count增1。当整个算法结束时，依据count的值，就可确定图的连通性。设E(G)为连通图G中所有边的集合，则从图中任一顶点出发遍历图时，必定将E(G)分成两个集合T(G)和B(G)，其中T(G)是遍历图过程中历经的边的集合；B(G)是剩余的边的集合。显然，T(G)和图G中所有顶点一起构成连通图G的极小连通子图。716.4图的连通性——连通图的生成树由深度优先搜索得到的为深度优先生成树；由广度优先搜索得到的为广度优先生成树。72V1V5V2V4V8V3V6V7V1V5V2V4V8V3V6V7V1V5V2V4V8V3V6V7无向连通图广度优先生成树深度优先生成树6.4图的连通性——非连通图的生成森林对于非连通图，通过遍历，将得到生成森林。73非连通无向图深度优先生成树林JHKLMAICFGBDEHKIGJLMACFBDE6.4图的连通性——最小生成树最小生成树的基本概念由生成树的定义可知，无向连通图的生成树不一定是唯一的。连通图的一次遍历所经过的边及图中所有顶点，构成该图的一棵生成树。连通图的不同遍历，可能得到不同的生成树。74V1V5V2V4V8V3V6V7无向连通图V1V5V2V4V8V3V6V7生成树AV1V5V2V4V8V3V6V7生成树B6.4图的连通性——最小生成树可以证明：有n个顶点的无向连通图，无论其生成树的形态如何，所有生成树都有且仅有n-1条边。最小生成树如果无向连通图是一个边带权值的网，那么它的所有生成树中至少存在一棵边的权值之和最小的生成树，简称为最小生成树。756.4图的连通性——最小生成树最小生成树可以用于解决许多实际问题。例如：以尽可能低的总价建造城市间的通讯网络，把若干个城市连接在一起。在这些城市中，任意两个城市之间都可以建造通讯线路，通讯线路的造价依据城市之间的距离不同，而有不同的造价。可以构造一个通讯线路造价网，用每个顶点表示一个城市，顶点之间的边表示城市之间的通讯线路，边的权值表示该条通讯线路的造价，要使总的造价最低，实际上就是寻找该网的最小生成树。766.4图的连通性——最小生成树最小(代价)生成树n个顶点构成的无向网的所有生成树中，n-1条边的权值之和最小的生成树。构造最小生成树的著名算法Prim算法(普里姆算法)Kruskal算法(克鲁斯卡尔算法)776.4图的连通性——Prim算法求最小生成树普里姆(Prim)算法的基本思想：从连通的带权图G={V,E}中的某一顶点z出发，将顶点z加入到生成树的顶点集合U中。未加入到U集合的顶点，构成集合W=V－U。从集合U选取一个顶点u，从集合W中选取一个顶点w。从跨越两个集合的所有边(u,w)中，选择一条权值最小的边(x,y)，并把对应的顶点也加入到集合U中。如此继续下去，直到带权图中的所有顶点都加入到生成树的顶点集合U中为止。786.4图的连通性——Prim算法求最小生成树从顶点A出发构造最小生成树与顶点A

关联的候选边有两条，权值小的边是(A,F)10，选取它及顶点F

加入到最小生成树。与顶点A、F

关联的候选边有两条，权值小的是(F,E)25，选取它及顶点E

加入到最小生成树。79FAEGBDC281025142422161812FAEGBDC281025142422161812FAEGBDC2810251424221618126.4图的连通性——Prim算法求最小生成树继续从指定范围中选取权值最小的边及其顶点与顶点A、F、E关联的候选边有三条，权值小的是(E,D)22，选取它并将顶点D

加入最小生成树。与顶点A、F、E、D关联的候选边有四条，权值最小的是(D,C)12，选取它并将顶点C加入最小生成树。80FAEGBDC281025142422161812FAEGBDC281025142422161812FAEGBDC2810251424221618126.4图的连通性——Prim算法求最小生成树继续从指定范围中选取权值最小的边及其顶点与顶点A、F、E、D、C关联的候选边有四条，权值小的边为(B,C)16，选取它并将顶点B

加入生成树。与顶点A、F、E、D、C、B关联的候选边有四条，权值最小的是(B,G)14，选取它及顶点G加入最小生成树。81FAEGBDC281025142422161812FAEGBDC102514242216181228FAEGBDC2810251424221618126.4图的连通性——Prim算法求最小生成树从n个顶点的图中，选取到第n-1条边时停止所有顶点A、F、E、D、C、B、G均已加入最小生成树，算法完成，7个顶点的图共需选取6次（每次选择一条边的同时，选取那个对应的顶点）。每次为了在候选边中选取权值最小的边，算法可以使用一个小根堆，把当前的候选边放在堆内，每次从堆中取出的一定是权值最小的候选边，可以提高效率。82FAEGBDC102514221612FAEGBDC281025142422161812FAEGBDC1025142422161812286.4图的连通性——Prim算法求最小生成树按Prim算法，选取各条边的顺序：(A,F)10(F,E)25(E,D)22(D,C)12(C,B)16(B,G)1483FAEGBDC281025142422161812FAEGBDC1025142216126.4图的连通性——Prim算法求最小生成树846.4图的连通性——克鲁斯卡尔(Kruskal)算法求最小生成树Kruskal算法的基本思想设有一个有n

个顶点的连通带权图G={V,E}先将边集E中所有的边，按权值从小到大排序。然后从权值小的边开始，依次选取各条边；选取每条边后，都要先判断所选边是否会让顶点构成环。如果会构成环，则放弃该条边；退而求其次，选取下一条权值稍大的边。如此重复下去，直到选取的边数达到n-1条。856.4图的连通性——克鲁斯卡尔(Kruskal)算法求最小生成树8610FAEGBDC(a)1210FAEGBDC(b)16121410FAEGBDC(d)2216141210FAEGBDC(e)FAEGBDC101412(c)22FAEGBDC2810251424161812(原图)6.4图的连通性——克鲁斯卡尔(Kruskal)算法求最小生成树按Kruskal算法，选取各条边的顺序：(A,F)10(D,C)12(B,G)14(C,B)16(E,D)22(F,E)2587FAEGBDC281025142422161812原图FAEGBDC102514221612(f)最小生成树6.4图的连通性——克鲁斯卡尔(Kruskal)算法求最小生成树886.5最短路径最短路径问题是图的比较典型的应用例如，某一地区的一个交通网，给定了该网内的n个城市以及这些城市之间公路的距离，问题是如何在城市A和城市B之间找一条最近的通路。如果将城市用顶点表示，城市间的公路用边表示，公路的长度作为边的权值，那么，这个问题就可归结为在网中，求点A到点B的所有路径中，边的权值之和最短的那一条路径。这条路径就称为两点之间的最短路径，并称路径上的第一个顶点为源点(source)，最后一个顶点为终点(destination)。896.5最短路径以V1为源点的路径举例V1到V2的路径有1条：V1→V2(20)V1到V3的路径有2条：V1→V3(15)V1→V2→V3(55)V1到V4的路径有3条：V1→V2→V4(30)V1→V3→V4(45)V1→V2→V3→V4(85)V1到V5的路径有2条：V1→V2→V3→V5(65)V1→V3→V5(25)90V1V5V2V4V32010351015306.5最短路径——Dijkstra算法单源最短路径从带权有向图G(E,V)中，找出从给定源顶点s到所有其它顶点v的最短路径。最短路径==路径上所有边的权值之和最小单源，例如从上海到全国所有其它大中城市。Dijkstra算法的核心要点：最终求出的是：某顶点到其它所有顶点的n-1条最短路径；求解过程：按n-1条最短路径递增的次序。91

6.5最短路径——Dijkstra算法单源最短路径92目标顶点

i=1i=2i=3v1

v210(v0,v2)v3

60(v0,v2,v3)50(v0,v4,v3)v430(v0,v4)30(v0,v4)v5100(v0,v5)100(v0,v5)90(v0,v4,

v5)60(v0,v4,v3,

v5)S{v0,v2}{v0,v2,v4}{v0,v2,v4,v3}{v0,v2,v4,v3,v5}20v5v4v0100601010v1v35030v26.5最短路径——Dijkstra算法单源最短路径Dijkstra算法：设置数组dist，其中每个分量dist[i]表示当前所求得的从源点到其余各顶点i的最短路径的长度。一般情况下dist[k]=<源点到顶点i的弧的权值>或者dist[k]=<源点到其它顶点的路径长度>+<其它顶点到顶点i的弧上的权值>936.5最短路径——Dijkstra算法单源最短路径在所有从源点出发的弧中，选取一条权值最小的弧，即为第一条最短路径。dist中的最小值，即为最短路径的长度。修改其它各顶点的dist[i]值。假设求得最短路径的顶点为u，若dist[u]+g.arcs[u][i]<dist[i]则将dist[i]改为dist[u]+g.arcs[u][i]94

6.6有向无环图及其应用一个不存在环的有向图，称为有向无环图(DirectedAcyclineGraph)，简称为DAG图。几乎所有工程，都可分为若干个称为活动的子工程，这些子工程之间，通常受着一定条件的约束。比如其中某些子工程的开始，必须在另一些子工程完成之后。956.6有向无环图及其应用对于整个工程，人们往往最关心两个方面：一是工程能否顺利进行；二是估算完成整个工程所必须的最短时间。其中前一个就是有向图能否拓扑排序的问题，后一个则和关键路径有关。96补充：离散数学中的关系及其性质什么是“关系”(Relation)假设有一个集合X(通俗地说就是一类东西)，某些元素之间(例如x、y之间)有某一种关系R，则记为R(x,y)。这个关系可以是“x和y认识”，或者“x比y大”，或者“x包含y”，或者是任意你说了算的关系，你说有关系就有关系。97补充：离散数学中的关系及其性质自反性对于集合X的任意元素x、必有R(x,x)。因为一般语境下的“关系”是两个对象，所以这个概念不太直观。举例，比如X=班级，x=小明，R=同班；那么小明一定和自己同班，所以R(x,x)。98补充：离散数学中的关系及其性质反自反性就是任意元素x，不满足R(x,x)。如果关系R是“我是你爸爸”，那么显然任意的x都不是自己的爸爸；因此关系“我是你爸爸”满足反自反的性质。99补充：离散数学中的关系及其性质对称性如果R(x,y)，则R(y,x)。还是“同班”的例子，“我是你同学”意味着“你是我同学”；结婚，我和你结婚，你必然和我结婚等。这里“意味着”就是推导。100补充：离散数学中的关系及其性质反对称性如果R(x,y)，则R(y,x)不成立。例如“我是你爸爸”就满足反对称，因为“我是你爸爸”，肯定不意味着“你是我爸爸”。101补充：离散数学中的关系及其性质传递性如果R(x,y)和R(y,z)，则R(x,z)。比如“同班”这个(特定班级，不是“同过班”)关系，就具备传递性。再比如“直系血亲”就是传递的，比如爸爸的爸爸是爷爷。102补充：离散数学中的关系及其性质不传递性（注意，不是反传递）很多关系都不满足传递性，例如“朋友”，“我是你爸爸”，“接过吻”等都不满足传递性。如果一个关系满足“反身，对称，传递”，那么这个关系就叫“等价关系”，也就是“分类关系”。也可以反过来理解，所有“分类关系”必然满足“反身，对称，传递”。1036.6.1拓扑排序在离散数学课程中关于偏序关系和全序关系有如下定义：若集合S上的关系R是自反的、反对称的和可传递的，则称R是集合S上的偏序关系。设关系R是集合S上的偏序(PartialOrder)，如果对每个R，必有xRy或yRx，则称R是集合S上的全序关系。偏序指集合中仅有部分成员之间存在关系，全序指集合中的全部成员之间均存在关系。比如集合之间的包含关系，就是一个偏序关系；因为并不是任何两个集合之间都存在包含关系。1046.6.1拓扑排序拓扑排序是有向图的一个重要操作。拓扑序列、拓扑排序：在有向图G中，若从顶点A到顶点B有一条路径，则在某线性序列中顶点A必定在顶点B之前，则称这个线性序列为一个拓扑序列。求一个有向图拓扑序列的过程，称为拓扑排序(TopologicalSort)实质上，拓扑排序是由某个集合上的偏序关系得到该集合上的一个全序关系的过程。1056.6.1拓扑排序偏序和全序关系举例106B和C之间不可比较A、B、C、D之间均可比较(a)偏序关系(b)全序关系6.6.1拓扑排序——AOV网偏序关系的有向图，可用来表示任务的流程。可能是施工的流程，或者是生产产品的流程。图中每条有向边表示两个子工程完成的先后次序。这种用顶点表示活动，用弧表示活动之间优先关系的有向图，称为顶点为活动的网(ActivityOnVertex)，简称AOV网。1076.6.1拓扑排序——AOV网在AOV网中，不应该出现有向环如果存在环，则意味着某项活动以自己为先决条件；如果这样，只能说明该活动无法完的，整个工程也是无法完成的。因此，对AOV网应首先判定是否存在环，如果不存在环，则可以进行拓扑排序，得到相应的拓扑序列，反之，则不能得到拓扑序列。1086.6.1拓扑排序——拓扑排序的应用109课程代号课程名称先修课程C1高等数学C2程序设计基础C3离散数学C1,C2C4数据结构C3,C2C5高级语言程序设计C2C6编译方法C5,C4C7操作系统C4,C9C8普通物理C1C9计算机原理C86.6.1拓扑排序——拓扑排序的应用对课程进行拓扑排序，得到如下拓扑序列C1,C2,C3,C4,C5,C6,C8,C9,C7C1,C8,C9,C2,C5,C3,C4,C7,C6课程关系图110C8C3C5C4C9C6C7C1C26.6.1拓扑排序拓扑排序示例11