页数：103页文件大小：701.4 KB来源： 数据结构与算法ppt课件
本课件讲解图的定义与术语，给出数组表示法、邻接表、十字链表与邻接多重表等存储结构，展开深度优先与广度优先遍历，随后讲最小生成树的普里姆与克鲁斯卡尔算法，以及拓扑排序、关键路径与最短路径的求解。
第七章图
线性结构——线性关系
本章内容：1.图的定义和术语2.图的存储结构3.图的遍历4.图的连通性问题5.有向无环图及其应用6.最短路经.本章重点
第一节图的定义和术语
硕图(Graph):图G是由两个集合V(G)和E(G)组成的,记为G=(V,E),其中：V(G)是顶点的非空有限集E(G)是边的有限集合，边是顶点的无序对或有序对V2V1V3V4V2V1V4V5V3G1G2
有向图:有向图G是由两个集合V(G)和E(G)组成的图,其中：V(G)是顶点的非空有限集V3V4E(G)是有向边（也称弧）的有限集合，弧是顶点的有序对，记为<v,w>，v,w是顶点，v为弧尾，w为弧头V1V2G1
无向图:无向图G是由两个集合V(G)和E(G)组成的图,其中：V(G)是顶点的非空有限集E(G)是边的有限集合，边是顶点的无序对，记为(v,w)或(w,v)，并且(v,w)=(w,v)V2V1V4V5V3G2
例如1245163G1图G1中：V(G1)={1,2,3,4,5,6}E(G1)={<1,2>,<2,1>,<2,3>,<2,4>,<3,5>,<5,6>,<6,3>}例如21573246G2图G2中：V(G2)={1,2,3,4,5,6,7}E(G1)={(1,2),(1,3),(2,3),(2,4),(2,5),(5,6),(5,7)}
完全图:对于有n顶点的无向图，边E的取值范围是0~n(n-1)/2，当n个顶点的无向图有n(n-1)/2条边时称为完全图
子图:假设有两个图G=(V,{E})和G’=(V’,{E’})，如果V’V,E’E,则称G’为G的子图
顶点的度
路径:路径是从顶点V到V’所经过的顶点系列{V=Vi,0,Vi,1,……Vi,m=V’}，其中(Vi,j-1,Vij)E，(1<jn)
DEGHKCFIJLMCFJAABBLMDEIGHK
强连通图356245136非连通图连通分量连通图245136
生成树:一个连通图的生成树是一个极小连通子图，它包含有图中的全部顶点（n个），但只有足以构成一棵树的n-1条边
第二节图的存储结构
数组表示法
(1)数组表示法
TypedefstructVNode{VertexType点向量AdjMatrixvexs[MAX_VERTEX_NUM];//顶arcs;//邻接矩阵intvexnum,arcnum;GraphKindkind;
0，其它
特点：0，其它
61857030040024208160@@@@@@0@5@7@0@3例如网络的邻接矩阵4537152318642返回
图中每个顶点建立一个单链表，第i个单链表中的结点表示依附顶点Vi的边
Typedefstruct{VertexTypeArcNodedata;//顶点信息*firstarc;
G1bdacaecbdG21234acdb32^^^4^112344212abcde^^^5435^15323^邻接表举例
无向图的邻接表生成和显示应用程序
例G1dabc1234acdb^4^1^1^3返回
(3)十字连表
(3)十字连表(续)
例bdacabcd12341312314241^^^^^^34^^43入度，逆邻接表十字链表举例尾，头返回(3)十字连表(续)
(4)邻接多重表
//无向图的邻接多重表存储表示
TypedefstructVexBox{VertexTypedata;//顶点信息*firstedge;//第一条依附该顶点的边ArcBox
例aebdacd12b345e123432521^4^^5^3^邻接多重表返回e2e3e1e4e5ce6e1e2e4e3e5e6
第三节图的遍历
图的遍历：从图中某个顶点出发，访遍图中其余结点，且使每个顶点仅被访问一次
(1)深度优先搜索
//从第v个顶点出发递归地深度优先遍历图G
V1V2V3V4V5V6V7V8例12341342vexdatafirstarc2783^^^adjvexnext56785641^51282^6787365^^3^4深度遍历：V1V3V7V6V2V5V8V4深度优先搜索（无向图）
V1V2V3V4V5V6V7V8例1234vexdatafirstarc2783^^^adjvexnext567864^82^7^123456^7^8深度遍历：V1V3V7V6V2V4V8V5深度优先搜索（有向图）
V1V2V3V4V5V6V7V8深度遍历：V1V2V4V8V5V6V3V7深度优先搜索从上述3个实例可以看出：深度遍历结点顺序与邻接表存储的具体值有关
(2)广度优先搜索
while(!QueueEmpty(Q))DeQueue(Q,u);{//对头元素出队并置为ufor(w=firstAdjvex(G,u);w;w=NextAdjVex(G,u,w)if(!visited[w]){//w为u的尚未访问的邻接顶点Visited[w]=TRUE;Visit(w);EnQueue(Q,w);}//while}//if}//if
V1V2V3V4V5V6V7V8例例V1V3V2V5V6V4V8V7广度遍历：V1V2V3V4V5V6V7V8广度遍历：V1V2V3V4V5V6V7V8广度优先搜索
V1V2V3V4V5V6V7V8例广度遍历：V1V2V3V4V6V7V8V5广度优先搜索
例123451234vexdatafirstarc5543^^adjvexnext1234555^1^1143^22f1012345r遍历序列：14f012345r遍历序列：1443f012345r遍历序列：143广度优先搜索
例123451234vexdatafirstarc5543^^adjvexnext1234555^1^1143^22432f012345r遍历序列：143232f012345r遍历序列：1432325f012345r遍历序列：14325广度优先搜索
25f012345r遍历序列：143255f012345r遍历序列：14325f012345r遍历序列：14325例123451234vexdatafirstarc5543^^adjvexnext1234555^1^1143^22广度优先搜索
实例
图的遍历算法应用程序
第四节图的连通性问题
目的：利用遍历图的算法求解图的连通性问题
(1)无向图的连通分量和生成树
返回V1V2V3V4V5V6V7V8G4V1V2V3V4V5V6V7V8广度优先生成树V1V2V4V3V7V6V8V5深度优先生成树DECFJABLMIGHK深度优先生成森林DEGHKCFIJABLMG3
(2)最小生成树
1)普里姆算法
1654326513566425131163141643142116432142516543214253普里姆算法举例
普里姆算法
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}}//for}//for
普里姆算法构造最小生成树应用程序mx[1][2]=50;mx[1][3]=60;mx[2][4]=65;mx[2][5]=40;mx[3][4]=52;mx[3][7]=45;mx[4][5]=50;mx[5][6]=70;mx[4][6]=30;mx[4][7]=42;
2)克鲁斯卡尔(Kruskal)算法
第五节有向无环图及其应用
有向无环图(directedacyclinegraph,DAG):一个无环的有向图
例如：
(1)拓扑排序
AOV-网概念：用顶点表示活动、边表示两个活动间的次序关系的有向图称为顶点表示活动的网（ActivityOnVertexNetwork）
1)拓扑排序过程
举例先修棵课程名称课程代号无程序设计基础C1C1离散数学C2C1,C2数据结构C3C1汇编语言C4C3,C4语言的设计和分析C5C11计算机原理C6C3.C5编译原理C7C3,C6操作系统C8无高等数学C9C9线性代数C10C9普通物理C11C1,C9,C10数值分析C12C1C3C4C2C5C6C7C8C9C10C11C12
C1C2C3C4C5C6C7C8C9C10C12C11拓扑序列：C1--C2--C3--C4--C5--C7--C9--C10--C11--C6--C12--C8或：C9--C10--C11--C6--C1--C12--C4--C2--C3--C5--C7--C8一个AOV网的拓扑序列不是唯一的
C1C2C3C4C5C6C7C8C9C10C11C12
C2C3C4C5C6C7C8C9C10C11C12拓扑序列：C1（1）C3C4C5C6C7C8C9C10C12C11拓扑序列：C1--C2（2）
C4C5C6C7C8C9C10C11C12C5C6C7C8C9C10C11C12拓扑序列：C1--C2--C3（3）拓扑序列：C1--C2--C3--C4（4）
C6C8C10C11拓扑序列：C1--C2--C3--C4--C5--C7--C9C6C11拓扑序列：C1--C2--C3--C4--C5--C7--C9--C10（8）拓扑序列：C1--C2--C3--C4--C5（5）C12C6C7C8C9C10C11C12C6C8C9C10C12C11拓扑序列：C1--C2--C3--C4--C5--C7（6）C12C8
C6C8C12（9）C8C12（10）拓扑序列：C1--C2--C3--C4--C5--C7--C9拓扑序列：C1--C2--C3--C4--C5--C7--C9--C10--C11--C10--C11--C6C8拓扑序列：C1--C2--C3--C4--C5--C7--C9--C10--C11--C6--C12（11）拓扑序列：C1--C2--C3--C4--C5--C7--C9--C10--C11--C6--C12--C8（12）
2)拓扑排序算法
While(!StackEmpty(S)){ Pop(s,i); printf(i,G.vertices[i].data); ++count;p; p=p->nextarc){ k=p->adjvex;//若入度减为0，则入栈}//whileif(count<G.vexnum)returnERROR;} 第77页：关键路径与AOE网
(2)关键路径
- AOE-网：
- 以边表示活动的网，是一个带权的有向无环网；
- 顶点表示事件、边表示活动
- 网中只有一个入度为零的点和一个出度为零的点
- 研究问题：
- 完成整个工程至少需要多少时间？
- 哪些活动是影响工程进度的关键？
- 关键路径：
- 完成一个工程的最短时间是从开始点到完成点的最长路径的长度（活动持续时间的长度，并非路径上的弧段数）
- 路径长度最长的路径叫关键路径
第78页：事件的最早与最迟发生时间
开始点v1到vj的最长路径长度叫事件vj的最早发生时间Ve(j)
- 事件vj的允许最迟发生时间Vl(j)是在保证汇点vn在e(n)时刻发生的前提下事件允许发生的最晚时间，它等于Ve(n)减去vj到vn的最长路径长度
- 设活动ai(<vj,vk>)的最早开始时间为e(i)、最迟开始时间为l(i),l(i)-e(i)为活动ai的最大可利用时间，如果l(i)=e(i)，则表明ai是关键活动，必须在e(i)时间开始立即执行才不会影响工程进度
- 其中：e(i)=Ve(j)<事件vj的最早发生时间ve(j)>l(i) =Vl(k)-dut<j,k>Ve(j)Vl(k)v1aijkvn
第79页：关键路径举例
例如：
- v1到v9的的最长路径长度是18（v1,v2,v5,v8,v9）
- 事件v9的最早发生时间是18
- 活动a6的最早开始时间是5，最迟开始时间是8（18-a11-a9-a6）意味着活动a6推迟3天开始不会影响整个工程
- 求关键路径就是判断那些是关键活动，以便在关键活动上提高它的功效，从而缩短整个工期
- 关键活动就是e(i) =l(i)的活动987465321a2=4a3=5a5=1a6=2a9=4a1=6a4=1a7=9a8=7a10=2a11=4AOE-网
第80页：关键路径算法过程
1)关键路径算法过程
- 输入e条弧，建立AOE网
- 从源点v0出发，令ve[0]=0，按拓扑有序求其余各点的最早发生时间Ve[i]
- 从汇点vn出发,令vl[n-1]=ve[n-1]，按拓扑逆序求其余各点的最迟发生时间Vl[i]
- 根据各顶点的Ve和Vl值，求各（活动）弧的最早开始时间e和最迟开始时间l
- 若某条弧ak满足e(k) =l(k),则为关键活动
- 从图中删除非关键活动，有所有关键活动组成的从源点到汇点的路径为关键路径
第81页：关键路径求解步骤表
求关键路径步骤
- 求Ve(i)
- 求Vl(j)
- 求e(i)< =Ve(j) >
- 求l(i)<=Vl(k)-dut<j,k>>
- 计算l(i)-e(i)l-ele活动0
- 00a1220a2330a30
- 66>a4264a5385a60
- 77a70
- 77a83107a90
- 1616a100
- 1414a11VlVe顶点00V1Vl66V264V385V477V5107V61616V71414V818V918987645321a2=4a3=5a5=1a6=2a9=4a1=6a4=1a7=9a8=7a10=2a11=4(5)-dut<j,k
第82页：关键路径实例
朋根东华理工学院程2)实例
第83页：拓扑排序求Ve算法
3)关键路径算法
- StatusTopologicalOrder(ALGraphG,Stck&T){//有向网G采用邻接表（+逆邻接表）存储结构，求各顶点的最早发生时间ve（全局变量）//T为拓扑序列顶点栈，S为零入度顶点栈。//若G无回路，则用栈T返回G的一个拓扑序列，且函数值为Ok，否则为ERROR。FindinDegree(G,indregee);//对各顶点求入度indegree[0..vernum-1]InitStack(S);
第84页：拓扑排序求Ve算法续
东华理工学院程朋根While(!StackEmpty(S)){ Pop(S,j); push(T,j); ++count;p; p=p->nextoutarc){ k=p->adjvex;//若入度数为0，则入栈if(ve[j]+*(p->info)>ve[k])ve[k]=ve[j]+*(p->info);//for*(p->info)=dut(<j,k>)}//该有向网有回路if(count<G.vexnum)elsereturnOk; } 第85页：关键路径算法CriticalPath
StatusCriticalPath(ALGraphG){Vl[0…G.vexnum-1]=Ve[0..G.vexnum-1];>nextinarc){ k=p->adjvex; dut=*(p->info);p; p=p-if(vl[j]-dut <Vl[k])Vl[k]=Vl[j]-dut; } 第86页：关键活动输出
for(j=0; j<G.vexnum; ++j)//求ee,el和关键活动for(p=G.vertices[j]; p; p=p->nextoutarc){ k=p->adjvex; dut=*(p->info); ee=Ve[j]; el=Vl[k]-dut; tag=(ee==el)?‘*’:‘’; printf(j,k,dut,ee,el,tag);} 第87页：第六节最短路经
第六节最短路经
第88页：最短路径问题
最短路径问题
- 在交通图上求中转次数最少的路径（边数最少），采用广度优先搜索
- 交通费、时间、里程等
- 术语
- 源点(Sourse)：路径上的第一个顶点
- 终点(Destination)：路径上的第后一个顶点
- 从某个源点到其余各点的最短路径
- 每一对顶点之间的最短路径
第89页：单源最短路径
(1)从某个源点到其余各点的最短路径
- 举例北京到各大省城最短路径物流运输中某货源地到各需求点的最短路径
- 方法
- 迪杰斯特拉(Dijkstra)
第90页：迪杰斯特拉算法步骤
1)迪杰斯特拉(Dijkstra)算法步骤
- (1)求从v点到其余各点vi最短路径长度的初值
- D[i]=arcs[LocateVex(G,v)[i]]|viV
- S赋空，如P190表的第一列,
- (2)选择vj,使得D[j]=Min{D[i]|viV-S},vj为当前求得的一条从v出发的最短路径终点，S=SU{j}，如二行一列的10,(v0,v2)
- (3)修改从v出发到集合V-S上任意一点vk可达到的最短路径长度
- 如果D[j]+arcs[j][k]<D[k],则D[k]=D[j]+arcs[j][k]
- 例如三行一列的无穷大改为60
- (4)重复(2),(3)共n-1次，即可求得v到各点的最短路径
第91页：迪杰斯特拉求解过程表
从V0到各终点的D值和最短路径求解过程终点I=5I=4I=3I=2I=1∞无∞∞∞∞V110(V0,V2)V250(V0,V4,V3)60(V0,V2,V3)∞V330(V0,V4)30(V0,V4)V460(V0,V4,V3,V5)90(V0,V4,V5)100(V0,V5)100(V0,V5)V5V5V3V4V2Vj{V0,V2,V3,V4,V5}｛V0,V2,V4,V3｝｛V0,V2,V4｝｛V0,V2｝S2)实例
第92页：迪杰斯特拉算法实现
3)迪杰斯特拉(Dijkstra)算法
- voidShortestpath_DIJ(MgraphG,intv0,PathMatrix&p,shortPathTable&D){//用Dijkstra算法求有向网G的v0顶点到其余顶点v的最短路径p[v]及其带权长度D[v]//若p[v][w]为TRUE,则w是从v0到v当前求的最短路径上的顶点//final[v]为TRUE当且仅当v∈s，即已经求得从v0到v的最短路径for(v=0;v<G.vexnum;++v){final[v]=FALSE;D[v]=G.arcs[v0][v];for(w=0;w<G.vexnum;++w)p[v][w]=FALSE;//设空路径if(D[v]<INFINITY){p[v][v0]=TRUE;p[v][v]=TRUE;}}//forD[v0]=0;final[v0]=TRUE;//初始化，v0顶点属于S集
第93页：迪杰斯特拉算法续
2)迪杰斯特拉(Dijkstra)算法(续)//开始主循环，每次求得v0到某个v顶点的最短路径，并加v到s集for(i=1;i<G.vexnum;++i){min=INFINITY;//其余G.vexnum-1个顶点//当前所知离v0顶点的最近距离for(w=0;w<G.vexnum;++w)if(!final[w])//w顶点在v-s中if(D[w]<min){v=w;min=D[w];}//w顶点离v0顶点更近final[v]=TRUE;for(w=0;w<G.vexnum;++w)//离v0顶点最近的v加入s集//更新当前最短路径及距离if(!final[w]&&(min+G.arcs[v][w]<D[w])){//修改D[w]和p[w],w∈v-sD[w]=min+G.arcs[v][w];p[w]=p[v];}//if}//forp[w][w]=TRUE;// p[w] =p[v]+[w]，行相加
- }//shortestPath_DIJ，时间复杂度为O(n2)
第94页：Dijkstra算法应用程序
Dijkstra算法求最短路径应用程序cost[1][2]=50;cost[1][3]=10;cost[1][5]=45;cost[2][3]=15;cost[2][4]=50;cost[2][5]=10;cost[3][1]=20;cost[3][4]=15;cost[4][2]=20;cost[4][5]=35;cost[5][4]=30;cost[6][4]=3;
第95页：每对顶点之间的最短路径
(2)每一对顶点之间的最短路径
- 每次以一个顶点为源，重复执行迪杰斯特拉算法时间复杂度为O(n3)
- 弗洛伊德(Floyd)法求Vi到Vj的最短路径：
- 如果从Vi到Vj存在弧，则arcs[i][j]是从Vi到Vj的路径，但不是最短路径，需要进行n次测试
- 首先考虑（Vi,V0,Vj)是否存在，如果存在则在(Vi,Vj)和(Vi,V0,Vj)之间中取长度最短的路径为从Vi到Vj的中间顶点不大于0的路径
- 依次类推。
第96页：弗洛伊德算法的思路
ViVjVkk =0,1,2,…,k
- 若(Vi,…,Vk)和(Vk,…Vj)分别为是从Vi到Vk和从Vk到Vj的中间顶点号不大于k-1的最短路径，则将(Vi,…,Vk,…Vj)和已得到的从Vi到Vj且中间顶点序号不大于k-1的最短路径比较，长度最短者便是从Vi到Vj的中间顶点序号不大于k的最短路径
- 经过n次比较后，并可求得从Vi到Vj的最短路径点号k值为0,1,2,…,k-1
第97页：弗洛伊德算法实现
1）弗洛伊德(Floyd)算法
- //用Floyd算法求有向网G中各对顶点v和w之间的最短路径p[v][w]及其带权长度D[v][w]。若p[v][w][u]为TRUE，则u是从v到w当前求得最短路径上的顶点。
- VoidShortestpath_FLOYD(MGRaph,pathMatrix&p[],DistancMatrix&D){for(v=0;v<G.vexnum;++v)//各对结点之间初始已知路径及距离for(w=0;w<G.vexnum;++w){D[v][w]=G.arcs[v][w];for(u=0;u<G.vexnum;++u)p[v][w][u]=FALSE;if(D[v][w]<INFINITY){//从v到w有直接路径P[v][w][v]=TRUE;p[v][w][w]=TRUE;}//if}//for
第98页：弗洛伊德算法续
for(u=0;u<G.vexnum;++u)for(v=0;v<G.vexnum;++v)for(w=0;w<G.vexnum;++w)if(D[v][u]+D[u][w]<D[v][w])经u到w的一条路径更短D[v][w]=D[v][u]+D[u][w];for(i=0;i<G.vexnum;++i){//从vp[v][w][i]=p[v][u][i]‖p[u][w][i];}//if
- }//ShortestPath_FLOYD
第99页：弗洛伊德算法实例
AB236411C0411初始：60230ACABBC：BACA路径046加入V2：602370BABCABBC：BACABCA路径0411加入V1：602370AACABBC：BACABCA路径046加入V3：502370C路径：ABCABBCBCACABCA算法分析：T(n)=O(n³)2)实例
第100页：本章重点
本章重点
- 图的定义、术语和存储结构
- 图的遍历
- 最小生成树
- 关键路径
- 最短路经
第101页：习题（一）
习题：
- 1、在一个图中，所有顶点的度数之和等于所有边数的2倍；而在一个有向图中，所有顶点的入度数之和等于所有顶点的出度数之和的1倍。
- 2、具有4个顶点的无向完全图有6条边。
- 3、对于一个具有n个顶点的无向图，若采用邻接矩阵表示，则该矩阵的大小是n2。
- 4、对于对于一个具有n个顶点和e条边的无向图，若采用邻接表表示，则表头向量的大小为n，所有邻接表中的结点总数为2e；若采用邻接多重表表示，则表头向量的大小为n，所有邻接多重表中的结点总数为e。
第102页：习题（二）
5、采用邻接表存储图的深度优先遍历法算类似与二叉树的先序遍历，而广度优先遍历算法类似与二叉树的层序遍历。
- 6、已知一个有向图用邻接矩阵表示，则计算第i结点入度的方法是求矩阵第i列非0元素之和。
- 7、图的深度优先搜索序列和广度优先搜索序列是不惟一的。
- 8、对于稠密图和稀疏图，采用邻接矩阵和邻接表哪个更好？
第103页：习题（三）
9、注意阐述题类型：
- 根据一个图或图的邻接表表示存储结构，写出图的深度优先和广度优先搜索的顶点系列。（课堂作业）
- 根据图和和边的权值，描述采用谱里姆算法生成最小生成树的过程。（P174的图、表）
- 根据一个有向图，求原点到其它各点最短路径.（用表描述，见图7.34和P190表格）
下载地址：{{downurl}}
{{{a}}}
{{#b}}{{{b}}}
{{/b}} {{/title}} {{#nolog}}登陆注册
{{/nolog}} {{#djsx}}点我刷新
{{/djsx}} {{#gocz}} {{/gocz}} {{#ffqr}} {{/ffqr}}