对于如图所示的无向带权图G采用普里姆算法和克鲁斯卡尔算法分别输出图的邻接矩阵存储和从顶点0出发的最小生成树。
如图所示,那你的图呢?不过i这个很简单,你对照教材自己看下就应该会,不会就是你没看书
这得益于操作系统的虚拟内存技术。虚拟内存使得应用程序认为它拥有连续的可用的内存(一个连续完整的地址空间),使得进程逻辑上有很大的连续内存地址空间。实际上一部分对应物理内存上的块,还有一部分没加载进内存的对应在外部磁盘,在需要时进行数据交换。这样就可以让程序拥有超过系统物理内存大小的可用的内存空间。
普里姆算法和克鲁斯卡尔算法在生成无向带权图的最小生成树方面有不同的实现方法:
1.普里姆算法:
普里姆算法的主要思想是从一个点开始,根据“合法边”的定义来扩展,每次加入与当前生成树相连的权值最小的顶点。因此,首先需要定义一个变量数组,用于存储点与点之间的关系,这个数组就是邻接矩阵。接着定义两个数组,一个用于存储已经选定的点,另一个用于存储待选点中与已选点相连的最短距离。具体流程如下:
示例代码:
考虑一个图示例:
0-1 | | 2 3-4
其中顶点0为起点,距离表示在边上。
邻接矩阵为:
0 1 2 3 4 0 0 2 3 inf inf 1 2 0 5 6 inf 2 3 5 0 4 inf 3 inf 6 4 0 6 4 inf inf inf 6 0
关键代码如下:
int prim(int G[V][V], int src){ int key[V], vis[V]; memset(key, INF, sizeof(key)); //初始化待选点的距离为正无穷 memset(vis, 0, sizeof(vis)); //初始化已选点数组为0 key[src] = 0; //起点的距离为0 for(int i = 0; i < V - 1; i++){
int u = -1; for(int j = 0; j < V; j++){ //在待选点中找到与当前已选点相连的最短边 if(!vis[j] && (u == -1 || key[j] < key[u])) u = j; } vis[u] = 1; //将当前待选点加入已选点数组中 for(int v = 0; v < V; v++){
if(G[u][v] != INF){ //更新待选点中与已选点相连的最短距离 if(!vis[v] && G[u][v] < key[v]) key[v] = G[u][v]; } } } int res = 0; for(int i = 0; i < V; i++) //计算所有选中点的权值之和 res += key[i]; return res; }
2.克鲁斯卡尔算法:
克鲁斯卡尔算法的核心思想是贪心,从所有的边里删选,使得图连通的同时边权之和最小。这个算法不需要邻接矩阵,只需要存储每条边的权值和两端点即可。步骤如下:
示例代码:
考虑一个图示例:
A----6----B | | | | 3 | 4 | |7 | | | D----5----C
其中的顶点为A、B、C、D,边上表示权值。
每个边跨越两个点,因此用一个结构体储存它们。
struct Edge{ int u, v, weight; };
下面是关键代码:
int find(int parent[], int i){ //查找祖先结点 if(parent[i] == i) return i; return find(parent, parent[i]); }
void union_set(int parent[], int rank[], int x, int y){ //合并两个结点 int root1 = find(parent, x); int root2 = find(parent, y); if(rank[root1] < rank[root2]) parent[root1] = root2; else if(rank[root1] > rank[root2]) parent[root2] = root1; else{ parent[root2] = root1; rank[root1]++; } }
int cmp(const void a, const void b){ //对边按权值排序 struct Edge x = (Edge)a; struct Edge y = (Edge)b; return x->weight - y->weight; }
int kruskal(struct Edge arr[], int V, int E){ int res = 0, i = 0, ecount = 0; int parent[V], rank[V]; for(int v = 0; v < V; v++){ //初始化每个结点为单独的集合 parent[v] = v; rank[v] = 0; } sort(arr, arr + E, cmp); //对边按权值进行排序 while(ecount < V - 1){ //从小到大遍历所有边 int u = arr[i].u, v = arr[i].v; int root1 = find(parent, u); int root2 = find(parent, v); if(root1 != root2){ //如果不构成回路则加入 union_set(parent, rank, root1, root2); res += arr[i].weight; ecount++; } i++; } return res; }
以上是两种算法实现的步骤和关键代码,下面详细介绍它们实际应用中的一些情况。
普里姆算法的优缺点和实际应用:
优点:
适合稠密图,即边数非常多的图,因为邻接矩阵的空间复杂度为O(n2),边数多的时候会比较高效。
可以处理带权图和不连通图。
实现较简单。
缺点:
只能处理连通图,不适合处理森林。
在稀疏图中效率比较低,因为它需要遍历整个图。
不如克鲁斯卡尔算法灵活。
典型应用:
最小生成树问题。
路由器算法。
克鲁斯卡尔算法的优缺点和实际应用:
优点:
适用于稀疏图,即边数相较于顶点数量少的图,因为它只需要存储每条边的权值和两端点即可。
可以处理带权图和不连通图。
缺点:
只能处理连通图。
与普里姆算法相比,速度较慢。
与其他算法相比,实现较为复杂。
典型应用:
最小生成树问题。