最小生成树，采用普里姆算法和克鲁斯卡尔算法分别输出
#普里姆算法
#克鲁斯卡尔算法
#分布解析
对于如图所示的无向带权图采用普里姆算法和克鲁斯卡尔算法分别输出图的领接矩阵存储和从顶点0出发的最小生成树。
对每一步需要详细解析，麻烦各位。
以下是使用C语言实现普里姆算法和克鲁斯卡尔算法生成最小生成树并输出领接矩阵存储的代码，有用请采纳呦：
#include <stdio.h>
#include <stdlib.h>
#include <limits.h>
// 图的最大顶点数
#define MAX_VERTICES 10
// 图的边类型
typedef struct {
int u;
int v;
int w;
} Edge;
// 图类型
typedef struct {
Edge edges[MAX_VERTICES * (MAX_VERTICES - 1) / 2];
int n; // 图中顶点数
} Graph;
// 最小堆类型
typedef struct {
int *data;
int size;
} MinHeap;
// 构建图
void createGraph(Graph *g) {
g->n = 5;
g->edges[0] = (Edge) {0, 1, 2};
g->edges[1] = (Edge) {0, 3, 6};
g->edges[2] = (Edge) {1, 2, 3};
g->edges[3] = (Edge) {1, 3, 8};
g->edges[4] = (Edge) {1, 4, 5};
g->edges[5] = (Edge) {2, 4, 7};
g->edges[6] = (Edge) {3, 4, 9};
}
// 交换两个元素的值
void swap(int *a, int *b) {
int temp = *a;
*a = *b;
*b = temp;
}
// 最小堆的上移操作
void siftUp(MinHeap *heap, int i) {
while (i > 0) {
int parent = (i - 1) / 2;
if (heap->data[i] >= heap->data[parent]) {
break;
}
swap(&heap->data[i], &heap->data[parent]);
i = parent;
}
}
// 最小堆的下移操作
void siftDown(MinHeap *heap, int i) {
while (2 * i + 1 < heap->size) {
int left = 2 * i + 1;
int right = 2 * i + 2;
int min_index = i;
if (heap->data[left] < heap->data[min_index]) {
min_index = left;
}
if (right < heap->size && heap->data[right] < heap->data[min_index]) {
min_index = right;
}
if (min_index == i) {
break;
}
swap(&heap->data[i], &heap->data[min_index]);
i = min_index;
}
}
// 将元素插入最小堆
void insert(MinHeap *heap, int x) {
heap->data[heap->size++] = x;
siftUp(heap, heap->size - 1);
}
// 从最小堆中取出最小元素
int extractMin(MinHeap *heap) {
int min_value = heap->data[0];
heap->data[0] = heap->data[--heap->size];
siftDown(heap, 0);
return min_value;
}
// 判断最小堆是否为空
int isHeapEmpty(MinHeap *heap) {
return (heap->size == 0);
}
// 初始化最小堆
void initHeap(MinHeap *heap, int *data, int size) {
heap->data = data;
heap->size = size;
for (int i = (size - 2) / 2; i >= 0; i--) {
siftDown(heap, i);
}
}
// 普里姆算法生成最小生成树
void prim(Graph *g, int *parent) {
// 初始化parent和dist数组
for (int i = 0; i < g->n; i++) {
parent[i] = -1;
}
int dist[g->n];
for (int i = 0; i < g->n; i++) {
dist[i] = INT_MAX;
}
// 从顶点0开始搜索
dist[0] = 0;
MinHeap heap;
int heap_data[MAX_VERTICES];
initHeap(&heap, heap_data, 0);
insert(&heap, 0);
while (!isHeapEmpty(&heap)) {
int u = extractMin(&heap);
for (int i = 0; i < g->n; i++) {
if (i != u) {
for (int j = 0; j < g->n * (g->n - 1) / 2; j++) {
Edge e = g->edges[j];
if ((e.u == u && e.v == i) || (e.u == i && e.v == u)) {
if (dist[i] > e.w) {
dist[i] = e.w;
parent[i] = u;
insert(&heap, i);
}
break;
}
}
}
}
}
}
// 克鲁斯卡尔算法生成最小生成树
void kruskal(Graph *g, int *parent) {
// 初始化parent数组
for (int i = 0; i < g->n; i++) {
parent[i] = i;
}
int m = g->n * (g->n - 1) / 2;
Edge edges[MAX_VERTICES * (MAX_VERTICES - 1) / 2];
for (int i = 0; i < m; i++) {
edges[i] = g->edges[i];
}
// 对edges数组按边权进行排序
for (int i = 0; i < m - 1; i++) {
for (int j = i + 1; j < m; j++) {
if (edges[i].w > edges[j].w) {
Edge temp = edges[i];
edges[i] = edges[j];
edges[j] = temp;
}
}
}
// 构建最小生成树
for (int i = 0; i < m; i++) {
Edge e = edges[i];
int u = e.u;
int v = e.v;
while (u != parent[u]) {
u = parent[u];
}
while (v != parent[v]) {
v = parent[v];
}
if (u != v) {
parent[u] = v;
}
}
}
// 输出领接矩阵存储的图
void printGraph(Graph *g) {
int matrix[MAX_VERTICES][MAX_VERTICES] = {0};
for (int i = 0; i < g->n * (g->n - 1) / 2; i++) {
Edge e = g->edges[i];
matrix[e.u][e.v] = matrix[e.v][e.u] = e.w;
}
for (int i = 0; i < g->n; i++) {
for (int j = 0; j < g->n; j++) {
printf("%d ", matrix[i][j]);
}
printf("\n");
}
}
int main() {
Graph g;
createGraph(&g);
int parent[MAX_VERTICES];
prim(&g, parent);
printf("Prim:\n");
for (int i = 1; i < g.n; i++) {
printf("(%d, %d)\n", parent[i], i);
}
printGraph(&g);
kruskal(&g, parent);
printf("Kruskal:\n");
for (int i = 1; i < g.n; i++) {
printf("(%d, %d)\n", parent[i], i);
}
printGraph(&g);
return 0;
}
该程序中，首先定义了图和边的结构体，定义了最小堆的结构体和操作函数，并实现了普里姆算法和克鲁斯卡尔算法生成最小生成树的函数。其中，最小堆采用数组实现，每个元素的值为某个顶点的下标，插入元素和取出最小元素的时间复杂度均为$O(logn)$。对于每个算法，都先初始化parent数组和dist数组，然后根据算法的不同，进行不同的操作。最后，输出生成的最小生成树和领接矩阵存储的图。
我只有示例可以供你参考
让我来为您详细解析一下普里姆算法和克鲁斯卡尔算法在该无向带权图上生成最小生成树的过程。
首先，让我们将该图的邻接矩阵表示出来：
0 1 2 3 4 5
0 0 14 4 0 0 0
1 14 0 8 74 0 0
2 4 8 0 2 54 64
3 0 74 2 0 5 0
4 0 0 54 5 0 7
5 0 0 64 0 7 0
其中，每一行表示一个顶点，每一列表示一个顶点，对应的数值表示两个顶点之间的边权重。如果两个顶点之间没有边相连，则对应的数值为0。
接下来，我们分别使用普里姆算法和克鲁斯卡尔算法来生成最小生成树。
普里姆算法：
普里姆算法是一种贪心算法，从一个任意顶点开始，每次选择一条与当前生成树相邻的边中权重最小的边，并将其连接到生成树上，直到生成树包含所有的顶点为止。下面是在该图上使用普里姆算法生成最小生成树的详细过程：
从顶点0开始，将其加入生成树中。
找到与生成树相邻的边中权重最小的边，即(0, 2)，将其加入生成树中。
找到与生成树相邻的边中权重最小的边，即(2, 3)，将其加入生成树中。
找到与生成树相邻的边中权重最小的边，即(3, 5)，将其加入生成树中。
找到与生成树相邻的边中权重最小的边，即(5, 4)，将其加入生成树中。
所有的顶点都已被包含在生成树中，最小生成树生成完毕。
下面是普里姆算法在该图上生成最小生成树的过程中生成树的邻接矩阵表示：
0 1 2 3 4 5
0 0 14 4 0 0 0
1 14 0 0 74 0 0
2 4 0 0 2 0 0
3 0 74 2 0 0 0
4 0 0 0 0 0 7
5 0 0 0 0 7 0
生成树的邻接矩阵可表示为一个对称的矩阵，且只有与生成树相邻的边被保留，其他的边都被删除了。
克鲁斯卡尔算法：
克鲁斯卡尔算法也是一种贪心算法，它按照边的权值从小到大的顺序逐步构造生成树。具体来说，该算法将所有边按照权重从小到大排序，然后依次加入生成树中，直到生成树包含所有的顶点为止。如果加入一条边会形成环，则不加入该边。
下面是在该图上使用克鲁斯卡尔算法生成最小生成树的详细过程：
将所有边按照权重从小到大排序，得到以下顺序：(2, 3), (3, 5), (0, 2), (1, 2), (4, 5), (1, 3), (2, 4).
依次加入排序后的边，首先加入权重最小的边(2, 3)，得到生成树{(2, 3)}。
加入下一条边(3, 5)，得到生成树{(2, 3), (3, 5)}。
加入下一条边(0, 2)，得到生成树{(0, 2), (2, 3), (3, 5)}。
加入下一条边(1, 2)，得到生成树{(0, 2), (1, 2), (2, 3), (3, 5)}。
加入下一条边(4, 5)，得到生成树{(0, 2), (1, 2), (2, 3), (3, 5), (4, 5)}。
加入下一条边(1, 3)，会形成环，不加入该边。
加入下一条边(2, 4)，得到最小生成树{(0, 2), (1, 2), (2, 3), (3, 5), (4, 5), (2, 4)}。
下面是克鲁斯卡尔算法在该图上生成最小生成树的过程中生成树的邻接矩阵表示：
0 1 2 3 4 5
0 0 0 4 0 0 0
1 0 0 8 0 0 0
2 4 8 0 2 0 0
3 0 0 2 0 5 0
4 0 0 0 5 0 7
5 0 0 0 0 7 0
生成树的邻接矩阵同样可表示为一个对称的矩阵，且只有与生成树相邻的边被保留，其他的边都被删除了。
希望这些详细的解析能够帮助您更好地理解普里姆算法和克鲁斯卡尔算法在该图上生成最小生成树的过程。
- 你可以参考下这个问题的回答, 看看是否对你有帮助, 链接: https://ask.csdn.net/questions/7652408
- 你也可以参考下这篇文章：数据结构与算法 ~ 图 ~ 最小生成树 ~ 普里姆算法（图采用邻接矩阵方式存储）
- 除此之外, 这篇博客: 指针的用法中的 指向数组元素的指针 支持 递增 递减 运算。（实质上所有指针都支持递增递减 运算 ，但只有在数组中使用才是有意义的） 部分也许能够解决你的问题, 你可以仔细阅读以下内容或跳转源博客中阅读:
int arr[3] = {1,2,3}; int*p = arr; for(;p!=arr+3;p++){ printf("%d\n",*p); } return 0; }- 您还可以看一下 吴刚老师的【吴刚大讲堂】电商视觉的排版与应用方法课程中的 订单页面的表单视觉优化及细节处理方法小节, 巩固相关知识点
我们先简单介绍普里姆算法和克鲁斯卡尔算法：
普里姆算法：
在图 G 中选取一个起点，并将其加入到一个集合 U 中。
在剩余的节点中，选取一条边权值最小的边（起点在 U 中，终点不在 U 中），将终点加入集合 U 中，将该边加入最小生成树的边集合 E 中，直到所有节点都被加入集合 U 中。
克鲁斯卡尔算法：
将图中的所有边按权值从小到大排序。
遍历每条边，判断它所连接的两个节点是否已经连通，如果没有连通，则将这条边加入最小生成树的边集合 E 中，并将这两个节点加入一个连通集合中。
下面是两种算法的详细解析及代码实现：
普里姆算法：
我们以顶点 0 作为起点，并将其加入集合 U 中，同时记录节点 i 的父节点 pi[i] 和起点到 i 的最小边权值 min_w[i]，初始时，pi[0]=-1，min_w[0]=0，min_w[i]=无穷大。
在剩余的节点中，找到一个顶点 i，满足 pi[i]=-1 且 min_w[i] 最小，将 i 加入集合 U 中，并以 i 为起点枚举与之相邻的各个节点 j，如果节点 j 不在集合 U 中，且边权值 dist[i][j] 小于 min_w[j]，那么将 pi[j] 设置为 i，min_w[j] 设置为 dist[i][j]，表示找到了一条到 j 的更小的边。
重复步骤 2，直到所有节点都被加入集合 U 中，此时 pi 数组记录了最小生成树的各个节点的父节点，min_w 数组记录了它们和父节点之间的最小边权值。最小生成树的边集合 E 可以根据 pi 和 min_w 数组重建出来。
克鲁斯卡尔算法的代码：
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<map>
#include<set>
#include<stack>
#include<queue>
#include<vector>
#define ll long long
using namespace std;
int n,m;
int a[105];
struct node{
int p,q;
int z;
}g[10010];
bool cmp(node p,node q)
{
return p.z <q.z ;
}
void init()
{
int i;
for(i=0;i<105;i++)
a[i]=i;
}
int find(int x)
{
if(x==a[x])return a[x];
return find(a[x]);
}
int Union(int x,int y)
{
int xx=find(x);
int yy=find(y);
if(xx==yy)return 0;
a[xx]=yy;
return 1;
}
int main()
{
while(1)
{
init();
scanf("%d%d",&n,&m);
if(n==0)break;
int i,j,k,s,t;
for(i=0,j=0;i<n;i++)
{
scanf("%d%d%d",&s,&k,&t);
g[j].p =s;g[j].q =k;
g[j].z =t;j++;
g[j].p =k;g[j].q =s;
g[j].z =t;j++;
}
sort(g,g+j,cmp);//按照权值排序
int ans=0;
for(i=0,k=0;i<j;i++)
{
if(Union(g[i].p ,g[i].q ))//利用并查集判断是否构成回路
{
ans=ans+g[i].z ;k++;
}
}
if(k!=m-1)
{
printf("?\n");
}
else printf("%d\n",ans);
}
return 0;
}