UC知道谁能帮我画个PRIM算法的流程图
来源：百度知道 编辑：UC知道 时间：2024/07/12 13:49:55
原程序如下#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define MIN 0
#define MAX_V_N 20
typedef enum {DG,DN,UDG,UDN} GraphKind; //DG表示有向图, DN表示有向网, UDG表示无向图, UDN表示无向网
typedef struct ArcNode{
int adj;
char * info;//该弧相关信息的指针
}ArcNode,
AdjMatrix[MAX_V_N][MAX_V_N];//邻接矩阵
typedef struct {
int vexs[MAX_V_N];
AdjMatrix arcs;
int vexnum,arcnum;
GraphKind kind;
}MGraph;
//-------
int LocateVex(int vexs[],int v){ //确定节点v在节点向量中的位置
for(int i=0;i<MAX_V_N;i++)
if(vexs[i]==v)
return i;
printf("不存在这个节点!");
exit(0);
}
bool CreateMarph(MGraph &G){ //bool函数返回ture or false
int IncInfo,v1,v2,weight,i,j,k;
printf("请输入%s的顶点数和弧数，以及各弧是否含有其他信息(0表示不含其它信息)\n","无向网");
scanf("%d%d%d",&G.vexnum,&G.arcnum,&IncInfo);
for(i=0;i<G.vexnum;i++){ //初始化节点向量
G.vexs[i]=i+1;
}
for(i=
#include <stdlib.h>
#include <string.h>
#define MIN 0
#define MAX_V_N 20
typedef enum {DG,DN,UDG,UDN} GraphKind; //DG表示有向图, DN表示有向网, UDG表示无向图, UDN表示无向网
typedef struct ArcNode{
int adj;
char * info;//该弧相关信息的指针
}ArcNode,
AdjMatrix[MAX_V_N][MAX_V_N];//邻接矩阵
typedef struct {
int vexs[MAX_V_N];
AdjMatrix arcs;
int vexnum,arcnum;
GraphKind kind;
}MGraph;
//-------
int LocateVex(int vexs[],int v){ //确定节点v在节点向量中的位置
for(int i=0;i<MAX_V_N;i++)
if(vexs[i]==v)
return i;
printf("不存在这个节点!");
exit(0);
}
bool CreateMarph(MGraph &G){ //bool函数返回ture or false
int IncInfo,v1,v2,weight,i,j,k;
printf("请输入%s的顶点数和弧数，以及各弧是否含有其他信息(0表示不含其它信息)\n","无向网");
scanf("%d%d%d",&G.vexnum,&G.arcnum,&IncInfo);
for(i=0;i<G.vexnum;i++){ //初始化节点向量
G.vexs[i]=i+1;
}
for(i=
对于这种比较高级的算法代码直接看程序会比较蒙，你就光看我的算法流程吧，prim算法用的是贪心算法的思想，即每一步都作出局部的最优解，关于prim算法为什么能用贪心算法的证明，你可以参考《计算机算法设计与分析》这本书。（我反正不想看那么无聊的证明，也看不明白，呵呵）。
定义一个集合v 和 a，其中v是全体节点（总节点数为n）的集合，v初始为空。定义一个记录最小生成数边数的变量c。
1.在v中任选一个节点，并加入到a中。在v中删除该节点。
2.选一个在所有连接v集合和a集合权值最小的边（即一个节点是v的某一个节点，一个是a中的某一个节点）
3。将两个节点连接。将c加1
4.将第3步才在v中节点删除并加入到a中.
5.如果c为n-1则完成最小生成树，否则回到第2步。
明白了没？不明白再问我啊，希望对你有所帮助。