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

基本思想：
最小生成树问题的概念—普里姆算法是从点的角度来解决。若在解决问题过程中需要遍历图的所有点，则普里姆算法更好。
普里姆算法更像构建一棵树。联想我们构建二叉树的过程，从根节点出发，构建左右子树，再以左右子树为根节点，构建它们的左右子树。普里姆算法设一个点集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。
要在调试停止时自动关闭控制台，请启用“工具”->“选项”->“调试”->“调试停止时自动关闭控制台”。
按任意键关闭此窗口. . .

这篇好文章是转载于：学新通技术网