图邻接矩阵存储 最小生成树 prim普里姆算法 C语言实现

MGraph.h

#pragma once#include "Queue.h"#define MaxVertexNum 100typedef char VertexType;typedef int EdgeType;typedef int VRType;typedef struct ArcCell{VRType adj;//对于无向图 用1、0填充 有向图以权值填充}ArcCell, AdjMatrix[MaxVertexNum][MaxVertexNum];typedef struct {VertexType vexs[MaxVertexNum];AdjMatrix edges;int n;//当前图顶点数int e;//当前边数}MGraph;typedef struct {VertexType adjvex;VRType lowcost;}Closedge[MaxVertexNum];bool visited[MaxVertexNum];MGraph* initMGraph();bool DFSTraverseM(MGraph* m);bool DFSM(MGraph* m, int i);bool BFSTraverseM(MGraph* m);bool BFSM(MGraph* m, int i);void miniSpanTree_PRIM(MGraph *m, VertexType u); 

 

MGraph.c

#include "MGraph.h"#include <stdio.h>#include <stdlib.h>#include <string.h>/************************************************************************/ /* 初始化无向带权图*/ /************************************************************************/ MGraph* initMGraph(){MGraph* m = NULL;int i, j, k, n;char v1, v2;m = (MGraph*)malloc(sizeof(MGraph));memset(m->vexs, 0, MaxVertexNum);printf("please input the number of vertex and edges('v,e'): ");scanf("%d,%d", &i, &j);if(i<0 && j<0){printf("error number");return NULL;}m->n = i;m->e = j;printf("please input the vertexs by order:/n");for(i=0; i<m->n; i++){fflush(stdin);scanf("%c", &m->vexs[i]);}for(i=0; i<m->n; i++)for(j=0; j<m->n; j++)m->edges[i][j].adj = 0;for(k=0; k<m->e; k++){printf("please input the edges by order('v1,v2'): ");fflush(stdin);scanf("%c,%c", &v1, &v2);for(i=0; v1!=m->vexs[i]; i++);for(j=0; v2!=m->vexs[j]; j++);{printf("Input the edges' weight: ");fflush(stdin);scanf("%d", &n);m->edges[i][j].adj = n;m->edges[j][i].adj = n;}}return m; }//最小生成树void miniSpanTree_PRIM( MGraph *m, VertexType u ){Closedge closedge; int i, j, k, min = 0, n;if( m == NULL )return;for( k=0; m->vexs[k]!=u && k<m->n; k++ );for( i=0; i<m->n; i++ )if( i != k ){if(m->edges[k][i].adj != 0){closedge[i].adjvex = u;closedge[i].lowcost = m->edges[k][i].adj;}elseclosedge[i].lowcost = 32767;}closedge[k].adjvex = u;closedge[k].lowcost = 0;min = 32767;for( i=0; i<m->n-1; i++ ){for( j=0; j<m->n; j++ )if( closedge[j].lowcost != 0 && closedge[j].lowcost < min && j != k ) //将表横向对应顶点栏的信息更新 如果有更小边{n = j;min = closedge[j].lowcost;}printf( "%c ", m->vexs[n] );closedge[n].lowcost = 0;//表纵向更新严蔚敏P174for( j=0; j<m->n; j++ )if( m->edges[n][j].adj < closedge[j].lowcost && m->edges[n][j].adj != 0 ){closedge[j].adjvex = m->vexs[n];closedge[j].lowcost = m->edges[n][j].adj;}min = 32767;}} 

 

main.cpp

#include "MGraph.h"int main(){MGraph* m = initMGraph();miniSpanTree_PRIM(m, 'a');system("pause");return 0;}