高级数据结构实验(Kruskal算法)C语言实现_kruskal算法代码c语言实现-程序员宅基地

技术标签: 算法  c语言  数据结构  

高级数据结构实验(Kruskal算法)C语言实现

实验目的:

1.掌握并查集的合并优化和查询优化
2.掌握Kruskal算法
3.能够针对实际问题,能够正确选择贪心策略
4.能够针对选择的贪心策略,证明算法的正确性
5.能够正确分析算法的时间复杂度和空间复杂度

实验内容:

采用Kruskal算法生成最小生成树,并采用并查集的合并优化和查询优化。

实验思路:

使用Kruskal算法解决稀疏图解决最小生成树问题效率较高,并使用并查集这种数据结构实现了isConnected()和unionElements()两种功能进行了路径压缩的功能,降低了代码的时间复杂度,提高了代码的运行速率。

实验心得:

在编写此程序时,我们必须非常熟悉Kruskal算法。 Kruskal算法总共选择n-1个边。 使用的贪婪标准是:选择一条成本最低的边线,该边线不会从其余边线生成循环,并将其添加到所选边线集合中。 然后根据该算法与C 语言一起练习出来,程序又长又复杂,需要更多的接触算法,以后的时间也有更多的练习

实现的过程:


#include<stdio.h>

#include<stdlib.h>

#include<stdbool.h>

#define MAXSIZE 100

typedef int Weight;

typedef char Datatype;

typedef struct AdjVNode{
    

Weight weight;

int adjv;

struct AdjVNode *Next;

}*PtrToAdjVNode;

typedef struct Vnode{
    

Datatype data;

PtrToAdjVNode FirstEdge;/* 边表头指针 */ 

}AdjList[MAXSIZE];

typedef struct Lnode{
    

int Nv;

int Ne;

AdjList G;

}*LGraph;

typedef struct Enode{
    

int v1;

int v2;

Weight weight;

//bool flag;//true -> false ->

}Edge;

 

 

 

 

LGraph  CreateGraph(int n){
    

LGraph Graph=(LGraph)malloc(sizeof(struct Lnode));

Graph->Nv=n;

Graph->Ne=0;

for(int i=0;i<n;i++){
    

Graph->G[i].FirstEdge=NULL;

 

}

 

return Graph;

}

 

void InsertEdge(LGraph Graph,const Edge *ptre){
    

PtrToAdjVNode Newnode=(PtrToAdjVNode)malloc(sizeof(struct AdjVNode));

Newnode->weight=ptre->weight;

Newnode->adjv=ptre->v2;

Newnode->Next=Graph->G[ptre->v1].FirstEdge;

Graph->G[ptre->v1].FirstEdge=Newnode;

//若是无向边

 

Newnode=(PtrToAdjVNode)malloc(sizeof(struct AdjVNode));

Newnode->weight=ptre->weight;

Newnode->adjv=ptre->v1;

Newnode->Next=Graph->G[ptre->v2].FirstEdge;

Graph->G[ptre->v2].FirstEdge=Newnode;

 

 

 

}

 

LGraph  buildGraph(){
    

LGraph Graph; 

    Edge E; 

    int V; 

    int Nv, i; 

      

    scanf("%d", &Nv);   /* 读入顶点个数 */ 

    Graph = CreateGraph(Nv); /* 初始化有Nv个顶点但没有边的图 */  

      

    scanf("%d", &(Graph->Ne));   /* 读入边数 */ 

    if ( Graph->Ne != 0 ) {
     /* 如果有边 */  

        

        /* 读入边,格式为"起点 终点 权重",插入邻接矩阵 */ 

        for (i=0; i<Graph->Ne; i++) {
     

            scanf("%d %d %d", &E.v1, &E.v2, &E.weight);  

            /* 注意:如果权重不是整型,Weight的读入格式要改 */ 

            InsertEdge( Graph, &E ); 

        }

    }

 

/* 如果顶点有数据的话,读入数据 */ 

    for (V=0; V<Graph->Nv; V++)  

        scanf(" %c", &(Graph->G[V].data)); 

  

    return Graph; 

 

 

}

 

/*-------------------- 边的最小堆定义 --------------------*/

typedef Edge Ele;

const Ele ERROR={
    -1,-1,-1};

typedef struct heap{
    

Ele *data;

int size;

int maxsize;

}*MinHeap;

MinHeap createMinHeap(int n){
    

MinHeap minheap=(MinHeap)malloc(sizeof(struct heap));

minheap->data=(Ele*)malloc(sizeof(Ele)*(n+1));

minheap->size=0;

minheap->maxsize=n;

return minheap;

 

}

