普里姆算法_最小代价生成树_邻接矩阵表示法

news/2024/7/20 20:24:20 标签: 算法, 图论, 深度优先

基本思想：
最小生成树问题的概念—普里姆算法是从点的角度来解决。若在解决问题过程中需要遍历图的所有点，则普里姆算法更好。
普里姆算法更像构建一棵树。联想我们构建二叉树的过程，从根节点出发，构建左右子树，再以左右子树为根节点，构建它们的左右子树。普里姆算法设一个点集V，初始时只有源点，从点集的点出发遍历所有以它们为起点的边，找到其中权值最小的边，且这条边的终点不在点集V中，然后将终点加入点集，再从点集V中的所有点出发，找一条权重最小的边。从点集中的点向外发散，构建起最小生成树。
在这里插入图片描述
在这里插入图片描述
在这里插入图片描述
该算法事件关键步骤数为
(n+n^2)*n/2 n为图中的结点数量
事件复杂度为O(n^3)

#include<stdio.h>
#include<stdlib.h>
#define MaxVertices 100
#define MaxNum 100
#define TRUE 1
#define FALSE 0
typedef struct graph {
	int NoEdge;
	int Vertices;
	int** A;
}Graph;
void CreateGraph(Graph* g, int n, int noedge) {
	int i, j;
	g->NoEdge = noedge;
	g->Vertices = n;
	g->A = (int**)malloc(n * sizeof(int*));
	for (i = 0; i < n; i++) {
		g->A[i] = (int*)malloc(n * sizeof(sizeof(int)));
		for (j = 0; j < n; j++) {
			g->A[i][j] = noedge;
		}
		g->A[i][i] = 0;
	}
}
void Add(Graph* g, int u, int v, int w) {
	if (u < 0 || v < 0 || u > g->Vertices - 1 || v>g->Vertices - 1 || u == v || g->A[u][v] != g->NoEdge) {
		printf("BadInput\n");
	}
	else {
		g->A[u][v] = w;
	}
}
void Delete(Graph* g, int u, int v) {
	if (u < 0 || v < 0 || u > g->Vertices - 1 || v>g->Vertices - 1 || u == v || g->A[u][v] == g->NoEdge) {
		printf("BadInput\n");
	}
	else {
		g->A[u][v] = g->NoEdge;
		printf("Delete Successfully\n");
	}
}
void Exist(Graph* g, int u, int v) {
	if (u < 0 || v < 0 || u > g->Vertices - 1 || v>g->Vertices - 1 || u == v || g->A[u][v] == g->NoEdge) {
		printf("No Existance\n");
	}
	else {
		printf("Element Exists!\n");
	}
}
void Prim(Graph* g) {
	int i,b, c, v, 
		n = g->Vertices,  count = -1,
		* gatheredTreeNodes,
		tempEnd, tempStart, tempMinW,
		* currentMinCostList, * currentEndList, * currentStartList,
		* endNodesList , * minCostList,  * startNodesList, stopWhile;
	int mark[MaxVertices];

	endNodesList = (int*)malloc(n * sizeof(int));
	minCostList = (int*)malloc(n * sizeof(int));
	startNodesList = (int*)malloc(n * sizeof(int));
	gatheredTreeNodes = (int*)malloc(n * sizeof(int));
	currentMinCostList = (int*)malloc(n * sizeof(int));
	currentEndList = (int*)malloc(n * sizeof(int));
	currentStartList = (int*)malloc(n * sizeof(int));
	
	for (i = 0; i < n; i++) {
		startNodesList[i] = -1;
		endNodesList[i] = -1;
		mark[i] = FALSE;
		minCostList[i] = MaxNum;
	}
	mark[0] = TRUE;
	minCostList[0] = 0; endNodesList[0] = 0; startNodesList[0] = 0;
	count++;
	gatheredTreeNodes[count] = 0;
	while (1) {
		stopWhile = TRUE;
		for (i = 0; i < n; i++)
		{
			if (mark[i] == FALSE)
			{
				stopWhile = FALSE;
			}
		}
		if (stopWhile == TRUE) {
			break;
		}
		tempMinW = 10000;
		for (c = 0; c <= count; c++) {
			for (v = 0; v < n; v++) {
				if (g->A[gatheredTreeNodes[c]][v] != 0 
					&& g->A[gatheredTreeNodes[c]][v] != g->NoEdge 
					&& mark[v] == FALSE) {
					if (g->A[gatheredTreeNodes[c]][v] < tempMinW)
					{
						tempMinW = g->A[gatheredTreeNodes[c]][v];
						tempEnd = v;
						tempStart = gatheredTreeNodes[c];
					}
				}
			}
			if (tempMinW != 10000) {
				currentMinCostList[c] = tempMinW;
				currentEndList[c] = tempEnd;
				currentStartList[c] = tempStart;
				tempMinW = 10000;
			}
			else {
				currentMinCostList[c] = tempMinW;
			}
		}
		tempMinW = currentMinCostList[0];
		tempEnd = currentEndList[0];
		tempStart = currentStartList[0];
		for (c = 0; c <= count; c++) {
			if (currentMinCostList[c] < tempMinW) {
				tempMinW = currentMinCostList[c];
				tempEnd = currentEndList[c];
				tempStart = currentStartList[c];
			}
		}
		if (tempMinW == 10000) {
			break;
		}
		endNodesList[tempEnd] = tempEnd;
		minCostList[tempEnd] = tempMinW;
		startNodesList[tempEnd] = tempStart;
		count++;
		gatheredTreeNodes[count] = tempEnd;
		mark[tempEnd] = TRUE;
	}
	for (b = 1; b < n; b++) {
		printf("%-6d %-6d%-6d\n", startNodesList[b], minCostList[b], endNodesList[b]);
	}
}
void PrintMatrix(Graph* g) {
	int i, j;
	for (i = 0; i < g->Vertices; i++) {
		for (j = 0; j < g->Vertices; j++) {
			printf("%-4d", g->A[i][j]);
		}
		printf("\n");
	}
	printf("***************\n");
}
void main() {
	Graph* g;
	g = (Graph*)malloc(sizeof(Graph));
	CreateGraph(g, 6, -1);
	PrintMatrix(g);
	/*Add(g, 0, 2, 7);
	Add(g, 0, 4, 7);
	Add(g, 1, 2, 5);
	Add(g, 1, 5, 6);
	Add(g, 2, 0, 7);
	Add(g, 2, 1, 5);
	Add(g, 2, 3, 1);
	Add(g, 2, 5, 2);
	Add(g, 3, 2, 1);
	Add(g, 3, 5, 2);
	Add(g, 4, 0, 9);
	Add(g, 4, 5, 1);
	Add(g, 5, 1, 6);
	Add(g, 5, 2, 2);
	Add(g, 5, 3, 2);
	Add(g, 5, 4, 1);*/
	//Delete(g, 1, 0);
	Add(g, 0, 3, 5);
	Add(g, 0, 2, 1);
	Add(g, 0, 1, 6);
	Add(g, 1, 4, 3);
	Add(g, 1, 2, 5);
	Add(g, 1, 0, 6);
	Add(g, 2, 4, 6);
	Add(g, 2, 3, 5);
	Add(g, 2, 1, 5);
	Add(g, 2, 5, 4);
	Add(g, 2, 0, 1);
	Add(g, 3, 2, 5);
	Add(g, 3, 0, 5);
	Add(g, 3, 5, 2);
	Add(g, 4, 5, 6);
	Add(g, 4, 2, 6);
	Add(g, 4, 1, 3);
	Add(g, 5, 4, 6);
	Add(g, 5, 2, 4);
	Add(g, 5, 3, 2);
	PrintMatrix(g);
	Prim(g);
}

