假设一个图的边的权值都在1到n的整数范围内，如何设计出一种算法来找出这个图的最小生成树呢？

Question

V代表点，E代表边，假设一个图的边的权值都在**1到n的整数范围**内，如何设计出一种**O(n(V+E))**的算法来找出这个图的最小生成树呢？有没有办法通过修改kruskal算法来得到O(n(V+E))时间复杂度呢？如果没法修改，有没有其它的算法可以达到O(n(V+E))？
不用写代码，只要给出具体算法思路即可，感谢！！

Answer 1

#include <stdio.h>
#include <stdlib.h>
#define Max 50
typedef struct road *Road;
typedef struct road
{
    int a , b;
    int w;
}road;

typedef struct graph *Graph;
typedef struct graph
{
    int e , n;
    Road data;
}graph;

Graph initGraph(int m , int n)
{
    Graph g = (Graph)malloc(sizeof(graph));
    g->n = m;
    g->e = n;
    g->data = (Road)malloc(sizeof(road) * (g->e));
    return g;
}

void create(Graph g)
{
    int i;
    for(i = 1 ; i <= g->e ; i++)
    {
        int x , y, w;
        scanf("%d %d %d",&x,&y,&w);
        if(x < y)
        {
            g->data[i].a = x;
            g->data[i].b = y;
        }
        else
        {
            g->data[i].a = y;
            g->data[i].b = x;
        }
        g->data[i].w = w;
    }
}

int getRoot(int v[], int x)
{
    while(v[x] != x)
    {
        x = v[x];
    }
    return x;
}

void sort(Road data, int n)
{
    int i , j;
    for(i = 1 ; i <= n-1 ; i++)
    {
        for(j = 1 ; j <= n-i ; j++)
        {
            if(data[j].w > data[j+1].w)
            {
                road t = data[j];
                data[j] = data[j+1];
                data[j+1] = t;
            }
        }
    }
}

int Kruskal(Graph g)
{
    int sum = 0;
    //并查集
    int v[Max];
    int i;
    //init
    for(i = 1 ; i <= g->n ; i++)
    {
        v[i] = i;
    }
    sort(g->data , g->e);
    //main
    for(i = 1 ; i <= g->e ; i++)
    {
        int a , b;
        a = getRoot(v,g->data[i].a);
        b = getRoot(v,g->data[i].b);
        if(a != b)
        {
            v[a] = b;
            sum += g->data[i].w;
        }
    }
    return sum;
}

int main()
{
    int m , n , id = 1;
    while(scanf("%d %d",&m,&n) != EOF)
    {
        int r , i;
        Graph g = initGraph(m,n);
        create(g);
        r = Kruskal(g);
        printf("Case %d:%d\n",id++,r);
        free(g);
    }
    return 0;
}

https://blog.csdn.net/mgsky1/article/details/77840286