bool isfull(MinHeap heap){
    

 

 

    return heap->size>=heap->maxsize;

}

bool isempty(MinHeap heap){
    

if(heap==NULL)

heap->size =5;

    return heap->size<=0;

}

 

void InsertMinHeap(MinHeap heap,Ele e){
    

if(isfull(heap))

    return;

heap->size++;

int i;

for(i=heap->size;i>1&&e.weight<heap->data[i/2].weight;i/=2)

heap->data[i]=heap->data[i/2];

heap->data[i]=e;

 

}

 

Ele DelMinHeap(MinHeap heap){
    

if(isempty(heap))

return ERROR;

Ele min=heap->data[1];

Ele tmp=heap->data[heap->size--];

int i=0,childmin;

for(i=1;2*i<=heap->size;i=childmin)

{
    

childmin=2*i;

if(childmin!=heap->size&&heap->data[childmin].weight>heap->data[childmin+1].weight)

childmin++;

if(tmp.weight<=heap->data[childmin].weight)break;

 heap->data[i]=heap->data[childmin];  

}

heap->data[i]=tmp;

 

return min;

}

 

void PercDown(MinHeap heap, int p){
    

 

 Ele tmp = heap->data[p]; /* 取出根结点存放的值 */

    int i=p,childmin;

for(;2*i<=heap->size;i=childmin)

{
    

childmin=2*i;

if(childmin!=heap->size&&heap->data[childmin].weight>heap->data[childmin+1].weight)

childmin++;

if(tmp.weight<=heap->data[childmin].weight)break;

 heap->data[i]=heap->data[childmin];  

}

heap->data[i]=tmp;

 

 

}

MinHeap buildMinHeap(Ele e[],int n){
    

MinHeap heap=createMinHeap(n);

heap->size=n;

for(int i=0;i<n;i++)

heap->data[i]=e[i];

 

for(int i=n/2;i>0;i--)

    PercDown(heap,i);

 

return heap;

 

}

/*-------------------- 边的最小堆定义end --------------------*/

/*-------------------- 顶点并查集定义 --------------------*/

typedef int ElementType; /* 默认元素可以用非负整数表示 */

typedef int SetName;     /* 默认用根结点的下标作为集合名称 */

typedef ElementType SetType[MAXSIZE]; /* 假设集合元素下标从0开始 */

 

void InitializeVSet( SetType S, int N )

{
     /* 初始化并查集 */

    int X;

 

    for ( X=0; X<N; X++ ) S[X] = -1;

}

 

void Union( SetType S, SetName Root1, SetName Root2 )

{
     /* 这里默认Root1和Root2是不同集合的根结点 */

    /* 保证小集合并入大集合 */

    //if ( S[Root2] < S[Root1] ) { /* 如果集合2比较大 */

      //  S[Root2] += S[Root1];     /* 集合1并入集合2  */

        //S[Root1] = Root2;

    //}

    //else {                         /* 如果集合1比较大 */

      //  S[Root1] += S[Root2];     /* 集合2并入集合1  */

        //S[Root2] = Root1;

    //}

S[Root2]=Root1;

}

 

SetName Find( SetType S, ElementType X )

{
     /* 默认集合元素全部初始化为-1 */

    if ( S[X] < 0 ) /* 找到集合的根 */

        return X;

    else

        return Find( S, S[X] ); /* 路径压缩 */

}

 

bool CheckCycle( SetType VSet, int V1, int V2 )

{
     /* 检查连接V1和V2的边是否在现有的最小生成树子集中构成回路 */

    int Root1, Root2;

 

    Root1 = Find( VSet, V1 ); /* 得到V1所属的连通集名称 */

    Root2 = Find( VSet, V2 ); /* 得到V2所属的连通集名称 */

 

    if( Root1==Root2 ) /* 若V1和V2已经连通,则该边不能要 */

        return false;

    else {
     /* 否则该边可以被收集,同时将V1和V2并入同一连通集 */

        Union( VSet, Root1, Root2 );

        return true;

    }

}

 

 

MinHeap InitializeESet(LGraph Graph){
    

    PtrToAdjVNode W;

    Edge edge;

MinHeap edgeheap=createMinHeap(Graph->Ne);

for (int V=0; V<Graph->Nv; V++ )

        for ( W=Graph->G[V].FirstEdge; W; W=W->Next )

            if ( V<W->adjv) {
     /* 避免重复录入无向图的边,只收V1<V2的边 */

                edge.v1 = V;

                edge.v2 = W->adjv;

                edge.weight=W->weight;

                //printf("abc %d ",edge.weight );

                InsertMinHeap(edgeheap,edge);

            }

return edgeheap;

}

 

