文档章节

克鲁斯卡尔(邻接矩阵无向网)

cyleft
 cyleft
发布于 2017/06/01 13:47
字数 393
阅读 12
收藏 0

 

#include <iostream>
#include <C:\Users\chenyi\OneDrive\c_work_space\A_数据结构调用\无向网\main.cpp>
//上述文件见文章底部链接
using namespace std;

int LocateVex(AMGraph G,VerTexType v);


/**辅助数组两个,存储最小边与值*/
struct A{
    VerTexType Head;
    VerTexType Tail;
    ArcType lowcost;
}Edge[MVNum];

int Vexset[MVNum];


int Sort(struct A *Edge,int len){
    cout<<len<<endl;
    VerTexType H;
    ArcType T;
    ArcType lowcost;
    for(int i=0;i<len;i++){
        for(int j=i+1;j<len;j++){
            if(Edge[j].lowcost<Edge[i].lowcost){
                H = Edge[i].Head;
                Edge[i].Head = Edge[j].Head;
                Edge[j].Head = H;

                T = Edge[i].Tail;
                Edge[i].Tail = Edge[j].Tail;
                Edge[j].Tail = T;

                lowcost = Edge[i].lowcost;
                Edge[i].lowcost = Edge[j].lowcost;
                Edge[j].lowcost = lowcost;
            }
        }
    }
    for(int i=0;i<len;i++){
        cout<<Edge[i].lowcost<<","<<Edge[i].Head<<","<<Edge[i].Tail<<endl;
    }
}

int LocateVex(AMGraph G,VerTexType v){
    for(int i=0;i<G.vexnum;i++){
        if(G.vexs[i]==v){
            return i;
        }
    }
    return -1;
}

/**克鲁斯卡尔算法,u是定点,从他出发*/
void MiniSpanTree_Kruskal(AMGraph G){
    int k=0;
    for(int i=0;i<G.vexnum;i++){
        for(int j=0;j<G.vexnum;j++){
            if(G.arcs[i][j]!=MaxInt && j>i){
                Edge[k].lowcost = G.arcs[i][j];
                Edge[k].Head = G.vexs[i];
                Edge[k].Tail = G.vexs[j];
                k++;
            }
        }
    }

    for(int i=0;i<G.vexnum;i++){
        Vexset[i] = i;
    }
    Sort(Edge,k);
    for(int i=0;i<G.arcnum;i++){
        int v1,v2;
        int vs1,vs2;
        v1 = LocateVex(G,Edge[i].Head);
        v2 = LocateVex(G,Edge[i].Tail);
        vs1 = Vexset[v1];
        vs2 = Vexset[v2];
        if(vs1!=vs2){
            cout<<Edge[i].Head<<"→"<<Edge[i].Tail<<endl;
            for(int j=0;j<G.vexnum;j++){
                if(Vexset[j]==vs2) Vexset[j] = vs1;
            }
        }
    }
}



int main()
{
    AMGraph amg;

    CreatUDN(amg); //创建无向网络
    UDN_dis(amg);  //显示无向网!
    MiniSpanTree_Kruskal(amg);
    return 0;
}


//int Min(struct CLOSE){
//    ;
//}

/**
6 10
1 2 3 4 5 6
1 2 6
1 4 5
1 3 1
2 3 5
3 4 5
4 6 2
2 5 3
3 5 6
3 6 4
5 6 6
*/

无向网

© 著作权归作者所有

cyleft
粉丝 1
博文 30
码字总数 9912
作品 0
九江
程序员
私信 提问
数据结构探险之图篇(上)理论篇

数据结构探险之图篇 什么是图? 如下图:无向图 & 有向图 箭头分方向。 无向图中每条认为有来有回两条线 图中的概念: 结点称为顶点。 之间的线称为弧。 弧尾和弧头(箭头)。 从顶点发出去和...

天涯明月笙
2017/09/11
0
0
Java 图的最小生成树 — prim算法和kruskal算法

一个有 n 个结点的连通图的生成树是原图的极小连通子图,且包含原图中的所有 n 个结点,并且有保持图连通的权值和边最小 一、最小生成树的应用 生成树和最小生成树有许多重要的应用。 例如:...

磊_lei
2018/05/18
0
0
图的基础知识(二、存储)

图需要存储的信息有以下这些 1、顶点信息 2、边或弧的信息,如果有权,也需要表示出来 3、顶点个数、边(弧)的个数 邻接矩阵及其实现 顶点数据存储: 一维数组 边(弧)信息存储 邻接矩阵 ...

大胖和二胖
2016/11/30
33
0
软考程序员课程精讲之最小生成树

最小生成树 如果连通图G的一个子图是一棵包含G的所有顶点的树,则该子图称为G的生成树。生成树是连通图包含图中的所有顶点的极小连通子图。值得注意的是,图的生成树并不唯一。从不同的顶点出...

软考希赛教育
2017/05/04
3
0
【算法和数据结构】图(一)图的定义和封装(C++实现)

图,一种复杂的数据结构,在实际生活中起着举足轻重的作用。如路网(线路规划),社交网络描述等等。现在我们就以下面这个简单无向图(图1)为例,来说明使用邻接矩阵 实现图在计算机中的存储...

qq_28869927
2017/02/27
0
0

没有更多内容

加载失败,请刷新页面

加载更多

3_数组

3_数组

行者终成事
今天
7
0
经典系统设计面试题解析:如何设计TinyURL(二)

原文链接:https://www.educative.io/courses/grokking-the-system-design-interview/m2ygV4E81AR 编者注:本文以一道经典的系统设计面试题:《如何设计TinyURL》的参考答案和解析为例,帮助...

APEMESH
今天
7
0
使用logstash同步MySQL数据到ES

概述   在生成业务常有将MySQL数据同步到ES的需求,如果需要很高的定制化,往往需要开发同步程序用于处理数据。但没有特殊业务需求,官方提供的logstash就很有优势了。   在使用logstas...

zxiaofan666
今天
10
0
X-MSG-IM-分布式信令跟踪能力

经过一周多的鏖战, X-MSG-IM的分布式信令跟踪能力已基本具备, 特点是: 实时. 只有要RX/TX就会实时产生信令跟踪事件, 先入kafka, 再入influxdb待查. 同时提供实时sub/pub接口. 完备. 可以完整...

dev5
今天
7
0
OpenJDK之CyclicBarrier

OpenJDK8,本人看的是openJDK。以前就看过,只是经常忘记,所以记录下 图1 CyclicBarrier是Doug Lea在JDK1.5中引入的,作用就不详细描述了,主要有如下俩个方法使用: await()方法,如果当前线...

克虏伯
今天
8
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部