首页 > 其他分享 >c: Kruskal Algorithm

c: Kruskal Algorithm

时间：2023-09-26 15:14:22浏览次数：42  
标签：spanlist Algorithm int Kruskal brief elist edge KruskalGraph

KruskalAlgorithm.h   

/*****************************************************************//**
 * \file   KruskalAlgorithm.h
 * \brief  Kruskal Algorithm克鲁斯卡尔算法
 * IDE: VSCODE   c11  https://github.com/hustcc/JS-Sorting-Algorithm/blob/master/2.selectionSort.md
 * https://www.programiz.com/dsa/counting-sort
 * https://www.geeksforgeeks.org/sorting-algorithms/
 * \author geovindu,Geovin Du 涂聚文
 * \date   2023-09-19
***********************************************************************/

#ifndef KRUSKALALGORITHM_H
#define KRUSKALALGORITHM_H



 
#include <stdio.h>
#include <stdlib.h>



#define MAX 30

typedef struct Kruskaledge {
  int u, v, w;
} Kruskaledge;

typedef struct edge_list {
  Kruskaledge data[MAX];
  int n;
} edge_list;

/**
 * @brief       
 * 
 */
void KruskalAlgo(int KruskalGraph[MAX][MAX],edge_list elist,edge_list spanlist);

/**
 * @brief       
 * 
 * @param       belongs 
 * @param       vertexno 
 * @return      int 
 */
int Kruskalfind(int belongs[], int vertexno);

/**
 * @brief       
 * 
 * @param       belongs 
 * @param       c1 
 * @param       c2 
 */
void KruskalapplyUnion(int belongs[], int c1, int c2);
/**
 * @brief       
 * 
 */
void Kruskalsort(edge_list elist);
/**
 * @brief       
 * 
 */
void Kruskalprint(edge_list spanlist);

/**
 * @brief       
 * 
 */
struct edge {
    //一条边有 2 个顶点
    int initial;
    int end;
    //边的权值
    int weight;
};

/**
 * @brief 图中边的数量      
 * 
 */
#define N 9   // 
/**
 * @brief   图中顶点的数量    
 * 
 */
#define P 6  
/**
 * @brief       构建表示边的结构体
 * 
 */
/** 
 * @brief Kruskal Algorithm
 * @param edge    INT 数组
 * @param edge 搜索的关键数字
 * 
 * @return 返回
 */
void KruskalMinTree(struct edge edges[], struct edge minTree[]);

/**
 * @brief       
 * 
 * @param       minTree 
 */
void KruskalDisplay(struct edge minTree[]);
/**
 * @brief       
 * 
 * @param       a 
 * @param       b 
 * @return      int 
 */
int Kruskalcmp(const void* a, const void* b);

#endif //KRUSKALALGORITHM

　　

KruskalAlgorithm.c 
/**
 * *****************************************************************************
 * @file        KruskalAlgorithm.c
 * @brief       Kruskal Algorithm kruskal算法（克鲁斯卡尔算法）
 * @author       (geovindu,Geovin Du,涂聚文) http://c.biancheng.net/algorithm/kruskal.html
 *                https://www.programiz.com/dsa/kruskal-algorithm
 *                https://www.geeksforgeeks.org/kruskals-minimum-spanning-tree-algorithm-greedy-algo-2/
 * @date        2023-09-26 
 * @copyright   geovindu
 * *****************************************************************************
 */
#include <stdio.h>
#include <stdlib.h>
#include "include/KruskalAlgorithm.h"




int  n=6;

// Applying Krushkal Algo
/**
 * @brief       
 * 
 * @param       KruskalGraph 
 */
void KruskalAlgo(int KruskalGraph[MAX][MAX],edge_list elist,edge_list spanlist) {
  int belongs[MAX], i, j, cno1, cno2;
  elist.n = 0;

  for (i = 1; i < n; i++)
    for (j = 0; j < i; j++) {
      if (KruskalGraph[i][j] != 0) {
        elist.data[elist.n].u = i;
        elist.data[elist.n].v = j;
        elist.data[elist.n].w = KruskalGraph[i][j];
        elist.n++;
      }
    }

  Kruskalsort(elist);

  for (i = 0; i < n; i++)
    belongs[i] = i;

  spanlist.n = 0;

  for (i = 0; i < elist.n; i++) {
    cno1 = Kruskalfind(belongs, elist.data[i].u);
    cno2 = Kruskalfind(belongs, elist.data[i].v);

    if (cno1 != cno2) {
      spanlist.data[spanlist.n] = elist.data[i];
      spanlist.n = spanlist.n + 1;
      KruskalapplyUnion(belongs, cno1, cno2);
    }
  }
  Kruskalprint(spanlist);

}

int Kruskalfind(int belongs[], int vertexno) {
  return (belongs[vertexno]);
}

void KruskalapplyUnion(int belongs[], int c1, int c2) {
  int i;

  for (i = 0; i < n; i++)
    if (belongs[i] == c2)
      belongs[i] = c1;
}

// Sorting algo
/**
 * @brief       
 * 
 */
