鱼C论坛

 找回密码
 立即注册
查看: 7100|回复: 49

[技术交流] 最小生成树kruskal

[复制链接]
发表于 2018-2-24 19:53:02 | 显示全部楼层 |阅读模式

马上注册,结交更多好友,享用更多功能^_^

您需要 登录 才可以下载或查看,没有账号?立即注册

x
#include <iostream>
using namespace std;
#define MAXSIZE 100
#define INFINITY 65535
typedef int ElemType;
typedef char VertexType;
typedef struct MGraph{
    VertexType vertex[MAXSIZE];///顶点表
    ElemType arc[MAXSIZE][MAXSIZE];///邻接矩阵,可看作边表
    ElemType vertexNum, arcNum;///vertexNum是顶点数,arcNum是边数
};
typedef struct EdgeNode{
    int begin;
    int end;
    int weight;
};

void CreateMGraph(MGraph *G) {
    int i, j, k ,n;
    cout << "输入边数和顶点数:";
    cin >> G->arcNum >> G->vertexNum;
    ///输入顶点
    cout << "输入顶点" << endl;
    for (i = 0; i < G->vertexNum; i++) {
        cin >> G->vertex[i];
    }
    ///初始化矩阵
    for (i = 0; i < G->vertexNum; i++) {
        for (j = 0; j < G->vertexNum; j++) {
            G->arc[i][j] = G->arc[j][i] = INFINITY;
            G->arc[i][i] = 0;
        }
    }
    ///输入由顶点构成的边
    for (k = 0; k < G->arcNum; k++) {
        cout << "请输入与边关联的两个顶点的序号和权值,例如( 1 2 34):" << endl;
        cin >> i>>j>>n;
        G->arc[i][j] = n;
        G->arc[j][i] = G->arc[i][j];
    }
}
///交换边集数组中的元素
void swap(EdgeNode edges[], int i ,int j){
    int temp ;
    temp = edges[i].begin;
    edges[i].begin = edges[j].begin;
    edges[j].begin = temp;
    temp=edges[i].end;
    edges[i].end = edges[j].end;
    edges[j].end = temp;
    temp = edges[i].weight;
    edges[i].weight = edges[j].weight;
    edges[j].weight = temp;

}
///排序
void Bubblesort(MGraph G,EdgeNode edges[]){
    int i , j ;
    for( i = 0 ; i < G.vertexNum; i++)
    {
        for(j = 0 ; j < G.vertexNum; j++)
        {
            if( edges[j].weight > edges[j+1].weight)
            {
                swap(edges,j,j+1);
            }
        }
    }
}

int Find(int partent[],int f){
    while( partent[f] > 0)
    {
        f =partent[f];
    }
    return f;
}
void MiniSpanTree_Kruskal(MGraph G){
    int i, j, n, m;
    int k = 0;
    int parent[MAXSIZE];
    EdgeNode edges[MAXSIZE];
    cout<<"起点"<<"\t"<<"终点"<<"\t"<<"权值"<<endl;

    ///将这个邻接矩阵变为边集数组
    for( i = 0 ;i < G.vertexNum - 1;i++)
    {
        for(j = i + 1; j <G.vertexNum; j++)
        {
            if(G.arc[i][j] < INFINITY)
            {
                edges[k].begin = i;
                edges[k].end = j;
                edges[k].weight=G.arc[i][j];
                k++;
            }
        }
    }
    Bubblesort(G,edges);
    /****************************/
    ///初始化数组
    for(i = 0; i < G.vertexNum; i++)
    {
        parent[i] = 0;
    }
    ///打印最小生成树
    for(i = 0;i < G.arcNum; i++)
    {
        n=Find(parent,edges[i].begin);
        m=Find(parent,edges[i].end);
        if( n != m)     ///如果相等则说明形成了环状
        {
             parent[n] = m;  ///partent第n(是起点)个位置存放终点坐标
            cout<<edges[i].begin<<"\t"<<edges[i].end<<"\t"<<edges[i].weight<<endl;
        }
    }
}
int main() {
    MGraph G;
    CreateMGraph(&G);
    MiniSpanTree_Kruskal(G);
    return 0;
}
鉴于其他几个都要收费,我就免费给大家提供一段自己的代码,方便大家自己理解
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复

使用道具 举报

发表于 2018-2-24 20:26:45 | 显示全部楼层
22

想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复

使用道具 举报

发表于 2018-2-24 21:39:00 | 显示全部楼层
6
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复

使用道具 举报

发表于 2018-3-19 20:02:39 | 显示全部楼层
QAQ
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复

使用道具 举报

发表于 2018-3-19 20:46:48 | 显示全部楼层
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复

使用道具 举报

发表于 2018-3-19 23:26:11 | 显示全部楼层
看看
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复

使用道具 举报

发表于 2018-3-21 12:50:09 | 显示全部楼层
Q
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复

使用道具 举报

发表于 2018-3-21 13:48:52 | 显示全部楼层
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复

使用道具 举报

发表于 2018-3-21 17:56:52 | 显示全部楼层
321
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复

使用道具 举报

发表于 2018-3-21 22:27:36 | 显示全部楼层
1
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复

使用道具 举报

发表于 2018-3-23 13:55:26 From FishC Mobile | 显示全部楼层
11
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复

使用道具 举报

发表于 2018-5-20 21:00:12 | 显示全部楼层
学习学习
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复 支持 反对

使用道具 举报

发表于 2018-5-31 15:36:57 | 显示全部楼层
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复

使用道具 举报

发表于 2018-6-2 16:32:16 | 显示全部楼层
谢谢大佬
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复 支持 反对

使用道具 举报

发表于 2018-6-2 20:19:31 | 显示全部楼层
33
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复

使用道具 举报

发表于 2018-6-10 16:43:17 | 显示全部楼层

0
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复

使用道具 举报

发表于 2018-7-28 14:06:54 | 显示全部楼层
1
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复

使用道具 举报

发表于 2018-7-28 21:17:37 | 显示全部楼层
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复

使用道具 举报

发表于 2018-8-1 16:05:55 | 显示全部楼层
楼主费心了。
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复 支持 反对

使用道具 举报

发表于 2018-8-9 09:21:27 | 显示全部楼层
看看
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复

使用道具 举报

您需要登录后才可以回帖 登录 | 立即注册

本版积分规则

小黑屋|手机版|Archiver|鱼C工作室 ( 粤ICP备18085999号-1 | 粤公网安备 44051102000585号)

GMT+8, 2024-11-22 17:56

Powered by Discuz! X3.4

© 2001-2023 Discuz! Team.

快速回复 返回顶部 返回列表