从零开始学数据结构系列之第四章《prim算法（普里姆算法）总代码》

标签：index prim weight min int MAX edge 算法从零开始

文章目录

回顾
初始化
寻找最小权值
算法主体
总代码
往期回顾

回顾

我们用这张图来进行算法讲解
在这里插入图片描述

初始化

/*
* vex  - 存储顶点
* weight - 存储权值
*/
typedef struct Edge {
    char vex;
    int weight;
}Edge;

/*
* 开辟数组大小得空间，大小具体为 vexNum 的个数
* 同时将 vex 初始化赋值同G->vexs 一样，这里的vex全都是一样的值，等后续进行更新
* weight的值为index行的那一列二维数组的值
* 按总代码来讲，如果传入值为 index= 0， 则 T[i].weight初始化成0, 6, 1, 5, MAX, MAX这一关于顶点“1”的所有边的权值
如果传入值为 index= 1， 则 T[i].weight初始化成6, 0, 5, MAX, 3, MAX,这一关于顶点“2”的所有边的权值，以此类推
*
* 总的来说初始化同时将传入进来的顶点也初始化了
*/

Edge* initEdeg(Graph* G, int index) 
{
	int i=0;
	Edge *T   =	(Edge*)malloc(sizeof(Edge) * G->vexNum);
	for(i=0;i<G->vexNum;i++)
	{
		T[i].vex = G->vexs[index];
		T[i].weight = G->arcs[index][i];
	}
	return T;
}

寻找最小权值

/*
*	我们规定，如果他的weight为0时，说明他已经访问过了这个节点/或者是他本身了
*	同时不断找到最小值并且逐步开始更新min的值，知道找到这一顶点这一条边的最小权值
*/

int getMinEdge(Edge* edge, Graph* G)
{
	int min = MAX;
	int i=0;
	int index=0;
	for(i=0;i<G->vexNum;i++)
	{
		if(edge[i].weight && edge[i].weight < min)
		{		
			min = edge[i].weight;
			index = i;
		}
	}
	return index;
}

算法主体

/*
*	初始化顶点的值，所以我们在循环的时候就要G->vexNum-1。这里减去的就是顶点的值
*	循环获取最小值，同时获取完最小值以后，将该点的权值赋值为0，代表已经寻找过了这个节点了
*	寻找完最小值（最小权值以后）我们就要重新将的内容进行一个更新，同时将他的边/权值替换为寻找到最小值的那个顶点后的那些边，同时小于他的权值都要更新他的vex值，所以这就是为什么他可以有类似于“回归节点再去寻找”的类似方法,他并不会把所有遍历的节点都给存储进去
*/

void prim(Graph* G, int index) 
{
	int i=0,j=0;
	Edge *edge = initEdeg(G,index);
	int min = 0;

	for(i=0;i<G->vexNum-1;i++)
	{
		min = getMinEdge(edge,G);
		printf("v%c --> v%c, weight = %d\n", edge[min].vex, G -> vexs[min], edge[min].weight);
		edge[min].weight = 0;
		for(j=0;j<G->vexNum;j++)
		{
			if(edge[j].weight > G->arcs[min][j] && edge[j].weight)
			{
				edge[j].weight = G->arcs[min][j];
				edge[j].vex = G->vexs[min];
			}
		}
		
	}
}

总代码

在这里插入图片描述

#include <stdio.h>
#include <stdlib.h>

/**
 * 图顶点之前不通，那么邻接矩阵的值为MAX
 * 如果顶点是自己本身，那么值为0
 */
#define MAX 32767

typedef struct Graph {
    char* vexs;
    int** arcs;
    int vexNum;
    int arcNum;
}Graph;

typedef struct Edge {
    char vex;
    int weight;
}Edge;

/**
 * 当edge.weight = 0时，代表顶点加入到U集合中
 */ 