void Kruskalsort(edge_list elist) {
  int i, j;
  Kruskaledge temp;

  for (i = 1; i < elist.n; i++)
    for (j = 0; j < elist.n - 1; j++)
      if (elist.data[j].w > elist.data[j + 1].w) {
        temp = elist.data[j];
        elist.data[j] = elist.data[j + 1];
        elist.data[j + 1] = temp;
      }
}

// Printing the result
/**
 * @brief       
 * 
 */
void Kruskalprint(edge_list spanlist) {
  int i, cost = 0;

  printf("克鲁斯卡尔算法 Kruskal Algorithm\n");
  for (i = 0; i < spanlist.n; i++) {
    printf("\n%d - %d : %d", spanlist.data[i].u, spanlist.data[i].v, spanlist.data[i].w);
    cost = cost + spanlist.data[i].w;
  }

  printf("\nSpanning tree cost: %d\n", cost);
}


/**
 * @brief qsort排序函数中使用，使edges结构体中的边按照权值大小升序排序      
 * 
 * 
 * @param       a 
 * @param       b 
 * @return      int 
 */
int Kruskalcmp(const void* a, const void* b) {
    return  ((struct edge*)a)->weight - ((struct edge*)b)->weight;
}

/** 
 * @brief Kruskal Algorithm克鲁斯卡尔算法寻找最小生成树，edges 存储用户输入的图的各个边，minTree 用于记录组成最小生成树的各个边
 * @param edge    INT 数组
 * @param edge 搜索的关键数字
 * 
 * @return 返回
 */
void KruskalMinTree(struct edge edges[], struct edge minTree[]) {
    int i, initial, end, elem, k;
    //每个顶点配置一个标记值
    int assists[P];
    int num = 0;
    //初始状态下，每个顶点的标记都不相同
    for (i = 0; i < P; i++) {
        assists[i] = i;
    }
    //根据权值，对所有边进行升序排序
    qsort(edges, N, sizeof(edges[0]), Kruskalcmp);
    //遍历所有的边
    for (i = 0; i < N; i++) {
        //找到当前边的两个顶点在 assists 数组中的位置下标
        initial = edges[i].initial - 1;
        end = edges[i].end - 1;
        //如果顶点位置存在且顶点的标记不同，说明不在一个集合中，不会产生回路
        if (assists[initial] != assists[end]) {
            //记录该边，作为最小生成树的组成部分
            minTree[num] = edges[i];
            //计数+1
            num++;
            elem = assists[end];
            //将新加入生成树的顶点标记全部改为一样的
            for (k = 0; k < P; k++) {
                if (assists[k] == elem) {
                    assists[k] = assists[initial];
                }
            }
            //如果选择的边的数量和顶点数相差1，证明最小生成树已经形成，退出循环
            if (num == P - 1) {
                break;
            }
        }
    }
    KruskalDisplay(minTree);

}
/**
 * @brief       
 * 
 * @param       minTree 
 */
void KruskalDisplay(struct edge minTree[]) {
    int cost = 0, i;
    printf("克鲁斯卡尔算法 Kruskal Algorithm 最小生成树为:\n");
    for (i = 0; i < P - 1; i++) {
        printf("%d-%d  权值：%d\n", minTree[i].initial, minTree[i].end, minTree[i].weight);
        cost += minTree[i].weight;
    }
    printf("总权值为：%d\n", cost);
}

　　

调用：

 //13 kruskal算法   
    printf("\n13.kruskal算法,请输入三个数字一行，输完一个数字时，按一个空格分开：\n");
    int ki;
    struct edge edges[N], minTree[P - 1];
    for (ki = 0; ki < N; ki++) {
        scanf("%d %d %d", &edges[ki].initial, &edges[ki].end, &edges[ki].weight);//每行输入3个数字 输入一个数字时，按空格键
    }
    KruskalMinTree(edges, minTree);  
    //n = 6;
    int KruskalGraph[MAX][MAX];

    KruskalGraph[0][0] = 0;
    KruskalGraph[0][1] = 4;
    KruskalGraph[0][2] = 4;
    KruskalGraph[0][3] = 0;
    KruskalGraph[0][4] = 0;
    KruskalGraph[0][5] = 0;
    KruskalGraph[0][6] = 0;

    KruskalGraph[1][0] = 4;
    KruskalGraph[1][1] = 0;
    KruskalGraph[1][2] = 2;
    KruskalGraph[1][3] = 0;
    KruskalGraph[1][4] = 0;
    KruskalGraph[1][5] = 0;
    KruskalGraph[1][6] = 0;

    KruskalGraph[2][0] = 4;
    KruskalGraph[2][1] = 2;
    KruskalGraph[2][2] = 0;
    KruskalGraph[2][3] = 3;
    KruskalGraph[2][4] = 4;
    KruskalGraph[2][5] = 0;
    KruskalGraph[2][6] = 0;

    KruskalGraph[3][0] = 0;
    KruskalGraph[3][1] = 0;
    KruskalGraph[3][2] = 3;
    KruskalGraph[3][3] = 0;
    KruskalGraph[3][4] = 3;
    KruskalGraph[3][5] = 0;
    KruskalGraph[3][6] = 0;

    KruskalGraph[4][0] = 0;
    KruskalGraph[4][1] = 0;
    KruskalGraph[4][2] = 4;
    KruskalGraph[4][3] = 3;
    KruskalGraph[4][4] = 0;
    KruskalGraph[4][5] = 0;
    KruskalGraph[4][6] = 0;

    KruskalGraph[5][0] = 0;
    KruskalGraph[5][1] = 0;
    KruskalGraph[5][2] = 2;
    KruskalGraph[5][3] = 0;
    KruskalGraph[5][4] = 3;
    KruskalGraph[5][5] = 0;
    KruskalGraph[5][6] = 0;
    edge_list spanlist;
    edge_list elist;
    KruskalAlgo(KruskalGraph,spanlist,spanlist);

　　