0 -1 -1 -1 -1 -1
-1 0 -1 -1 -1 -1
-1 -1 0 -1 -1 -1
-1 -1 -1 0 -1 -1
-1 -1 -1 -1 0 -1
-1 -1 -1 -1 -1 0

0 6 1 5 -1 -1
6 0 5 -1 3 -1
1 5 0 5 6 4
5 -1 5 0 -1 2
-1 3 6 -1 0 6
-1 -1 4 2 6 0

2 5 1
0 1 2
5 2 3
1 3 4
2 4 5

C:\C程序&C语言数据结构\C语言数据结构_从入门到入坑\10\邻接矩阵实现Prim算法\Debug\邻接矩阵实现Prim算法.exe (进程 9000)已退出，代码为 0。
要在调试停止时自动关闭控制台，请启用“工具”->“选项”->“调试”->“调试停止时自动关闭控制台”。
按任意键关闭此窗口. . .


http://www.niftyadmin.cn/n/1365098.html

相关文章

C与C++

C与C++

很多朋友对于C和C的区别不是很清楚&#xff0c;以至于经常弄混。我在刚开始接触的时候也对这两种语言的区别了解的不是很多。后来慢慢的学习&#xff0c;总结出几点这二者的区别&#xff0c;跟大家分享一下。 c在c的基础上增添类&#xff0c;还有C是一个结构化语言&#xff0c;…
阅读更多...
xcode4的自动完成功能(Code sense or Code Snippet)

