实现prim算法或kruscal算法中的一种最小生成树算法
来源:学生作业帮助网 编辑:作业帮 时间:2024/07/05 21:55:55
![实现prim算法或kruscal算法中的一种最小生成树算法](/uploads/image/z/8553461-5-1.jpg?t=%E5%AE%9E%E7%8E%B0prim%E7%AE%97%E6%B3%95%E6%88%96kruscal%E7%AE%97%E6%B3%95%E4%B8%AD%E7%9A%84%E4%B8%80%E7%A7%8D%E6%9C%80%E5%B0%8F%E7%94%9F%E6%88%90%E6%A0%91%E7%AE%97%E6%B3%95)
实现prim算法或kruscal算法中的一种最小生成树算法
实现prim算法或kruscal算法中的一种最小生成树算法
实现prim算法或kruscal算法中的一种最小生成树算法
Prim算法:
#include
#include
typedef int VRType;
typedef char InfoType;
#define MAX_NAME 3
/*顶点字符串的最大长度+1*/
#define MAX_INFO 20
/*相关信息字符串的最大长度+1*/
typedef char VertexType[MAX_NAME];
#define INFINITY 32767
/*用整型最大值代替无穷大*/
#define MAX_VERTEX_NUM 20
/*最大顶点个数*/
typedef enum{DG,DN,AG,AN} GraphKind;
/*{有向图,有向网,无向图,无向网}*/
typedef int PathMatrix[MAX_VERTEX_NUM][MAX_VERTEX_NUM];
typedef int ShortPathTable[MAX_VERTEX_NUM];
typedef struct
{
VRType adj;
/*顶点关系类型.对无权图,用1(是)或0(否)表示相邻否*/
/*对带全图,则为权值类型*/
InfoType *info;
/*该弧相关信息的指针(可无)*/
}ArcCell,AdjMatrix[MAX_VERTEX_NUM][MAX_VERTEX_NUM];
typedef struct
{
VertexType vexs[MAX_VERTEX_NUM];
/*顶点向量*/
AdjMatrix arcs;
/*邻接矩阵*/
int vexnum,arcnum;
/*图的当前顶点数和弧数*/
GraphKind kind;
/*图的种类标志*/
}MGraph;
int LocateVex(MGraph G,VertexType u)
{ /*初始条件:图G存在,u和G中顶点有相同特征*/
/*操作结果:若G中存在顶点u,则返回该顶点在图中位置;否则返回-1*/
int i;
for(i=0;i