数据结构图之prime算法详解

本篇为文章是写的prime算法，本人见书上算法只有伪代码于是想着写出一个能跑的prime算法

本人写了一个下午的prime算法，但是运行的结果是不正确的 （本人是个小菜鸡） 经过朋友的帮助，运行结果正确。

我觉得算法主要先理解思想   在去试图打出分部的伪代码 最后打出能跑的代码

不多说上代码

# include # define  m 31715# define maxs 100typedef struct {int v[maxs];  // 顶点表int arc[maxs][maxs];//边表int v1, a1, w;      //顶点数  和边数  权数} tu;int getid(tu t, int i) {for (int j = 0; j < t.v1; j++) {if (i == t.v[j])return j;}return -1;}tu creat (tu t) {printf("请输入定点数和边数");//输入顶点数    边数scanf("%d", &(t.v1));//printf("进行到这了");scanf("%d", &(t.a1));for (int i = 0; i < t.v1; i++) { //初始化  顶点表printf("请输入顶点");scanf("%d", &t.v[i]);}printf("请输入边的权值");for (int i = 0; i < t.v1; i++) {for (int j = 0; j < t.v1; j++) {scanf("%d", &t.arc[i][j]);t.arc[j][i] = t.arc[i][j];}} for(int i=0;i<t.v1;i++)     {  for(int j=0;jv1];  //用于存放邻接节点int adjest[t->v1]; int lowcost [t->v1];  //用于存放到各边的权值//初始化for (int i = 0; i v1; i++) {lowcost[i] = t->arc[0][i];  //    先按以0为起点   到各边的权值adjest[i]=0;tree[i] = 0; //表示  各边均以 0  为起点}//寻找   lowcost中最小值//要遍历    int cnt=0;for (int w = 1; w v1; w++) {int min, k;min = 32767;//设置初始最小值for (int i = 1; i a1; i++) { //进行遍历     找到  lowcost中最小值   来确定  下一个进树的节点if (lowcost[i]  0) { //     =0   表示已经进树min = lowcost[i] ;//赋值k = i;    //记录i的值  用于后续进树操作和更新lowcost操作}}tree[++cnt] = k;lowcost[k] = 0;for (int i = 1; i v1; i++) { //为什么从1开始  ？    因为  lowcost数组中第一个数已经在树中  lowcost【0】=0；一定不满足下边if语句if ( (lowcost[i] t->arc[k][i] )&& t->arc[k][i] >= 0) {lowcost[i] = t->arc[k][i]; //   当满足if语句时    说明lowcost需要更新  把二维数组中的k行i列数据进行赋值      //表示这条边的起点为  k//printf("here");adjest[i]=k;}}}printf("入树的顺序");for (int i = 0; i v1; i++) {printf("%d ", tree[i]);}printf("\n");printf("边的前驱"); for (int i = 0; i v1; i++) {printf("%d ", adjest[i]);}}int main() {tu  t;t = creat(t);prime(&t);/*prime    算法 建立 lowcost  数组用于存放最小生成树的邻接边 如果两条边都指向同一个顶点    则 把最小的存入   lowcost设置最小值   min   =312715 比min小  则会进行  赋值 用for循环   进行全部比较 最后保留的是   最小权的下标和权值  下标的   lowcost    为0   则表示进树  则   lowcost会更新  如果   新进入树的节点的二维数组 中 第i个值   比lotcost   中第i个值   小则赋值  tree[i]=k;k  是    进入树的节点的下标  输出tree*/return 0;}

开发者涨薪指南 48位大咖的思考法则、工作方式、逻辑体系