Edge GetEdge( MinHeap edgeheap){
    

 

    return DelMinHeap(edgeheap);

}

 

 

/*-------------------- 并查集定义结束 --------------------*/

    int Kruskal( LGraph Graph, LGraph MST )

    {
     /* 将最小生成树保存为邻接表存储的图MST,返回最小权重和 */

        Weight TotalWeight;

        int ECount;

        SetType VSet; /* 顶点并查集 */

        MinHeap edgeheap=NULL;    /* 边的最小堆 */

       // printf("%p ",edgeheap );exit(0);

       Edge NextEdge;

        InitializeVSet( VSet, Graph->Nv ); /* 初始化顶点并查集 */

      

        edgeheap=InitializeESet( Graph ); /* 初始化边的最小堆 */

 

        /* 创建包含所有顶点但没有边的图。注意用邻接表版本 */

        MST = CreateGraph(Graph->Nv);

        TotalWeight = 0; /* 初始化权重和     */

        ECount = 0;      /* 初始化收录的边数 */

    

      

        while ( ECount < Graph->Nv-1 ) {
      /* 当收集的边不足以构成树时 */

            NextEdge = GetEdge( edgeheap ); /* 从边的最小堆de到最小边 */

        //printf("%d ", NextEdge.weight);

            if (NextEdge.v1==-1) /* 边集已空 */

                break;

 

            /* 如果该边的加入不构成回路,即两端结点不属于同一连通集 */

            if ( CheckCycle( VSet, NextEdge.v1, NextEdge.v2 )==true ) {
    

                /* 将该边插入MST */

                InsertEdge( MST, &NextEdge);

                printf("%d<->%d weight:%d collected ",NextEdge.v1,NextEdge.v2,NextEdge.weight);

                TotalWeight += NextEdge.weight; /* 累计权重 */

                ECount++; /* 生成树中边数加1 */

            }

        }

        if ( ECount < Graph->Nv-1 )

            TotalWeight = -1; /* 设置错误标记,表示生成树不存在 */

    

        return TotalWeight;

    }

 

int main(){
    

 

LGraph Graph=buildGraph();

LGraph MST;

printf("------------------------------------------- ");

printf("TotalWeight %d",Kruskal(Graph,MST));

 

    return 0;

}

实验结果

在这里插入图片描述

版权声明:本文为博主原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明。
本文链接:https://blog.csdn.net/m0_46529566/article/details/121343688

智能推荐

mysql etl mongodb_kettle之mongodb数据同步-程序员宅基地

文章浏览阅读657次。需求:1.源数据库新增一条记录,目标库同时新增一条记录;2.源数据库修改一条记录,目标库同时修改该条记录;示例用到三个Kettle组件下面详细说下每个组件的配置Source:本示例连接的是Mongodb数据库,四个字段,ID默认为主键,_id会系统自动生成暂时先不管。值映射:本步在本示例作用不大,只是为了测试效果。按照截图上进行配置即可MongoDbOutput:关键是这一步的配置官网上对这个ta..._kettle 怎么配置两张mongodb表实时更新

PSO(粒子群)求解TSP(旅行商问题)_pso tsp-程序员宅基地

文章浏览阅读2.4k次,点赞2次,收藏23次。PSO(粒子群)求解TSP(旅行商问题)  PSO求解TSP代码可以参考之前的博客PSO求解TSP。但是有时候可能会加一些限制,例如某个城市需要先被访问。这里以城市8要第一个访问,起始只需要每次昨晚位置更新后,将城市8更换至第一个访问城市即可。修改  只需修改初始化和每次更新位置的函数,initpos.m 和 updatepos.m 文件。function [ pos ] = initpos( pasize,padim )%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%_pso tsp

第20篇-SAP咨询顾问英语口语提升宝典-程序员宅基地

文章浏览阅读1.3k次,点赞35次,收藏24次。「全网最细」保姆级教程总结,全盘托出式英语口语提升分享,最高效的口语实战提升方法,打工人、学生均适用。

Scene Text Image Super-Resolution in the Wild-程序员宅基地

