当前位置：首页 > news >正文

数据结构图的应用最小生成树-普里姆算法(C语言代码+无向网+有向网+邻接矩阵存储结构)-最低附带图片+终端输入内容方便理解

news 2024/10/22 21:50:01

无向网代码如下：

#define _CRT_SECURE_NO_WARNINGS 1
#include<stdlib.h>
#include<stdio.h>
#include <limits.h>
#define MAX_SIZE 100
struct
{char adjvex;int lowcost;
}closedge[MAX_SIZE];
typedef struct
{char vexs[MAX_SIZE];int mart[MAX_SIZE][MAX_SIZE];int numVertex, numEdge;
}AMGraph;
int Locate(AMGraph G, int v)
{int i;for (i = 0; i < G.numVertex; i++){if (G.vexs[i] == v){return i;}}return -1;
}
void CreateAMGraph(AMGraph* G)
{printf("请输入顶点数+边数\n");scanf("%d %d", &G->numVertex, &G->numEdge);getchar();int i, j, k, w;printf("请输入顶点的信息\n");for (i = 0; i < G->numVertex; i++){scanf(" %c", &G->vexs[i]);//前面的空格不能省略}for (i = 0; i < G->numVertex; i++){for (j = 0; j < G->numVertex; j++){G->mart[i][j] = INT_MAX;}}printf("请输入(vi,vj)的情况以及权值\n");for (k = 0; k < G->numEdge; k++){printf("请输入第%d条边依附的顶点+权值\n", k + 1);char v1, v2;scanf(" %c %c %d", &v1, &v2, &w);//第一个%c之前必须留空格 %ci = Locate(*G, v1);j = Locate(*G, v2);G->mart[i][j] = w;G->mart[j][i] = w;}
}
int Min(AMGraph G)
{int i;int index = -1;int min = INT_MAX;for (i = 0; i < G.numVertex; i++){if (min > closedge[i].lowcost && closedge[i].lowcost != 0){min = closedge[i].lowcost;index = i;}}return index;
}
void MiniSpanTree_Prim(AMGraph G, char u)
{int k, j, i;char u0, v0;k = Locate(G, u);for (j = 0; j < G.numVertex; j++){if (j!=k){closedge[j].adjvex = u;closedge[j].lowcost = G.mart[k][j];}}closedge[k].lowcost = 0;for (i = 1; i < G.numVertex; i++){k = Min(G);//新的极小值顶点u0 = closedge[k].adjvex;v0 = G.vexs[k];printf("边 %c --> %c\n", u0, v0);closedge[k].lowcost = 0;for (j = 0; j < G.numVertex; j++){if (G.mart[k][j] < closedge[j].lowcost)//重新修改我周围的人脉（权值）{closedge[j].adjvex = G.vexs[k];closedge[j].lowcost = G.mart[k][j];}}}
}
int main()
{AMGraph G;CreateAMGraph(&G);printf("普里姆算法如下\n");MiniSpanTree_Prim(G, '0');return 0;
}

无向图图片如下：

无向网终端输入内容如下：

请输入顶点数+边数
6 10
请输入顶点的信息
0
1
2
3
4
5
请输入(vi,vj)的情况以及权值
请输入第1条边依附的顶点+权值
0 1 6
请输入第2条边依附的顶点+权值
0 2 1
请输入第3条边依附的顶点+权值
0 3 5
请输入第4条边依附的顶点+权值
1 2 5
请输入第5条边依附的顶点+权值
1 4 3
请输入第6条边依附的顶点+权值
2 3 5
请输入第7条边依附的顶点+权值
2 4 6
请输入第8条边依附的顶点+权值
2 5 4
请输入第9条边依附的顶点+权值
4 5 6
请输入第10条边依附的顶点+权值
5 3 2
普里姆算法如下
边 0 --> 2
边 2 --> 5
边 5 --> 3
边 2 --> 1
边 1 --> 4

普里姆算法走过的边如图：

有向网代码如下:

	for (k = 0; k < G->numEdge; k++){printf("请输入第%d条边依附的顶点+权值\n", k + 1);char v1, v2;scanf(" %c %c %d", &v1, &v2, &w);//第一个%c之前必须留空格 %ci = Locate(*G, v1);j = Locate(*G, v2);G->mart[i][j] = w;//G->mart[j][i] = w;}

只需要把G->mart[j][i] = w;给注销即可，因为邻接矩阵的存储结构中无向网是对称的，有向网并不是对称的

有向网的图片如下:

有向网普里姆算法终端输入如下:

请输入顶点数+边数
6 9
请输入顶点的信息
0
1
2
3
4
5
请输入(vi,vj)的情况以及权值
请输入第1条边依附的顶点+权值
0 1 5
请输入第2条边依附的顶点+权值
0 5 2
请输入第3条边依附的顶点+权值
1 2 4
请输入第4条边依附的顶点+权值
2 3 9
请输入第5条边依附的顶点+权值
3 4 7
请输入第6条边依附的顶点+权值
3 5 3
请输入第7条边依附的顶点+权值
4 0 1
请输入第8条边依附的顶点+权值
5 2 1
请输入第9条边依附的顶点+权值
5 4 8
普里姆算法如下
边 0 --> 5
边 5 --> 2
边 0 --> 1
边 5 --> 4
边 2 --> 3