7.4.2广度优先搜索遍历
图的广度优先搜索遍历类似于树的按层次遍历,其基本思想为从图中的某个顶点V0出发，在访问此顶点之后依次访问V0。的所有未被访问的邻接点,之后按这些邻接点被访问的先后次序依次访问它们的邻接点,直至图中所有和V0有路径相通的顶点都被访问到。若此时图中尚有顶点未被访问,则另选图中一个未被访问的顶点作为新的出发点,重复上述过程,直至图中所有顶点都被访问到。
相关代码请看配套资源
7-BFSAdjMatrix.c
#include<stdio.h> #include "2-邻接矩阵plus.c" //去掉main() #include "链队列.c" //去掉main() void main(){ printf("创建\n"); AdjMatrix* G=(AdjMatrix*)malloc(sizeof(AdjMatrix)); printf("输入图的类型 "); printf("无向图(1) "); printf("有向图(2) "); printf("无向网(3) "); printf("有向网(4) ："); scanf("%d",&G->t); Create(G); printf("BFS:\n"); // int v0=1; // BFSAdjMatrix(*G,v0); TraverseG(*G); printf("\n"); printf("打印\n"); Printf(G); }
注意这是BFS，不是DFS(显示错误)
相关代码请看配套资源
8-BFSAdjList.c
void main(){ printf("创建\n"); AdjList* G=(AdjList*)malloc(sizeof(AdjList)); printf("输入图的类型 "); printf("无向图(1) "); printf("有向图(2) "); printf("无向网(3) "); printf("有向网(4) ："); scanf("%d",&G->t); Create(G); printf("BFS:\n"); // int v0=1; // BFSAdjList(*G,v0); TraverseG(*G); printf("\n"); printf("打印\n"); Printf(G); }
运行结果如下
7.5图的应用
7.5.1最小生成树
图G的生成树是指该图的一个极小连通子图,含有图中的全部n个顶点,但只有足以构成
棵树的n-1条边。显然,生成树不唯一,可能有多棵。
在一个连通网的所有生成树中,选中的n-1条边权值(代价)之和最小的生成树被称为该连通网的“最小代价生成树"(minimum-cost spanning tree,MST)。
MST性质:设图G=<V,R>是一个带权的连通图,即连通网,集合U是顶点集V的一个非空
子集。构建生成树时需要一条边连通顶点集合U和V-U。如果(u,v)∈R,其中,u∈U,v∈V-U,且边(u，v)是具有最小权值的一条边,那么一定存在一棵包含边(u,v)的最小生成树。
1.Prim算法（加点法）
适用于稠密图
基本思想:从连通网络N={v,E}中的某一顶点u出发，选择与它关联的具有最小权值的边(u0,v),将其顶点加人生成树的顶点集合U。以后每一步从一个顶点在U中,而另一个顶点不在U中的各条边中选择权值最小的边(u,v),把它的顶点加人集合U中,这意味着(u,v)也加入生成树的边集合。如此继续下去，直到网络中的所有顶点都加入生成树的顶点集合U中为止。
具体地，记N是连通网的顶点集,U是求得生成树的顶点集,TE是求得生成树的边集
①开始时,U={U0}TE=∅。
②修正U到其余顶点N-U的最小权值,将具有最小权值的边纳入TE,对应的顶点纳入U。
③重复②直到U=N。
经过上述步骤,TE中包含了G中的n-1条边,此时选取到的所有顶点及边恰好就构成了G的一棵最小生成树。
相关代码请看配套资源
9-Prim.c
#include<stdio.h> #include "2-邻接矩阵plus.c" typedef int VertexData; int main(){ printf("创建\n"); AdjMatrix* G=(AdjMatrix*)malloc(sizeof(AdjMatrix)); printf("输入图的类型 "); printf("无向图(1) "); printf("有向图(2) "); printf("无向网(3) "); printf("有向网(4) ："); scanf("%d",&G->t); Create(G); printf("最小生成树\n"); VertexData u=1; Prim(*G,u); printf("打印\n"); Printf(G); }
运行结果如下
说明
最小生成树 每两个代表生成树一个边的两个顶点 4 7 可以改成7 10也是对的 把printf("%d %d ",u0,v0); 替换为printf("第%d条边:%d--%d--%d\n ",e,u0,min,v0); 就美观了
2.Kruskal算法（加边法）
适用于稀疏图
Kruskal算法使用的贪心准则是,从剩下的边中选择不会产生环路且具最小权值的边加人生成树的边集。
基本思想:先构造一个只含n个顶点的子图SG,然后从权值最小的边
开始,若它的添加不使SG中产生回路,则在SG上加入该边,依次按照权值通增的次序,选择合适的边进行添加，如此重复，直至加完n-1条边为止。
7.5.2 拓扑排序
假设以有向图表示个工程的施工图或程序的数据流图,每个顶点代表一个活动,弧<vi，vj)表示活动必须先于活动j进行。我们将顶点表示活动、弧表示活动间优先关系的有向无“顶点表示活动的网”,简称"AOV-网"(activity on vertex),图中不允许出现回路。
对于一个AOV-网,若存在满足以下性质的一个线性序列,则这个线性序列称为“拓扑序列”。
①网中的所有顶点都在该序列中。
②若顶点i到顶点Vj存在一条路径,则在线性序列中，Vi一定排在Vj之前。
构造拓扑序列的操作称为“拓扑排序”。实际上,拓扑排序就是离散数学中由某个集合上一个偏序得到该集合上的一个全序的操作。
那么,对于一个AOV-网来说,如何求得拓扑序列呢?其方法如下。
①从有向图中选取一个没有前驱的顶点并输出之。
②从有向图中删去该顶点以及所有以它为尾的弧。
③重复上述两步,直至图空(不存在回路),或者图不空但找不到无前驱的顶点为止(存在 回路)。可见,拓扑排序可以检查有向图中是否存在回路。
