博客

实现内容:

①无向网的数组表示法储存实现

②普利姆算法

数组表示法：分两部分，一个顶点数组，一个邻接矩阵

两结点间没有连接 用MAX_INT表实

测试图：



PS：网的内容从文本文档Prim.txt中读取 文档内容如下



运行截图：

/*
	实现内容:
	①无向网的数组表示法储存实现
	②普利姆算法
	数组表示法：分两部分，一个顶点数组，一个邻接矩阵
				两结点间没有连接 用MAX_INT表实
	VS2019编译通过  2020.7.31
*/
#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include <stdlib.h>
#include <ctype.h>
#include <memory.h>

#define ALGraphType char
#define Max_Vertices 100

typedef enum GRAKIND { DG, UG, DN, UN } GraKind;

//图的顶点定义
typedef struct VNODE {
	ALGraphType Date;

}VNode;

typedef struct ALGRAPH {
	VNode* Vertices;
	int Vexnum, Arcnum; //顶点数目、边的数目
	int** Arc_Matrix;
	GraKind Kind;

}ALGraph;

//普利姆算法中结构数组的结点
typedef struct PRIME_CLOSEDGE {
	int AdjVex;
	int Weight;
}Prime_Closedge;

//根据顶点信息，找到顶点在顺序存储的位置(默认顶点按照字母顺序编号)
int Locate(ALGraphType ch) {
	return toupper(ch) - 'A';
}

//创建图
void Creat_ALGraph(ALGraph* G) {

	if (NULL == G)
		return;

	//从文件中读取数据
	FILE* fp = fopen("C:\\Users\\86132\\Desktop\\第十周周末程序设计\\普利姆算法(邻接矩阵表示法)\\Prim.txt", "r");


	fscanf(fp, "%d", &G->Vexnum);
	G->Vertices = (VNode*)malloc(sizeof(VNode) * G->Vexnum);
	
	fscanf(fp, "%d", &G->Arcnum);
	G->Arc_Matrix = (int**)malloc(sizeof(int*) * G->Vexnum);

	//初始化邻接矩阵
	for (int i = 0; i < G->Vexnum; i++) {
		G->Arc_Matrix[i] = (int*)malloc(sizeof(int) * G->Vexnum);

		//初始赋值MAX_INT
		for (int j = 0; j < G->Vexnum; j++)
			G->Arc_Matrix[i][j] = INT_MAX;
	}

	//录入顶点信息
	for (int i = 0; i < G->Vexnum; i++) {
	
		//空格作用为不读回车
		fscanf(fp," %c", &G->Vertices[i].Date);

	}

	//录入每个边的信息(默认顶点按照ABCD编号)
	for (int i = 0; i < G->Arcnum; i++) {

		char ch1, ch2;
		int n;
		
		空格作用为不读回车
		fscanf(fp," %c %c%d", &ch1, &ch2, &n);

		//更新邻接矩阵
		ch1 = Locate(ch1);
		ch2 = Locate(ch2);

		G->Arc_Matrix[ch1][ch2] = G->Arc_Matrix[ch2][ch1] = n;
	}
	fclose(fp);
}

//获得已经算出的顶点数目
int Get_Vex_Num(Prime_Closedge* P, int n) {

	int m = 0;
	for (int i = 0; i < n; i++)
		if (0 == P[i].Weight)
			m++;

	return m;
}

//普里姆算法 输出树G从元素为ch顶点开始的最小生成树的边
void Mini_Span_Tree_Prim(ALGraph G) {

	ALGraphType ch;
	printf("请输入开始顶点的元素：");

	ch = getchar();

	ch = Locate(ch);
	Prime_Closedge* P = (Prime_Closedge*)malloc(sizeof(Prime_Closedge) * G.Vexnum);

	//初始化P
	for (int i = 0; i < G.Vexnum; i++) {

		if (i == ch) {
			P[i].Weight = 0;
			continue;
		}
		P[i].AdjVex = ch;
		P[i].Weight = G.Arc_Matrix[ch][i];
	}

	//外层循环为边的数目
	for (int i = 0; i < G.Vexnum - 1; i++) {

		//记录进入U集合的顶点的位置
		int pos = 0;

		//更新P

		//有几个顶点就比较几次权重 
		for (int j = Get_Vex_Num(P, G.Vexnum); j > 0; j--) {

			//寻找pos后面第一个U集合顶点的位置
			while (0 != P[pos].Weight)
				pos++;

			//每次比较需要让pos顶点和剩下的所有顶点的权重比
			for (int k = 0; k < G.Vexnum; k++) {
				if (P[k].Weight > G.Arc_Matrix[pos][k]) {
					P[k].Weight = G.Arc_Matrix[pos][k];
					P[k].AdjVex = pos;
				}
			}
			pos++;
		}//Closedge数组更新完毕

		//寻找最小权
		int tmp = INT_MAX, minpos[2] = { 0 };
		for (int j = 0; j < G.Vexnum; j++) {

			if (0 != P[j].Weight && tmp > P[j].Weight) {
				tmp = P[j].Weight;
				minpos[0] = P[j].AdjVex;
				minpos[1] = j;
			}
		}
		printf("第%d条边依附的顶点为%c %c 权重为%d \n", i + 1, G.Vertices[minpos[0]].Date, G.Vertices[minpos[1]].Date, tmp);
		P[minpos[1]].Weight = 0;
	}
}

int main() {

	ALGraph G;
	Creat_ALGraph(&G);
	Mini_Span_Tree_Prim(G);

	return 0;
}