Edge* initEdeg(Graph* G, int index) 
{
	int i=0;
	Edge *T   =	(Edge*)malloc(sizeof(Edge) * G->vexNum);
	for(i=0;i<G->vexNum;i++)
	{
		T[i].vex = G->vexs[index];
		T[i].weight = G->arcs[index][i];
		//printf("T[i].vex->%c, T[i].weight->%d\r\n", T[i].vex,T[i].weight);

	}
	
	return T;
}

int getMinEdge(Edge* edge, Graph* G)
{
	int min = MAX;
	int i=0;
	int index=0;
	for(i=0;i<G->vexNum;i++)
	{
		if(edge[i].weight && edge[i].weight < min)
		{		
			min = edge[i].weight;
			index = i;
		}
	}
	return index;
}

void prim(Graph* G, int index) 
{
	int i=0,j=0;
	Edge *edge = initEdeg(G,index);
	int min = 0;

	for(i=0;i<G->vexNum-1;i++)
	{
		min = getMinEdge(edge,G);
		
		printf("v%c --> v%c, weight = %d\n", edge[min].vex, G -> vexs[min], edge[min].weight);
		edge[min].weight = 0;
		for(j=0;j<G->vexNum;j++)
		{
			if(edge[j].weight > G->arcs[min][j] && edge[j].weight)
			{
				edge[j].weight = G->arcs[min][j];
				edge[j].vex = G->vexs[min];
			}
		}
		
	}
} 

Graph* initGraph(int vexNum) 
{
	int i = 0;
    Graph* G = (Graph*)malloc(sizeof(Graph));
    G -> vexs = (char*)malloc(sizeof(char) * vexNum);
    G -> arcs = (int**)malloc(sizeof(int*) * vexNum);
    for (i = 0 ; i < vexNum; i++) {
        G -> arcs[i] = (int*)malloc(sizeof(int) * vexNum);
    }
    G -> vexNum = vexNum;
    G -> arcNum = 0;
    return G;
}

void createGraph(Graph* G, char* vexs, int* arcs) 
{
	int i=0,j=0;

    for (i = 0 ; i < G -> vexNum; i++) 
	{
        G -> vexs[i] = vexs[i];
        for (j = 0; j < G -> vexNum; j++) 
		{
            G -> arcs[i][j] = *(arcs + i * G -> vexNum + j);
            if (G -> arcs[i][j] != 0 && G -> arcs[i][j] != MAX)  
                G -> arcNum ++;
        }
    }
    G -> arcNum /= 2;
}

void DFS(Graph* G, int* visited, int index) 
{
	int i=0;
    printf("%c\t", G -> vexs[index]);
    visited[index] = 1;
    for (i = 0; i < G ->vexNum; i++) 
	{
        if (G -> arcs[index][i] > 0 && G -> arcs[index][i] != MAX && !visited[i]) 
		{
            DFS(G, visited, i);
        }
    }
}

int main() 
{
	int i=0;
	int arcs[6][6] = {
        0, 6, 1, 5, MAX, MAX,
        6, 0, 5, MAX, 3, MAX,
        1, 5, 0, 5, 6, 4,
        5, MAX, 5, 0, MAX, 2,
        MAX, 3, 6, MAX, 0, 6,
        MAX, MAX, 4, 2, 6, 0
    };
	Graph* G = initGraph(6);
	int* visited = (int*)malloc(sizeof(int) * G -> vexNum);
    
    
    for (i = 0; i < G -> vexNum; i++)
        visited[i] = 0;
    
    createGraph(G, "123456", (int*)arcs);
    DFS(G, visited, 0);
    printf("\n");
    prim(G, 0);
    return 0;
}

最后树得出来的样式图
在这里插入图片描述

往期回顾

标签：index,prim,weight,min,int,MAX,edge,算法,从零开始
From： https://blog.csdn.net/qq_62548908/article/details/140615641

从零开始学数据结构系列之第四章《prim算法（普里姆算法）总代码》

文章目录

回顾

初始化

寻找最小权值

算法主体

总代码

往期回顾

相关文章

赞助商

阅读排行