数据结构图之prime算法详解

简介: 数据结构图之prime算法详解

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

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

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

不多说上代码

# include <stdio.h>
# define  m 31715
# define maxs 100
typedef 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;j<t.v1;j++)
         {
             printf("%d ",t.arc[i][j]);
         }
         printf("\n");
     }  
  return t;
}
void prime(tu *t) {
  int tree[t->v1];  //用于存放邻接节点
  int adjest[t->v1]; 
  int lowcost [t->v1];  //用于存放到各边的权值
//初始化
  for (int i = 0; i < t->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 < t->v1; w++) {
    int min, k;min = 32767;//设置初始最小值
    for (int i = 1; i < t->a1; i++) { //进行遍历     找到  lowcost中最小值   来确定  下一个进树的节点
      if (lowcost[i] < min && lowcost[i] > 0) { //     =0   表示已经进树
        min = lowcost[i] ;            //赋值
        k = i;                     //记录i的值  用于后续进树操作和更新lowcost操作
      }
    }
    tree[++cnt] = k;
    lowcost[k] = 0;
    for (int i = 1; i < t->v1; i++) { //为什么从1开始  ?    因为  lowcost数组中第一个数已经在树中  lowcost【0】=0;一定不满足下边if语句
      if ( (lowcost[i]<0 || 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 < t->v1; i++) {
    printf("%d ", tree[i]);
  }
printf("\n");
printf("边的前驱"); 
  for (int i = 0; i < t->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;
}
相关文章
|
4月前
|
算法系列之数据结构-二叉树
树是一种重要的非线性数据结构,广泛应用于各种算法和应用中。本文介绍了树的基本概念、常见类型(如二叉树、满二叉树、完全二叉树、平衡二叉树、B树等)及其在Java中的实现。通过递归方法实现了二叉树的前序、中序、后序和层次遍历,并展示了具体的代码示例和运行结果。掌握树结构有助于提高编程能力,优化算法设计。
98 9
 算法系列之数据结构-二叉树
|
4月前
|
算法系列之数据结构-Huffman树
Huffman树(哈夫曼树)又称最优二叉树,是一种带权路径长度最短的二叉树,常用于信息传输、数据压缩等方面。它的构造基于字符出现的频率,通过将频率较低的字符组合在一起,最终形成一棵树。在Huffman树中,每个叶节点代表一个字符,而每个字符的编码则是从根节点到叶节点的路径所对应的二进制序列。
117 3
 算法系列之数据结构-Huffman树
|
4月前
|
算法系列之数据结构-二叉搜索树
二叉查找树(Binary Search Tree,简称BST)是一种常用的数据结构,它能够高效地进行查找、插入和删除操作。二叉查找树的特点是,对于树中的每个节点,其左子树中的所有节点都小于该节点,而右子树中的所有节点都大于该节点。
107 22
C 408—《数据结构》算法题基础篇—链表(下)
408考研——《数据结构》算法题基础篇之链表(下)。
139 29
C 408—《数据结构》算法题基础篇—链表(上)
408考研——《数据结构》算法题基础篇之链表(上)。
195 25
C 408—《数据结构》算法题基础篇—数组(通俗易懂)
408考研——《数据结构》算法题基础篇之数组。(408算法题的入门)
176 23
探索局域网电脑监控软件:Python算法与数据结构的巧妙结合
在数字化时代,局域网电脑监控软件成为企业管理和IT运维的重要工具,确保数据安全和网络稳定。本文探讨其背后的关键技术——Python中的算法与数据结构,如字典用于高效存储设备信息,以及数据收集、异常检测和聚合算法提升监控效率。通过Python代码示例,展示了如何实现基本监控功能,帮助读者理解其工作原理并激发技术兴趣。
159 20
【C++数据结构——树】二叉树的遍历算法(头歌教学实验平台习题) 【合集】
本任务旨在实现二叉树的遍历,包括先序、中序、后序和层次遍历。首先介绍了二叉树的基本概念与结构定义,并通过C++代码示例展示了如何定义二叉树节点及构建二叉树。接着详细讲解了四种遍历方法的递归实现逻辑,以及层次遍历中队列的应用。最后提供了测试用例和预期输出,确保代码正确性。通过这些内容,帮助读者理解并掌握二叉树遍历的核心思想与实现技巧。
203 2
|
8月前
|
非递归实现后序遍历时,如何避免栈溢出?
后序遍历的递归实现和非递归实现各有优缺点,在实际应用中需要根据具体的问题需求、二叉树的特点以及性能和空间的限制等因素来选择合适的实现方式。
182 58
栈区的非法访问导致的死循环(x64)
这段内容主要分析了一段C语言代码在VS2022中形成死循环的原因,涉及栈区内存布局和数组越界问题。代码中`arr[15]`越界访问,修改了变量`i`的值,导致`for`循环条件始终为真,形成死循环。原因是VS2022栈区从低地址到高地址分配内存,`arr`数组与`i`相邻,`arr[15]`恰好覆盖`i`的地址。而在VS2019中,栈区先分配高地址再分配低地址,因此相同代码表现不同。这说明编译器对栈区内存分配顺序的实现差异会导致程序行为不一致,需避免数组越界以确保代码健壮性。
21 0
栈区的非法访问导致的死循环(x64)

热门文章

最新文章

AI助理
登录插画

登录以查看您的控制台资源

管理云资源
状态一览
快捷访问

你好,我是AI助理

可以解答问题、推荐解决方案等