数据结构-图（笔记）B-b--
一.图（上）
数据结构-图（笔记）B-b--一.图（上）(一).什么是图1.怎么在程序中表示图1.1邻接矩阵1.2邻接表2.源码(二).图的遍历1.遍历1.1DFS(DepthFirstSearch)1.2BFS(BreadthFirstSearch)2.其他2.1两种遍历的特点：2.2图不连通的处理方法3.源码二.图（中）(一).最短路径问题1.问题分类2.无权图的单源最短路算法3.有权图单源最短路算法4.实例详解5.多源最短路算法6.对应源码三.图（下）(一).MinimumSpanningTree1.简介2.贪心算法2.0Notes2.1Prim算法-让一颗小数长大2.2Prim算法实现(伪代码)2.3Krusial算法-将森林合并成树3.源码(二).拓扑排序1.例：计算机专业排课2.拓扑排序3.算法实现4.拓扑排序的应用（关键路径问题）：5.对应源码篇末数据类型及操作集源码1.图的表示法1.1图的邻接矩阵表示法1.2图的邻接表表示法2.图的遍历2.1邻接表存储的图进行DFS2.2邻接矩阵存储的图进行BFS3.最短路径问题3.1邻接表存储-无权图的单源最短路算法3.2邻接矩阵存储-有权图的单源最短路算法3.3邻接矩阵存储-多源最短路算法4.最小生成树4.1Prim4.2Kruskal5.拓扑排序5.1邻接表存储的拓扑排序算法
(一).什么是图
1.怎么在程序中表示图
1.1邻接矩阵
可以用一个矩阵（二维数组存储），G[j]表示顶点i-j的有向边
截屏-11-05下午1.14.42
截屏-11-05下午1.14.07
关于邻接矩阵的优势：-直观-方便检查一对顶点是否存在边-方便查找所有“邻接点”-方便计算“度”
劣势：-浪费空间-浪费时间
1.2邻接表
截屏-11-07下午3.33.03
邻接表的存储方式更适合稀疏图
优势：
-方便找顶点的邻接点-节约稀疏空间（需要N个头指针+2E个结点，没个结点至少两个域）-方便计算顶点的“度”吗？对无向图来说，是的，对有向图来说，只能计算“出度”；需要构造“逆邻接表”方便计算入度-不方便计算任意一对顶点存在边吗？
问：用邻接表表示有个顶点、条边的图，则遍历图中所有边的时间复杂度为：(C)A.O(N2)B.O(E)C.O(N+E)D.O(N)
2.源码
图的邻接矩阵表示法图的邻接表表示法
(二).图的遍历
1.遍历
1.1DFS(DepthFirstSearch)
在迷宫问题中，我们前往一个顶点，递归调用DFS，访问更深的结点
截屏-11-05下午2.00.59
Visited[v]数组是一个全局变量，用于标示v结点是否已经被访问。
例：已知一个图如下图所示，从顶点a出发按深度优先搜索法进行遍历，则可能得到的一种顶点序列为：
答案：a,e,d,f,c,b
1.2BFS(BreadthFirstSearch)
类似树的层序遍历：
访问当前顶点，将邻接点push进队列。所有邻接点push进队列后，pop队列中的一个结点，对其使用BFS方法。BFS是“一圈一圈”往外进行遍历的方法
2.其他
2.1两种遍历的特点：
DFS：优点：1、能找出所有解决方案2、优先搜索一棵子树，然后是另一棵，所以和BFS对比，有着内存需要相对较少的优点缺点：1、要多次遍历，搜索所有可能路径，标识做了之后还要取消2、在深度很大的情况下效率不高
BFS：优点：1、对于解决最短或最少问题特别有效，而且寻找深度小2、每个结点只访问一遍，结点总是以最短路径被访问，所以第二次路径确定不会比第一次短缺点：1、内存耗费量大（需要开大量的数组单元用来存储状态）
2.2图不连通的处理方法
Def:
连通：如果v到w存在一条（无向）路径，则称v和w是连通的。路径：v到w的路径是一系列顶点{V,V1,V2,Vn,W}的集合,其中任一对相邻的顶点间都有图中的边。路径的长度是路径中的边数(如果带权,则是所有边的权重和)。如果到w之间的所有顶点都不同,则称简单路径。回路：起点等于终点的路径连通图：图中任意两顶点均连通连通分量：无向图的极大连通子图。又有极大顶点数和极大边数。强连通：v和w间存在双向路径，称v和w是强连通的强连通图：有向图中任意两顶点均强连通强连通分量：有向图的极大强连通子图
截屏-11-05下午2.03.55
ListComponents：对当前图下的连通分量进行处理
3.源码
邻接表存储的图进行DFS邻接矩阵存储的图进行BFS
二.图（中）
(一).最短路径问题
Def:
最短路径问题的抽象：在网络中，求两个不同顶点之间的所有路径中，边的权值之和最小的那一条路径这条路径为ShortestPath第一个顶点为源点(Source)终点为(Destination)
1.问题分类
A.单源最短路径问题：从某固定源点出发，求其道所有顶点的最短路径。a.有向无权图b.无向无权图
B.多源最短路径问题求任意两个顶点间最短路径的问题
2.无权图的单源最短路算法
截屏-11-06下午1.01.24
分析：从起点v3出发，再从v3的邻接点一个个访问，顶点一个个被搜索，再往外扩展，可以想到BFS于是我们参考BFS算法。在求最短路的时候，我们并不需要访问结点。但我们要，我们定义dist[W]记录s到w的最短距离，dist[W]可被初始化为正无穷、负无穷或-1我们还要定义path[W]来记录最短路径
voidUnweighted(VertexS){Enqueue(S,Q);while(isEmpty(Q)){V=Dequeue(Q);for(V的每个邻接点){if(dist[W]==-1){dist[W]=dist[V]+1;//记录路径长度并标记已访问path[W]=V;//记录路径Enqueue(W,Q);}}}}
例如，该图进行此算法运算后的结果为：
3.有权图单源最短路算法
Dijkstra算法简介：
?令S={源点s+已经确定了最短路径的顶点v，}
?对任一未收录的顶点v，定义dist[v]为s到v的最短路径长度，但该路径仅经过s中的顶点。即路径{s→（v；ES）→v}的最小长度
?若路径是按照递增（非递减）的顺序生成的则
a.真正的最短路必须只经过s中的顶点（为什么？）b.每次从未收录的顶点中选一个dist最小的收录（贪心算法）c.增加一个v进入s，可能影响另外一个w的dist值！dist[w]=min{dist[w]，dist[v]+的权重}即dist[w]，dist[v]+的权重更小，收录到dist集合中。Dijkstra算法伪代码描述：
/*不能解决负边问题*dist[]初始化只能初始化为正无穷，发现更短路径才能更新他。否则是负数的话就无法更新，判断不成立*/voidDijkstra(Vertexs){while(1){V=未收录顶点中dist最小者；if(这样的V不存在)break;collected[V]=true;//记录收集的顶点for(V的每个顶点W){if(collected[W]=false)if(dist[V]+Edist[W]){/*E是的边*/dist[W]=dist[V]+E;//更新最短距离path[W]=V;}}}}
该算法时间复杂度取决于如何找到V，即未收录顶点中dist最小者
方法1:直接扫描所有未收录顶点-O(
V
)，此时T=O(
V
2+
E
)，该方法对稠密图效果较好
方法2:将dist存在最小堆中-O(log
V
)，更新dist[W]的值-O(log
V
)，所以T=O(
V
log
V
+
E
log
V
)=O(
E
log
V
)，该方法对于稀疏图更好
在稀疏图中，E和V为相同数量级，此时用方法2更快
4.实例详解
对于该图，我们以v1作为source，与v1相邻的两个顶点，v2,v4的dist分别被更新为2和1，path均为1.
1??dist[2]=2,dist[4]=1path[2]=path[4]=1
2??此时进入Dijkstra算法,v4位未收录点中dist最小值，收录v4，更新：
dist[3]=3,path[3]=4dist[5]=3,path[5]=4dist[6]=9,path[6]=9dist[7]=5,path[7]=4
3??在未收录的顶点中找dist最小者，为顶点2，标记v2。因为v4已经被收录，所以只剩v5。对v5来说，最短距离为3（即dist[5]），dist[2]+10大于3，不做处理，进入下一次循环。
4??寻找未收录的顶点，dist最小的为v3，v3未被访问的邻接点只有v6，dist[3]+E3,6=8，更新dist[6]和path[6]:
5??以此类推在做v5,发现不做处理：
6??v7:发现现在v6的路径为1-4-3-6,长度为8，但在v7处发现，dist[7]+E7,6=6，比dist[6]更小，所以更新为：dist[6]=6,path[6]=7,表示目前从v1到v6最短长度为6，路径为1-4-7-6
7??v6：v6没有邻接点，for循环直接结束了。所以最终结果为上图。若destination为v6，则最短路径为1-4-7-6,长度为6
5.多源最短路算法
方法1:直接将单源最短路算法调用
V
遍，T=O(
V
3+
E
x
V
)，对稀疏图效果更好
方法2:Floyd算法，T=O(
V
3)
Floyd算法简介
Notes:1.最短路径长度是由D0,D1,...,D
V
-1[j]一步步递推的2.初始D-1定义为邻接矩阵，对角元全是03.如果i,j之间没有边，要定义为正无穷，最小路径算法都是如此
voidFloyd(){for(i=0;in;i++)span=""/n;i++)for(j=0;jn;j++){span=""/n;j++){D[j]=G[j];path[j]=-1;}for(k=0;kn;k++)span=""/n;k++)for(i=0;in;i++)span=""/n;i++)for(j=0;jn;j++)span=""/n;j++)if(D[k]+D[k][j]d[j]){span=""/d[j]){D[j]=D[k]+D[k][j];path[j]=k;}}
6.对应源码
3.1邻接表存储-无权图的单源最短路算法3.2邻接矩阵存储-有权图的单源最短路算法3.3邻接矩阵存储-多源最短路算法
三.图（下）
(一).MinimumSpanningTree
1.简介
要求：1.是一颗树，无回路，V个顶点有V-1条边（向生成树里添加任意一条边都一定会构成回路）2.是生成树，包含全部顶点，V-1条边都在图里3.边的权重和最小4.最小生成树存在-图是连通的
2.贪心算法
2.0Notes
所谓贪心算法，就是每一步都要做到最好。在MinimumSpanningTree中，“好”就是指权重最小的边。问题中有这样的约束条件：1.只能用图里有的边；2.只能用V-1跳边；3.不能有回路
2.1Prim算法-让一颗小数长大
截屏-11-06下午4.14.57
在上图中，若以v1作为根结点，构造最小生成树：A.v1寻找权重最小的边，v4收入树B.v1-v2,收入v2,v3也被收入C.v2-v4会形成回路，不能收入D.v4-v7,v7-v6,v7-v5
不难发现，Prim算法与Dijkstra算法很相似
2.2Prim算法实现(伪代码)
voidPrim(){MST={s};//定义并初始化树while(1){V=未收录顶点中dist最小者；if(这样的V不存在)break;将V收录到MST：dist[V]=0;//因为收录后，成为结点，这个顶点到树的距离为0for(V的每个邻接点){if(dist[W]!=0)//W没有被收录if(Edist[w]){span=""/dist[w]){dist[W]=E;parent[W]=V;}}}if(MST中的顶点不到V个)Error("生成树不存在")；}
生成树的方法：定义并初始化parent[s]=-1
dist的初始化：dist[V]=E或正无穷，若不存在边，则要定义为正无穷
时间复杂度：T=O(2)
2.3Krusial算法-将森林合并成树
Krusial是每次找权重最小的边并收录，为什么叫把森林合并成树？因为，在初始状态下，我们认为每一个顶点都构成一个树，收录边并合并，所以叫把森林合并成树
截屏-11-06下午4.58.59
MST={};没有边被收录，创建空树并查集：把E上的两个顶点加到树中，V和W应该在两棵树上。若V和W本身已在同一棵树了，那么V和W必定形成回路从E中取一条权重最小的边E：可以采用最小堆的方法，T=O(logE)
3.源码
4.1Prim4.2Kruskal
(二).拓扑排序
1.例：计算机专业排课
有些课需要预选课程，有些不需要，我们该如何处理排课问题？
我们可以形成右边的图，其为一种AOV网络，这样的情况下排课不存在矛盾了
截屏-11-07下午4.01.49
我们将没有前驱结点的顶点输出，同时把他们在原来的图中抹掉，得到如下结果：
截屏-11-07下午4.04.57
2.拓扑排序
拓扑序:如果图中从V到W有一条有向路径，则V一定排在W之前。满足此条件的顶点序列称为一个拓扑序，获得一个拓扑序的过程就是拓扑排序
3.算法实现
截屏-11-07下午4.08.27
时间复杂度为T=O(V2)
通过改进划线处的改进，可以加快运算。将入度为0的顶点放入一个容器中，这样我们不用扫描所有的顶点集合，而是直接从容器中拿取
改进后：
截屏-11-07下午4.11.13
4.拓扑排序的应用（关键路径问题）：
Def：AOE(ActivityOnEdge)，一般用于安排项目的工序。将一个顶点分成三个部分，项目编号，最早完成时间，最晚完成时间
截屏-11-07下午4.17.25
案例：有如下项目工程
截屏-11-07下午4.30.32
A.如果我们要使v6,v7开工受v4,v5影响，也就是v6,v7开工需要等齐v1,v2,v3三条路线，我们要对图做什么改进？思考：是直接将v4和v5合并吗？显然不是，因为v5-v7是否开工，实际上与v1和v2毫无关系。解决方法：v5-v4处画虚线，边的权重为0，表示v6,v7要等齐之前的工作才能开工
B.整个工期有多长？
截屏-11-07下午4.37.03
C.哪几个组有机动时间？通过倒退计算Latest，特别注意v5的计算，再计算机动时间（边上的绿色数字）
截屏-11-07下午4.39.45
关键路径问题：回到关键路径问题，关键路径问题就是由绝对不允许延误的活动组成的路径。算法实现是通过对拓扑排序的算法改进完成的
例：下图给定了一个项目的AOE。
截屏-11-07下午4.56.33
A.整个项目最早完工需要的时间是？B.在上图中，如果0,2组能加快进度，整个项目可以提前完工吗？
答案：A.23;B.能
5.对应源码
5.1邻接表存储的拓扑排序算法
篇末数据类型及操作集源码
1.图的表示法
1.1图的邻接矩阵表示法
/*图的邻接矩阵表示法*/#defineMaxVertexNum/*最大顶点数设为*/#defineINFINITY/*∞设为双字节无符号整数的最大值*/typedefintVertex;/*用顶点下标表示顶点,为整型*/typedefintWeightType;/*边的权值设为整型*/typedefcharDataType;/*顶点存储的数据类型设为字符型*//*边的定义*/typedefstructENode*PtrToENode;structENode{VertexV1,V2;/*有向边*/WeightTypeWeight;/*权重*/};typedefPtrToENodeEdge;/*图结点的定义*/typedefstructGNode*PtrToGNode;structGNode{intNv;/*顶点数*/intNe;/*边数*/WeightTypeG[MaxVertexNum][MaxVertexNum];/*邻接矩阵*/DataTypeData[MaxVertexNum];/*存顶点的数据*//*注意：很多情况下，顶点无数据，此时Data[]可以不用出现*/};typedefPtrToGNodeMGraph;/*以邻接矩阵存储的图类型*/MGraphCreateGraph(intVertexNum){/*初始化一个有VertexNum个顶点但没有边的图*/VertexV,W;MGraphGraph;Graph=(MGraph)malloc(sizeof(structGNode));/*建立图*/Graph-Nv=VertexNum;Graph-Ne=0;/*初始化邻接矩阵*//*注意：这里默认顶点编号从0开始，到(Graph-Nv-1)*/for(V=0;VNv;V++)for(W=0;WNv;W++)Graph-G[V][W]=INFINITY;returnGraph;}voidInsertEdge(MGraphGraph,EdgeE){/*插入边*/Graph-G[E-V1][E-V2]=E-Weight;/*若是无向图，还要插入边*/Graph-G[E-V2][E-V1]=E-Weight;}MGraphBuildGraph(){MGraphGraph;EdgeE;VertexV;intNv,i;scanf("%d",Nv);/*读入顶点个数*/Graph=CreateGraph(Nv);/*初始化有Nv个顶点但没有边的图*/scanf("%d",(Graph-Ne));/*读入边数*/if(Graph-Ne!=0){/*如果有边*/E=(Edge)malloc(sizeof(structENode));/*建立边结点*//*读入边，格式为"起点终点权重"，插入邻接矩阵*/for(i=0;iNe;i++){scanf("%d%d%d",E-V1,E-V2,E-Weight);/*注意：如果权重不是整型，Weight的读入格式要改*/InsertEdge(Graph,E);}}/*如果顶点有数据的话，读入数据*/for(V=0;VNv;V++)scanf("%c",(Graph-Data[V]));returnGraph;}
1.2图的邻接表表示法
/*图的邻接表表示法*/#defineMaxVertexNum/*最大顶点数设为*/typedefintVertex;/*用顶点下标表示顶点,为整型*/typedefintWeightType;/*边的权值设为整型*/typedefcharDataType;/*顶点存储的数据类型设为字符型*//*边的定义*/typedefstructENode*PtrToENode;structENode{VertexV1,V2;/*有向边*/WeightTypeWeight;/*权重*/};typedefPtrToENodeEdge;/*邻接点的定义*/typedefstructAdjVNode*PtrToAdjVNode;structAdjVNode{VertexAdjV;/*邻接点下标*/WeightTypeWeight;/*边权重*/PtrToAdjVNodeNext;/*指向下一个邻接点的指针*/};/*顶点表头结点的定义*/typedefstructVnode{PtrToAdjVNodeFirstEdge;/*边表头指针*/DataTypeData;/*存顶点的数据*//*注意：很多情况下，顶点无数据，此时Data可以不用出现*/}AdjList[MaxVertexNum];/*AdjList是邻接表类型*//*图结点的定义*/typedefstructGNode*PtrToGNode;structGNode{intNv;/*顶点数*/intNe;/*边数*/AdjListG;/*邻接表*/};typedefPtrToGNodeLGraph;/*以邻接表方式存储的图类型*/LGraphCreateGraph(intVertexNum){/*初始化一个有VertexNum个顶点但没有边的图*/VertexV;LGraphGraph;Graph=(LGraph)malloc(sizeof(structGNode));/*建立图*/Graph-Nv=VertexNum;Graph-Ne=0;/*初始化邻接表头指针*//*注意：这里默认顶点编号从0开始，到(Graph-Nv-1)*/for(V=0;VNv;V++)Graph-G[V].FirstEdge=NULL;returnGraph;}voidInsertEdge(LGraphGraph,EdgeE){PtrToAdjVNodeNewNode;/*插入边*//*为V2建立新的邻接点*/NewNode=(PtrToAdjVNode)malloc(sizeof(structAdjVNode));NewNode-AdjV=E-V2;NewNode-Weight=E-Weight;/*将V2插入V1的表头*/NewNode-Next=Graph-G[E-V1].FirstEdge;/*此端好做插入，请做理解*/Graph-G[E-V1].FirstEdge=NewNode;/*若是无向图，还要插入边*//*为V1建立新的邻接点*/NewNode=(PtrToAdjVNode)malloc(sizeof(structAdjVNode));NewNode-AdjV=E-V1;NewNode-Weight=E-Weight;/*将V1插入V2的表头*/NewNode-Next=Graph-G[E-V2].FirstEdge;Graph-G[E-V2].FirstEdge=NewNode;}LGraphBuildGraph(){LGraphGraph;EdgeE;VertexV;intNv,i;scanf("%d",Nv);/*读入顶点个数*/Graph=CreateGraph(Nv);/*初始化有Nv个顶点但没有边的图*/scanf("%d",(Graph-Ne));/*读入边数*/if(Graph-Ne!=0){/*如果有边*/E=(Edge)malloc(sizeof(structENode));/*建立边结点*//*读入边，格式为"起点终点权重"，插入邻接矩阵*/for(i=0;iNe;i++){scanf("%d%d%d",E-V1,E-V2,E-Weight);/*注意：如果权重不是整型，Weight的读入格式要改*/InsertEdge(Graph,E);}}/*如果顶点有数据的话，读入数据*/for(V=0;VNv;V++)scanf("%c",(Graph-G[V].Data));returnGraph;}
2.图的遍历
2.1邻接表存储的图进行DFS
/*邻接表存储的图-DFS*/voidVisit(VertexV){printf("正在访问顶点%d\n",V);}/*Visited[]为全局变量，已经初始化为false*/voidDFS(LGraphGraph,VertexV,void(*Visit)(Vertex)){/*以V为出发点对邻接表存储的图Graph进行DFS搜索*/PtrToAdjVNodeW;Visit(V);/*访问第V个顶点*/Visited[V]=true;/*标记V已访问*/for(W=Graph-G[V].FirstEdge;W;W=W-Next)/*对V的每个邻接点W-AdjV*/if(!Visited[W-AdjV])/*若W-AdjV未被访问*/DFS(Graph,W-AdjV,Visit);/*则递归访问之*/}
2.2邻接矩阵存储的图进行BFS
/*邻接矩阵存储的图-BFS*//*IsEdge(Graph,V,W)检查是否图Graph中的一条边，即W是否V的邻接点。*//*此函数根据图的不同类型要做不同的实现，关键取决于对不存在的边的表示方法。*//*例如对有权图,如果不存在的边被初始化为INFINITY,则函数实现如下:*/boolIsEdge(MGraphGraph,VertexV,VertexW){returnGraph-G[V][W]INFINITY?true:false;}/*Visited[]为全局变量，已经初始化为false*/voidBFS(MGraphGraph,VertexS,void(*Visit)(Vertex)){/*以S为出发点对邻接矩阵存储的图Graph进行BFS搜索*/QueueQ;VertexV,W;Q=CreateQueue(MaxSize);/*创建空队列,MaxSize为外部定义的常数*//*访问顶点S：此处可根据具体访问需要改写*/Visit(S);Visited[S]=true;/*标记S已访问*/AddQ(Q,S);/*S入队列*/while(!IsEmpty(Q)){V=DeleteQ(Q);/*弹出V*/for(W=0;WNv;W++)/*对图中的每个顶点W*//*若W是V的邻接点并且未访问过*/if(!Visited[W]IsEdge(Graph,V,W)){/*访问顶点W*/Visit(W);Visited[W]=true;/*标记W已访问*/AddQ(Q,W);/*W入队列*/}}/*while结束*/}
3.最短路径问题
3.1邻接表存储-无权图的单源最短路算法
/*邻接表存储-无权图的单源最短路算法*//*dist[]和path[]全部初始化为-1*/voidUnweighted(LGraphGraph,intdist[],intpath[],VertexS){QueueQ;VertexV;PtrToAdjVNodeW;Q=CreateQueue(Graph-Nv);/*创建空队列,MaxSize为外部定义的常数*/dist[S]=0;/*初始化源点*/AddQ(Q,S);while(!IsEmpty(Q)){V=DeleteQ(Q);for(W=Graph-G[V].FirstEdge;W;W=W-Next)/*对V的每个邻接点W-AdjV*/if(dist[W-AdjV]==-1){/*若W-AdjV未被访问过*/dist[W-AdjV]=dist[V]+1;/*W-AdjV到S的距离更新*/path[W-AdjV]=V;/*将V记录在S到W-AdjV的路径上*/AddQ(Q,W-AdjV);}}/*while结束*/}
3.2邻接矩阵存储-有权图的单源最短路算法
/*邻接矩阵存储-有权图的单源最短路算法*/VertexFindMinDist(MGraphGraph,intdist[],intcollected[]){/*返回未被收录顶点中dist最小者*/VertexMinV,V;intMinDist=INFINITY;for(V=0;VNv;V++){if(collected[V]==falsedist[V]MinDist){/*若V未被收录，且dist[V]更小*/MinDist=dist[V];/*更新最小距离*/MinV=V;/*更新对应顶点*/}}if(MinDistINFINITY)/*若找到最小dist*/returnMinV;/*返回对应的顶点下标*/elsereturnERROR;/*若这样的顶点不存在，返回错误标记*/}boolDijkstra(MGraphGraph,intdist[],intpath[],VertexS){intcollected[MaxVertexNum];VertexV,W;
3.3邻接矩阵存储-多源最短路算法
/*邻接矩阵存储-多源最短路算法*/boolFloyd(MGraphGraph,WeightTypeD[][MaxVertexNum],Vertexpath[][MaxVertexNum]){Vertexi,j,k;/*初始化*/for(i=0;iNv;i++)for(j=0;jNv;j++){D[j]=Graph-G[j];path[j]=-1;}for(k=0;kNv;k++)for(i=0;iNv;i++)for(j=0;jNv;j++)if(D[k]+D[k][j]D[j]){D[j]=D[k]+D[k][j];if(i==jD[j]span=""0)/*若发现负值圈*/returnfalse;/*不能正确解决，返回错误标记*/path[j]=k;}
4.最小生成树
4.1Prim
/*邻接矩阵存储-Prim最小生成树算法*/VertexFindMinDist(MGraphGraph,WeightTypedist[]){/*返回未被收录顶点中dist最小者*/VertexMinV,V;WeightTypeMinDist=INFINITY;for(V=0;VNv;V++){if(dist[V]!=0dist[V]MinDist){/*若V未被收录，且dist[V]更小*/MinDist=dist[V];/*更新最小距离*/MinV=V;/*更新对应顶点*/}}if(MinDistINFINITY)/*若找到最小dist*/returnMinV;/*返回对应的顶点下标*/elsereturnERROR;/*若这样的顶点不存在，返回-1作为标记*/}intPrim(MGraphGraph,LGraphMST){/*将最小生成树保存为邻接表存储的图MST，返回最小权重和*/WeightTypedist[MaxVertexNum],TotalWeight;Vertexparent[MaxVertexNum],V,W;intVCount;EdgeE;/*初始化。默认初始点下标是0*/for(V=0;VNv;V++){/*这里假设若V到W没有直接的边，则Graph-G[V][W]定义为INFINITY*/dist[V]=Graph-G[0][V];parent[V]=0;/*暂且定义所有顶点的父结点都是初始点0*/}TotalWeight=0;/*初始化权重和*/VCount=0;/*初始化收录的顶点数*//*创建包含所有顶点但没有边的图。注意用邻接表版本*/MST=CreateGraph(Graph-Nv);E=(Edge)malloc(sizeof(structENode));/*建立空的边结点*//*将初始点0收录进MST*/dist[0]=0;VCount++;parent[0]=-1;/*当前树根是0*/while(1){V=FindMinDist(Graph,dist);/*V=未被收录顶点中dist最小者*/if(V==ERROR)/*若这样的V不存在*/break;/*算法结束*//*将V及相应的边
收录进MST*/E-V1=parent[V];E-V2=V;E-Weight=dist[V];InsertEdge(MST,E);TotalWeight+=dist[V];dist[V]=0;VCount++;for(W=0;WNv;W++)/*对图中的每个顶点W*/if(dist[W]!=0Graph-G[V][W]INFINITY){/*若W是V的邻接点并且未被收录*/if(Graph-G[V][W]dist[W]){/*若收录V使得dist[W]变小*/dist[W]=Graph-G[V][W];/*更新dist[W]*/parent[W]=V;/*更新树*/}}}/*while结束*/if(VCountGraph-Nv)/*MST中收的顶点不到
V
个*/TotalWeight=ERROR;returnTotalWeight;/*算法执行完毕，返回最小权重和或错误标记*/}
4.2Kruskal
/*邻接表存储-Kruskal最小生成树算法*//*--------------------顶点并查集定义--------------------*/typedefVertexElementType;/*默认元素可以用非负整数表示*/typedefVertexSetName;/*默认用根结点的下标作为集合名称*/typedefElementTypeSetType[MaxVertexNum];/*假设集合元素下标从0开始*/voidInitializeVSet(SetTypeS,intN){/*初始化并查集*/ElementTypeX;for(X=0;XN;X++)S[X]=-1;}voidUnion(SetTypeS,SetNameRoot1,SetNameRoot2){/*这里默认Root1和Root2是不同集合的根结点*//*保证小集合并入大集合*/if(S[Root2]S[Root1]){/*如果集合2比较大*/S[Root2]+=S[Root1];/*集合1并入集合2*/S[Root1]=Root2;}else{/*如果集合1比较大*/S[Root1]+=S[Root2];/*集合2并入集合1*/S[Root2]=Root1;}}SetNameFind(SetTypeS,ElementTypeX){/*默认集合元素全部初始化为-1*/if(S[X]0)/*找到集合的根*/returnX;elsereturnS[X]=Find(S,S[X]);/*路径压缩*/}boolCheckCycle(SetTypeVSet,VertexV1,VertexV2){/*检查连接V1和V2的边是否在现有的最小生成树子集中构成回路*/VertexRoot1,Root2;Root1=Find(VSet,V1);/*得到V1所属的连通集名称*/Root2=Find(VSet,V2);/*得到V2所属的连通集名称*/if(Root1==Root2)/*若V1和V2已经连通，则该边不能要*/returnfalse;else{/*否则该边可以被收集，同时将V1和V2并入同一连通集*/Union(VSet,Root1,Root2);returntrue;}}/*--------------------并查集定义结束--------------------*//*--------------------边的最小堆定义--------------------*/voidPercDown(EdgeESet,intp,intN){/*改编代码4.24的PercDown(MaxHeapH,intp)*//*将N个元素的边数组中以ESet[p]为根的子堆调整为关于Weight的最小堆*/intParent,Child;structENodeX;X=ESet[p];/*取出根结点存放的值*/for(Parent=p;(Parent*2+1)N;Parent=Child){Child=Parent*2+1;if((Child!=N-1)(ESet[Child].WeightESet[Child+1].Weight))Child++;/*Child指向左右子结点的较小者*/if(X.Weight=ESet[Child].Weight)break;/*找到了合适位置*/else/*下滤X*/ESet[Parent]=ESet[Child];}ESet[Parent]=X;}voidInitializeESet(LGraphGraph,EdgeESet){/*将图的边存入数组ESet，并且初始化为最小堆*/VertexV;PtrToAdjVNodeW;intECount;/*将图的边存入数组ESet*/ECount=0;for(V=0;VNv;V++)for(W=Graph-G[V].FirstEdge;W;W=W-Next)if(VW-AdjV){/*避免重复录入无向图的边，只收V1V2的边*/ESet[ECount].V1=V;ESet[ECount].V2=W-AdjV;ESet[ECount++].Weight=W-Weight;}/*初始化为最小堆*/for(ECount=Graph-Ne/2;ECount=0;ECount--)PercDown(ESet,ECount,Graph-Ne);}intGetEdge(EdgeESet,intCurrentSize){/*给定当前堆的大小CurrentSize，将当前最小边位置弹出并调整堆*//*将最小边与当前堆的最后一个位置的边交换*/Swap(ESet[0],ESet[CurrentSize-1]);/*将剩下的边继续调整成最小堆*/PercDown(ESet,0,CurrentSize-1);returnCurrentSize-1;/*返回最小边所在位置*/}/*--------------------最小堆定义结束--------------------*/intKruskal(LGraphGraph,LGraphMST){/*将最小生成树保存为邻接表存储的图MST，返回最小权重和*/WeightTypeTotalWeight;intECount,NextEdge;SetTypeVSet;/*顶点数组*/EdgeESet;/*边数组*/InitializeVSet(VSet,Graph-Nv);/*初始化顶点并查集*/ESet=(Edge)malloc(sizeof(structENode)*Graph-Ne);InitializeESet(Graph,ESet);/*初始化边的最小堆*//*创建包含所有顶点但没有边的图。注意用邻接表版本*/MST=CreateGraph(Graph-Nv);TotalWeight=0;/*初始化权重和*/ECount=0;/*初始化收录的边数*/NextEdge=Graph-Ne;/*原始边集的规模*/while(ECountGraph-Nv-1){/*当收集的边不足以构成树时*/NextEdge=GetEdge(ESet,NextEdge);/*从边集中得到最小边的位置*/if(NextEdge0)/*边集已空*/break;/*如果该边的加入不构成回路，即两端结点不属于同一连通集*/if(CheckCycle(VSet,ESet[NextEdge].V1,ESet[NextEdge].V2)==true){/*将该边插入MST*/InsertEdge(MST,ESet+NextEdge);TotalWeight+=ESet[NextEdge].Weight;/*累计权重*/ECount++;/*生成树中边数加1*/}}if(ECountGraph-Nv-1)TotalWeight=-1;/*设置错误标记，表示生成树不存在*/returnTotalWeight;}
5.拓扑排序
5.1邻接表存储的拓扑排序算法
/*邻接表存储-拓扑排序算法*/boolTopSort(LGraphGraph,VertexTopOrder[]){/*对Graph进行拓扑排序,TopOrder[]顺序存储排序后的顶点下标*/intIndegree[MaxVertexNum],cnt;VertexV;PtrToAdjVNodeW;QueueQ=CreateQueue(Graph-Nv);/*初始化Indegree[]*/for(V=0;VNv;V++)Indegree[V]=0;/*遍历图，得到Indegree[]*/for(V=0;VNv;V++)for(W=Graph-G[V].FirstEdge;W;W=W-Next)Indegree[W-AdjV]++;/*对有向边AdjV累计终点的入度*//*将所有入度为0的顶点入列*/for(V=0;VNv;V++)if(Indegree[V]==0)AddQ(Q,V);/*下面进入拓扑排序*/cnt=0;while(!IsEmpty(Q)){V=DeleteQ(Q);/*弹出一个入度为0的顶点*/TopOrder[cnt++]=V;/*将之存为结果序列的下一个元素*//*对V的每个邻接点W-AdjV*/for(W=Graph-G[V].FirstEdge;W;W=W-Next)if(--Indegree[W-AdjV]==0)/*若删除V使得W-AdjV入度为0*/AddQ(Q,W-AdjV);/*则该顶点入列*/}/*while结束*/if(cnt!=Graph-Nv)returnfalse;/*说明图中有回路,返回不成功标志*/elsereturntrue;}
预览时标签不可点收录于话题#个上一篇下一篇