prim算法怎么实现不了啊 krusal可以实现
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define maxvex 100
#define INFINITY 9999
typedef int EdgeType; /* 边上的权值类型 */
typedef struct MGraph {
EdgeType arc[maxvex][maxvex]; /*二维邻接矩阵 */
int vexnum /*图的边*/, arcnum; /* 图中当前的顶点数 */
};
typedef struct EdgeNode { /* 边表结点 */
struct EdgeNode *next; /* 链域,指向下一个邻接点 */
} EdgeNode;
typedef struct vertexnode { /* 顶点表结点 */
char data[20]; /* 顶点域,存储顶点信息 */
EdgeNode *firstedge;/* 边表头指针 */
} vertexnode, AdjList[maxvex];
typedef struct {
int parent;
int rank;
} Subset;
typedef struct {
int start;
int end;
int weight;
} Edge;
typedef struct {
AdjList adjList;
EdgeType arc[maxvex][maxvex];
int arcnum, vexnum; /* 图中当前顶点数和边数 */
} graphAdjList, * GraphAdjList;
int CreateMGraph(MGraph *G, GraphAdjList *G1);
void printCreateMGraph(MGraph *G, GraphAdjList *G1);
void Kruskal(MGraph *G);
void Prim(MGraph *G);
int find(Subset subsets[], int i);
void Union(Subset subsets[], int x, int y);
int CreateMGraph(MGraph *G, GraphAdjList *G1) {
*G1 = (GraphAdjList)malloc(sizeof(graphAdjList));
if (*G1 == NULL) {
printf("内存分配失败\n");
return 0;
}
printf("输入顶点数目: ");
scanf("%d", &G->vexnum);
printf("请输入图的边数目：");
scanf("%d", &G->arcnum);
// 为每个顶点的邻接表分配内存
for (int i = 1; i <= G->vexnum; i++) {
(*G1)->adjList[i].firstedge = NULL;
}
// 建立邻接矩阵
int i, j, w;
for (int k = 1; k <= G->arcnum; k++) {
printf("请输入第%d条边连接(vi,vj)的第一个顶点下标i(i=1,2...): ", k);
scanf("%d", &i);
printf("请输入第%d条边连接(vi,vj)的第二个顶点下标j(j=1,2...): ", k);
scanf("%d", &j);
printf("请输入第%d条边的权值：", k);
scanf("%d", &w);
G->arc[i][j] = w;
G->arc[j][i] = w;
}
// 输入顶点信息
for (int i = 1; i <= G->vexnum; i++) {
printf("请输入第%d个顶点的信息：", i);
scanf("%s", (*G1)->adjList[i].data, sizeof((*G1)->adjList[i].data));
}
return 1;
}
// Kruskal 算法实现
void Kruskal(MGraph *G) {
int numEdges = 0;
Edge result[maxvex]; // 存储最小生成树的边
Edge edges[maxvex * maxvex]; // 存储图的所有边
// 将图的所有边存入 edges 数组
for (int i = 1; i <= G->vexnum; i++) {
for (int j = i + 1; j <= G->vexnum; j++) {
if (G->arc[i][j] != 0) {
edges[numEdges].start = i;
edges[numEdges].end = j;
edges[numEdges].weight = G->arc[i][j];
numEdges++;
}
}
}
// 根据边的权值排序
for (int i = 0; i < numEdges - 1; i++) {
for (int j = 0; j < numEdges - i - 1; j++) {
if (edges[j].weight > edges[j + 1].weight) {
Edge temp = edges[j];
edges[j] = edges[j + 1];
edges[j + 1] = temp;
}
}
}
Subset subsets[maxvex];
// 初始化并查集
for (int v = 0; v < G->vexnum; v++) {
subsets[v].parent = v;
subsets[v].rank = 0;
}
int e = 0; // 边的索引
int i = 0; // 结果数组的索引
// 从权值最小的边开始遍历
while (i < G->vexnum - 1 && e < numEdges) {
Edge next_edge = edges[e++];
int x = find(subsets, next_edge.start);
int y = find(subsets, next_edge.end);
// 如果加入该边不会形成环，则将其加入结果数组
if (x != y) {
result[i++] = next_edge;
Union(subsets, x, y);
}
}
// 输出最小生成树的边
printf("最小生成树的边:\n");
for (int i = 0; i < G->vexnum - 1; i++) {
printf("(%d, %d) -> %d\n", result[i].start, result[i].end, result[i].weight);
}
}
// 在并查集中查找顶点所属的子集
int find(Subset subsets[], int i) {
if (subsets[i].parent != i)
subsets[i].parent = find(subsets, subsets[i].parent);
return subsets[i].parent;
}
// 合并两个子集
void Union(Subset subsets[], int x, int y) {
int xroot = find(subsets, x);
int yroot = find(subsets, y);
if (subsets[xroot].rank < subsets[yroot].rank)
subsets[xroot].parent = yroot;
else if (subsets[xroot].rank > subsets[yroot].rank)
subsets[yroot].parent = xroot;
else {
subsets[yroot].parent = xroot;
subsets[xroot].rank++;
}
}
// Prim 算法实现
void Prim(MGraph *G) {
int parent[maxvex]; // 存储最小生成树的父节点
int key[maxvex]; // 存储每个顶点到最小生成树的最小权值
int mstSet[maxvex]; // 标记顶点是否已加入最小生成树
// 初始化 key 和 mstSet 数组
for (int i = 0; i < G->vexnum; i++) {
key[i] = INFINITY;
mstSet[i] = 0;
}
// 从顶点 0 开始
key[0] = 0;
parent[0] = -1; // 根节点没有父节点
// 构建最小生成树
while (1) {
int u, min_key = INFINITY;
// 选择 key 值最小的顶点
for (int v = 0; v < G->vexnum; v++) {
if (mstSet[v] == 0 && key[v] < min_key) {
min_key = key[v];
u = v;
}
}
if (min_key == INFINITY) // 如果没有找到合适的顶点，表示所有顶点都已加入最小生成树，退出循环
break;
// 将选中的顶点加入最小生成树
mstSet[u] = 1;
// 更新与 u 相邻的顶点的 key 值
for (int v = 0; v < G->vexnum; v++) {
// 仅当权值不为0且未加入最小生成树时才考虑更新
if (G->arc[u][v] && mstSet[v] == 0 && G->arc[u][v] < key[v]) {
parent[v] = u;
key[v] = G->arc[u][v];
}
}
}
// 输出最小生成树的边
printf("最小生成树的边:\n");
for (int i = 1; i < G->vexnum; i++) { // 注意从1开始
printf("(%d, %d) -> %d\n", parent[i], i, G->arc[i][parent[i]]);
}
}
void printCreateMGraph(MGraph *G, GraphAdjList *G1) {
int i, j;
for (i = 1; i <= G->vexnum; i++)
printf(" V%d", i);
printf("\n\n");
for (i = 1; i <= G->vexnum; i++) {
printf("V%d |", i);
for (j = 1; j <= G->vexnum; j++) {
if ((i == j) || (G->arc[i][j] == 0))
printf(" ∞");
else
printf("%4d", G->arc[i][j]);
}
printf("|\n");
}
}
void menu() {
printf(" 1:创建无向网(用邻接矩阵存储) \n");
printf(" 2:无向网的邻接矩阵的输出 \n");
printf(" 3:利用kruska算法实现最小生成树 \n");
printf(" 4:利用prim算法实现最小生成树 \n");
printf(" 0:结束循环退出 \n");
}
int main() {
MGraph G;
GraphAdjList G1;
int choice;
while (1)
{
menu();
printf("请输入你需要的操作");
scanf("%d", &choice);
switch (choice) {
case 1:
CreateMGraph(&G, &G1);
break;
case 2:
printCreateMGraph(&G, &G1);
break;
case 3:
Kruskal(&G);
break;
case 4:
Prim(&G);
break;
}
system("pause");
}
return 0;
}
