最小生成树之Kruskal(并查集实现)

#include "stdafx.h"
#include <iostream>
#include <fstream>
#include <Windows.h>
#include <algorithm>

using namespace std;

#define INFINITY INT_MAX
#define MAX_VERTEX_NUM 20  //顶点最多个数
#define LENGTH 5           //顶点字符长度

//********************************Kruskal(并查集实现)********************************begin

typedef struct _edge
{
int v;             //起点
int w;             //终点
int weight;        //权值
}edge;

typedef struct _Graph
{
    edge edges[MAX_VERTEX_NUM*MAX_VERTEX_NUM/2]; //弧的数组
char vexs[MAX_VERTEX_NUM][LENGTH];           //顶点数组
int vexnum;                                  //顶点个数
int arcs;                                    //弧的个数
}Graph;

int father[MAX_VERTEX_NUM];
int rank[MAX_VERTEX_NUM];

int LocateVex(const Graph & g, char name[LENGTH])
{
for (int i = 0; i < g.vexnum; i++)
    {
if (0 == strcmp(g.vexs[i], name))
        {
return i;
        }
    }
return -1;
}

//图的建造
void CreateGraph(Graph &g)
{
    ifstream fcin(_T("kruskal.txt"));
    fcin>>g.vexnum;
for (int i = 0; i < g.vexnum; i++)
    {
        fcin>>g.vexs[i];
    }
    fcin>>g.arcs;
char arcHead[LENGTH];
char arcTail[LENGTH];
int weight;
for (int i = 0; i < g.arcs; i++)
    {
        memset(arcHead, 0, LENGTH);
        memset(arcTail, 0, LENGTH);
        fcin>>arcTail>>arcHead>>weight;
int w = LocateVex(g, arcHead);
int v = LocateVex(g, arcTail);
        g.edges[i].w = w;
        g.edges[i].v = v;
        g.edges[i].weight = weight;
    }
}

int comp(const void *a,const void *b)
{
return ((edge *)a)->weight - ((edge *)b)->weight;
}

//并查集
//1、初始化
void make_set()
{
for (int i = 0; i < MAX_VERTEX_NUM; i++)
    {
        father[i] = i;
        rank[i] = 1;
    }
}

//2、查询
int find_set(int x)
{
while (x != father[x])
    {
        x = father[x];
    }
return x;
}

//3、合并
bool Union(int first, int second)
{
int x = find_set(first);
int y = find_set(second);
if (x == y)    //同一个父亲就返回
    {
return false;
    }
else
    {
if (rank[x] > rank[y])
        {
            father[y] = x;
        }
else 
        {
if (rank[x] == rank[y])
            {
                rank[y]++;
            }
            father[x] = y;
        }
return true;
    }
return false;
}

//kruskal算法
void MiniSpanTree_Kruskal(Graph g)
{
int count = 0;
int cost = 0;
for (int i = 0; i < g.arcs; i++)
    {
if (Union(g.edges[i].w, g.edges[i].v))
        { 
            cost += g.edges[i].weight;
            count++;
            cout<<"第"<<count<<"条："<<g.vexs[g.edges[i].v]<<"  "
                <<g.vexs[g.edges[i].w]<<"  "<<g.edges[i].weight<<endl;            if (count == g.vexnum - 1)
            {
break;
            }
        }
    }
    cout<<"最少花费为："<<cost<<endl;
}

//********************************Kruskal(并查集实现)********************************end

//辅助函数，设置控制台的颜色
void SetConsoleTextColor(WORD dwColor)
{
    HANDLE handle = GetStdHandle(STD_OUTPUT_HANDLE);
if (INVALID_HANDLE_VALUE == handle)
    {
return;
    }
    SetConsoleTextAttribute(handle, dwColor);
}

int _tmain(int argc, _TCHAR* argv[])
{
    Graph graph;
    CreateGraph(graph);
    SetConsoleTextColor(FOREGROUND_GREEN | FOREGROUND_INTENSITY);
    cout<<"********************Kruskal(并查集实现)**********************"<<endl<<endl;
    make_set();
    qsort(graph.edges, graph.arcs, sizeof(edge), comp);
    MiniSpanTree_Kruskal(graph);
    cout<<endl<<endl;

return 0;
}

界面运行如下：

图建造用到的kruskal.txt文件为：

6
V1 V2 V3 V4 V5 V6
10
V1 V2 6
V1 V3 1
V1 V4 5
V2 V3 5
V2 V5 3
V3 V4 5
V3 V5 6
V3 V6 4
V4 V6 2
V5 V6 6