输出：

 

 

标签：spanlist,Algorithm,int,Kruskal,brief,elist,edge,KruskalGraph
From： https://www.cnblogs.com/geovindu/p/17730114.html

相关文章

  • python: Sorting Algorithms
     #encoding:utf-8#版权所有2023涂聚文有限公司#许可信息查看：PythonSortingAlgorithms#描述：*https://www.programiz.com/dsa/counting-sort#*https://www.geeksforgeeks.org/sorting-algorithms/#Author:geovindu,GeovinDu涂聚文.#IDE:PyC......
  • python: Essential Algorithms
     #encoding:utf-8#版权所有2023涂聚文有限公司#许可信息查看：#描述：#Author:geovindu,GeovinDu涂聚文.#IDE:PyCharm2023.1python311#Datetime:2023/9/2121:28#User:geovindu#Product:PyCharm#Project:EssentialAlgor......
  • c: Sorting Algorithms
    SortAlgorithm.h /*****************************************************************//***\fileSortAlgorithm.h*\brief业务操作方法*VSCODEc11https://github.com/hustcc/JS-Sorting-Algorithm/blob/master/2.selectionSort.md*https://www.progra......
  • 论文阅读： Co-design Hardware and Algorithm for Vector Search
    1.Introduction介绍一下论文背景，向量检索常用于搜索引擎，推荐系统，LLM和科学计算等对应的常用的硬件向量检索方法，IVF-PQ其中IVF：将多个向量聚类,PQ将向量压缩而为了最大化IVF-PQ的效果，也会面临很多的挑战在芯片设计的过程中，会遇到针对六个阶段如何设计合适的微架构？如何将有......
  • Kruskal重构树 学习笔记
    Kruskal重构树最大生成树将部分内容倒置即可回顾：Kruskal基本信息求解最小生成树时间复杂度：\(O(m\logm)\)更适合稀疏图算法思想按照边权从小到大排序依次枚举每一条边，如果这一条边两侧不连通，则加入这条边代码点击查看代码#include<bits/stdc++.h>#define......
  • Proj. CRR Paper Reading: Optimal Speedup of Las Vegas Algorithms, Adaptive resta
    TitleAdaptiverestartforstochasticsynthesisPLDI2021TaskDistributethepowerbetweenmultiplerunsinstochasticprogramsynthesistoaccelerateHere,astochasticprogramsynthesisprogramcanbesummarizedasfollows:Givenasetof<input,ou......
  • 解决npm ERR! Cannot read properties of null (reading ‘pickAlgorithm‘)报错问题
    转载自：https://www.cnblogs.com/zhyp/p/16920380.html=========解决方法：在终端中运行命令：npmcacheclear--force然后重新运行npmi命令，再次安装安装完成，没有出现报错npmrunserve运行项目，项目可以正常启动了。  安装vueCLI失败后，百度得知在终端执行命令：npmcleanc......
  • Data structure and algorithm-Two
    B树                扩容           找出不含重复字符的最长字串的长度 字母异位词分组   优化用一个长度26的整数数组来标识 ArrayKey的构造方法   判断是否存在重复元素 ......
  • 【MySQL 8.0】新特性：ALTER TABLE … ALGORITHM=INSTANT
    MySQL8.0.29之前，在线DDL操作中即时添加列只能添加在表的最后一列MySQL8.0.29扩展了对ALTERTABLE…ALGORITHM=INSTANT的支持：用户可以在表的任何位置即时添加列、即时删除列、添加列时评估行大小限制(root@node01)>altertablecustomeraddcolumnc_commentvarcha......
  • Kruskal重构树小记
    模拟赛考了，简单贺一下oi-wiki引入定义在跑\(\rmKruskal\)的过程中我们会从小到大加入若干条边。现在我们仍然按照这个顺序。首先新建\(n\)个集合，每个集合恰有一个节点，点权为\(0\)。每一次加边会合并两个集合，我们可以新建一个点，点权为加入边的边权，同时将两个集合的根节......

赞助商

阅读排行

网站主页关于我们联系我们网站地图

本网站内容转载自其他媒体，侵权联系[admin##ips99.com]。

Copyright © 2020-2023 IPS99 版权所有 IPS99