xcode4的自动完成功能(Code sense or Code Snippet)

所谓自动完成功能就是自动完成喽。真是废话&#xff0c;哈哈&#xff01;自动完成包括两种含义吧&#xff0c;一种是输入字母的时候可以动态弹出一个列表&#xff0c;然后通过选择&#xff0c;提高输入效率&#xff0c;这种好像叫代码提示(Code sense?);另一种就是输入几个字母…
阅读更多...
Apache 服务器的配置

Apache 服务器的配置

Apache 服务器的配置 LoadModule php5_module "E:..." 让服务器知道php的根目录 phpIniDir "E:/PHP" 让服务器知道php配置文件的目录 DocumentRoot "E:/phpweb" 网页使用的php文…
阅读更多...
最短路径-迪杰斯特拉算法-单源最短路径

最短路径-迪杰斯特拉算法-单源最短路径

时间复杂度为 O(n^2) #include<stdio.h> #include<stdlib.h> #define BOOL int #define TRUE 1 #define FALSE 0 #define T int #define SIZE 6 #define MAXNUMBER 99 typedef struct graph {int NoEdge;int Vertices;int** A; }Graph; void CreateGraph(Graph* g…
阅读更多...
C++的虚函数与多态

C++的虚函数与多态

C中的虚函数的作用主要是实现了多态的机制。关于多态&#xff0c;简而言之就是用父类型别的指针指向其子类的实例&#xff0c;然后通过父类的指针调用实际子类的成员函数。这种技术可以让父类的指针有“多种形态”&#xff0c;这是一种泛型技术。所谓泛型技术&#xff0c;说白了…
阅读更多...
最短路径-弗洛伊德算法-所有顶点之间的最短路径

最短路径-弗洛伊德算法-所有顶点之间的最短路径

#include<stdio.h> #include<stdlib.h> #define BOOL int #define TRUE 1 #define FALSE 0 #define T int #define SIZE 4 //指示途中结点数量 #define MAXNUMBER 99 typedef struct graph {int NoEdge;int Vertices;int** A; }Graph; void CreateGraph(Graph* g…
阅读更多...
CSS 架构

CSS 架构

存档&#xff0c;已备学习。原文路径&#xff1a;http://www.admin10000.com/document/1229.html 英文原文&#xff1a;http://engineering.appfolio.com/2012/11/16/css-architecture/ Philip Walton 在AppFolio担任前端工程师&#xff0c;他在Santa Barbara on Rails的聚会上…
阅读更多...
邻接表有向图是否包含回路

邻接表有向图是否包含回路

//我在这里其实是找不到有几条回路的&#xff0c;这个函数只能判断图里面有没有回路。下面的那个找出几条回路的是不完善的。如果你能完善这些功能&#xff0c;请在评论区给出你的答案&#xff0c;谢谢 #include<stdio.h> #include<stdlib.h> //int target0; //相…
阅读更多...
最新文章

Copyright @ 2022~2023