图论----生成树

本文介绍了图中最小生成树的两种算法—-Prim算法和Kruskal算法

@[TOC]

Prim算法

#include<stdio.h>
typedef int EdgeType;
typedef char VertexType;
#define MAXVEX 100
#define INFINITY 65535
int visited[MAXVEX];

typedef struct
{
    VertexType vexs[MAXVEX];
    EdgeType arc[MAXVEX][MAXVEX];
    int numVertexs, numEdges;
}MGraph;

void CreateMGraph(MGraph *G)
{
    int row = 0, column = 0, value = 0;
    printf("请输入顶点数和边数\n");
    scanf("%d %d",&G->numVertexs, &G->numEdges);
    getchar();
    printf("请输入顶点\n");
    for (int i = 0; i < G->numVertexs; ++i)
    {
        scanf("%c",&G->vexs[i]);
        getchar();
    }
    for (int i = 0; i < G->numVertexs; ++i)
    {
        for (int j = 0; j < G->numVertexs; ++j)
        {
            G->arc[i][j] = INFINITY;
        }
    }
    printf("请输入边\n");
    for (int i = 0; i < G->numEdges; ++i)
    {
        scanf("%d %d %d",&row, &column, &value);
        G->arc[row][column] = value;
        G->arc[column][row] = value; //无向图，若是有向图可以不添加
    }
}

void show(MGraph *g)
{
    for (int i = 0; i < g->numVertexs; ++i)
    {
        for (int j = 0; j < g->numVertexs; ++j)
        {
            printf("%7d",g->arc[i][j]);
        }
        printf("\n");
    }
}

void MiniSpanTree_Prim(MGraph *g)
{
    int min, k = 0;
    int len = g->numVertexs;
    int lowcosts[len];
    int adjvex[len];
    lowcosts[0] = 0;
    adjvex[0] = 0;
    for (int i = 1; i < len; ++i)
    {
        lowcosts[i] = g->arc[0][i];
        adjvex[i] = 0;
    }
    for (int i = 1; i < len; ++i)
    {
        min = INFINITY;
        for (int j = 1; j < len; ++j)
        {
            if (lowcosts[j] != 0 && min > g->arc[k][j])
            {
                min = g->arc[k][j];
                k = j;
            }
        }
        lowcosts[k] = 0;
        for (int m = 1; m < len; ++m)
        {
            if (lowcosts[m] != 0 && lowcosts[m] > g->arc[k][m])
            {
                lowcosts[m] = g->arc[k][m];
                adjvex[m] = k;
            }
        }
    }
    for (int i = 0; i < len; ++i)
    {
        printf("%d\t",adjvex[i]);
    }
}

int main()
{
    freopen("5.txt","r",stdin);
    MGraph *g = (MGraph*)malloc(sizeof(MGraph));
    CreateMGraph(g);
    MiniSpanTree_Prim(g);
    return 0;
}

5.txt

9 14
A B C D E F G H I
0 1 10
0 5 11
1 2 18
1 6 16
1 8 12
2 3 22
2 8 8
3 4 20
3 7 16
3 8 21
4 5 26
4 7 7
5 6 17
6 7 19

细细思考，这与求最短路径的思想是一样的，都是基于贪心的思想，甚至连代码样式都很类似，只是很少部分不一样。

Kruskal算法

#include<stdio.h>
typedef int EdgeType;
typedef char VertexType;
#define MAXVEX 100
#define INFINITY 65535
int visited[MAXVEX];

typedef struct
{
    int begin;
    int end;
    int weight;
}Edge;

typedef struct
{
    VertexType vexs[MAXVEX];
    EdgeType arc[MAXVEX][MAXVEX];
    int numVertexs, numEdges;
}MGraph;

void CreateMGraph(MGraph *G)
{
    int row = 0, column = 0, value = 0;
    printf("请输入顶点数和边数\n");
    scanf("%d %d",&G->numVertexs, &G->numEdges);
    getchar();
    printf("请输入顶点\n");
    for (int i = 0; i < G->numVertexs; ++i)
    {
        scanf("%c",&G->vexs[i]);
        getchar();
    }
    for (int i = 0; i < G->numVertexs; ++i)
    {
        for (int j = 0; j < G->numVertexs; ++j)
        {
            G->arc[i][j] = INFINITY;
        }
    }
    printf("请输入边\n");
    for (int i = 0; i < G->numEdges; ++i)
    {
        scanf("%d %d %d",&row, &column, &value);
        G->arc[row][column] = value;
        G->arc[column][row] = value; //无向图，若是有向图可以不添加
    }
}

void show(MGraph *g)
{
    for (int i = 0; i < g->numVertexs; ++i)
    {
        for (int j = 0; j < g->numVertexs; ++j)
        {
            printf("%7d",g->arc[i][j]);
        }
        printf("\n");
    }
}

int Find(int *parent, int f)
{
    while (parent[f] > 0)
        f = parent[f];
    return f;
}

void MiniSpanTree_Kruskal(MGraph *g)
{
    Edge edges[g->numEdges];
    int parent[g->numVertexs];
    for (int i = 0; i < g->numVertexs; ++i)
    {
        parent[i] = 0;
    }
    for (int i = 0; i < g->numEdges; ++i)
    {
        n = Find(parent, edges[i].begin);
        m = Find(parent, edges[i].end);
        if (n != m)
        {
            parent[n] = m;
        }
    }
}

int main()
{
    freopen("5.txt","r",stdin);
    MGraph *g = (MGraph*)malloc(sizeof(MGraph));
    CreateMGraph(g);
    //MiniSpanTree_Prim(g);
    return 0;
}

边集数组的代码没有写，所以这个程序是不能运行的。
其思想依旧是利用贪心思想，不过，贪的方式不一样，Kruskal算法是从最小的边开始，而Prim算法是从点开始。从边开始需要一个是否构成回路的判断。