Code_mzh 发表于 2018-2-24 19:53:02

最小生成树kruskal

#include <iostream>
using namespace std;
#define MAXSIZE 100
#define INFINITY 65535
typedef int ElemType;
typedef char VertexType;
typedef struct MGraph{
    VertexType vertex;///顶点表
    ElemType arc;///邻接矩阵，可看作边表
    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;
    }
    ///初始化矩阵
    for (i = 0; i < G->vertexNum; i++) {
      for (j = 0; j < G->vertexNum; j++) {
            G->arc = G->arc = INFINITY;
            G->arc = 0;
      }
    }
    ///输入由顶点构成的边
    for (k = 0; k < G->arcNum; k++) {
      cout << "请输入与边关联的两个顶点的序号和权值,例如（ 1 2 34）：" << endl;
      cin >> i>>j>>n;
      G->arc = n;
      G->arc = G->arc;
    }
}
///交换边集数组中的元素
void swap(EdgeNode edges[], int i ,int j){
    int temp ;
    temp = edges.begin;
    edges.begin = edges.begin;
    edges.begin = temp;
    temp=edges.end;
    edges.end = edges.end;
    edges.end = temp;
    temp = edges.weight;
    edges.weight = edges.weight;
    edges.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.weight > edges.weight)
            {
                swap(edges,j,j+1);
            }
      }
    }
}

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

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

python~ 发表于 2018-2-24 20:26:45

22

admintest166 发表于 2018-2-24 21:39:00

6

Namier 发表于 2018-3-19 20:02:39

QAQ

Lumos 发表于 2018-3-19 20:46:48

看

xiaocy123 发表于 2018-3-19 23:26:11

看看

大川 发表于 2018-3-21 12:50:09

Q

fan1993423 发表于 2018-3-21 13:48:52

{:5_91:}

JxinBain 发表于 2018-3-21 17:56:52

321

Ae_ki 发表于 2018-3-21 22:27:36

1

996561465 发表于 2018-3-23 13:55:26

11

kykio 发表于 2018-5-20 21:00:12

学习学习

jesushtc 发表于 2018-5-31 15:36:57

{:9_239:}

刘亮 发表于 2018-6-2 16:32:16

谢谢大佬

wujixiang 发表于 2018-6-2 20:19:31

33

王7149 发表于 2018-6-10 16:43:17


0

我要去实习！ 发表于 2018-7-28 14:06:54

1

天使不在线 发表于 2018-7-28 21:17:37

{:10_277:}

tabuainiwoai 发表于 2018-8-1 16:05:55

楼主费心了。

crjun 发表于 2018-8-9 09:21:27

看看
页: [1] 2 3
查看完整版本: 最小生成树kruskal