文章浏览阅读937次。Scene Text Image Super-Resolution in the Wild ECCV2020上的一篇文章,作者来自商汤研究院、香港大学等。Motivation文章的主要动机有以下几点:现代文本识别技术在清晰本文上已经取得了很好的识别效果,但是在识别低分辨率文本图像时,表现性能急剧下降,主要困难在于光学退化模糊了字符形状,所以作者提到将超分作为文本识别任务的预处理过程非常有必要。目前大多数SISR方法是在特定下采样核(Bicubic)的低分辨率图像上进行训练,不能很好地推广到真实的_scene text image super-resolution in the wild

深入分析MPU6050在ESP32的实现流程_esp32 mpu6050-程序员宅基地

文章浏览阅读1k次。概念与操作描述一种用于在集成电路之间进行数据传输的串行通信协议。主设备(Master)发起通信并控制整个数据传输过程的设备。从设备(Slave)被动响应主设备请求的设备。数据线(SDA)双向的数据线,用于传输数据。时钟线(SCL)主设备通过时钟线控制数据的传输速率。地址每个从设备在总线上具有唯一的地址,用于识别设备。读写操作主设备向从设备发送读取或写入命令,用于读取从设备的数据或向从设备写入数据。应答(ACK/NACK)_esp32 mpu6050

畅购商城第五天_商城系统 es商品搜索排序-程序员宅基地

文章浏览阅读736次。第5章 商品搜索学习目标Elasticsearch安装docker安装Elasticsearch系统参数问题跨域操作IK分词器配置Kibana的使用->DSL语句Kibana->DSL语句操作->ElasticsearchES导入商品搜索数据Sku数据导入到ElasticsearchMap数据类型->Object关键词搜索->能够实现搜索流程代码的编写分类统计搜索1. Elasticsearch 安装我们之前已经使_商城系统 es商品搜索排序

随便推点

为什么java Hashmap 中的加载因子是默认为0.75_java中0.75-程序员宅基地

文章浏览阅读1.4w次,点赞12次,收藏33次。转自:http://www.jianshu.com/p/dff8f4641814前几天在一个群里看到有人讨论hashmap中的加载因子为什么是默认0.75。HashMap源码中的加载因子static final float DEFAULT_LOAD_FACTOR = 0.75f;当时想到的是应该是“哈希冲突”和“空间利用率”矛盾的一个折衷。跟数据结构要么查询快要么插_java中0.75

智能社vue.js精讲项目实战(完整)_vue2.0项目实战语法-智能社-程序员宅基地

文章浏览阅读1.7k次。下载地址:百度网盘_vue2.0项目实战语法-智能社

Android进阶——Handler的应用之解决Only the original thread that created a view hierarchy can touch its views_android handler更新ui only the original thread that -程序员宅基地

文章浏览阅读3.9w次,点赞2次,收藏4次。解决错误:Only the original thread that created a view hierarchy can touch its views。_android handler更新ui only the original thread that created a view hierarchy

[ctf学习]ctfhub技能树-web_ctfhub技能树(web)-程序员宅基地

文章浏览阅读1.4k次。背景知识HTTP 请求方法, HTTP/1.1协议中共定义了八种方法(也叫动作)来以不同方式操作指定的资源。方法1、OPTIONS返回服务器针对特定资源所支持的HTTP请求方法,也可以利用向web服务器发送‘*’的请求来测试服务器的功能性2、HEAD向服务器索与GET请求相一致的响应,只不过响应体将不会被返回。这一方法可以再不必传输整个响应内容的情况下,就可以获取包含在响应小消息头中的元信息。3、GET向特定的资源发出请求。注意:GET方法不应当被用于产生“副作用”的操作中,例如在Web A_ctfhub技能树(web)

截屏软件集合-程序员宅基地

文章浏览阅读684次。截屏软件copy /b ssss.png + licecap.zip sss2.png新软件PureRef更好用https://www.pureref.com视频缩略图显示:图片查看器HONEYVIEWunity优化

红米note4x连点Android,红米Note4X lineage16 安卓9.0 极致省电 纯净 完美root Xposed 经典版...-程序员宅基地

文章浏览阅读680次。小米lineage os16经典版,再次开启享受类原生的乐趣。部分机型支持PT项目,也就是说必须刷入支持PT版本TWRP后Vendor分区才可以正常启动,原生自带vendor分区的无视使用TWRP刷入如遇到到无限重启recovery,格式data开机就好LOS16.0特色介绍源于lineage16.0最新源码制作,稳定靠谱默认添加开机语音中文,时区为正常北京超级纯净,非常流畅。它有电话、信息、相机..._lineage-16.0 note4x

推荐文章

热门文章

相关标签