数据结构学习之最小生成树算法

数据结构学习之最小生成树算法

0x1 生成树的概念

​ 一个连通图的生成树(连通无回路图)是一个极小连通子图,其中含有图中的全部顶点,和n-1条边。

0x2 最小生成树概念

​ 图中所有生成树中具有边权值之和最小的树称之为图的最小生成树

0x3 Prim(普里姆算法) and Kruskal(克鲁斯卡尔算法)

0x3.1 问题描述

​ Prim算法

​ 编写一个程序,实现求带权连通图的最小生成树的普里姆算法。对于如图8.55所示的带权连通图G,输出从顶点0出发的一棵最小生成树。

​ Kruskal算法

​ 领会克鲁斯卡尔算法求带权连通图最小生成树的过程和相关算法设计。

0x3.2 代码

#include <iostream>
#include <algorithm>
#include <cstdio>
#include <cstdlib>
#define INF 32767
#define MAX 200
using namespace std;
/*
6 10
0 1 5
1 2 4
3 2 5
4 3 5
5 4 1
2 0 8
2 5 9
0 3 7
3 5 6
0 5 3
*/
typedef struct
{
    int no;
}VertextType;

typedef struct
{
    int edge[MAX][MAX];
    int n;
    int e;
    VertextType info;
}MatGraph;

typedef struct
{
    int u;
    int v;
    int w;
}Edge;

void CreateMat(MatGraph &g,int n,int e)
{
    //Init
    int i=0,j=0,v=0;
    g.n=n;
    g.e=e;
    for(i=0;i<n;i++)
        for(j=0;j<n;j++)
            if(i!=j)
                g.edge[i][j]=INF;
            else
                g.edge[i][j]=0;
    for(int n=1;n<=e;n++)
    {
        cin>>i>>j>>v;
        g.edge[i][j]=v;
        g.edge[j][i]=v;
    }
}

void DispMat(MatGraph &g)
{
    for(int i=0;i<g.n;i++)
        for(int j=0;j<g.n;j++)
        {
            cout<< g.edge[i][j] <<"\t";
            if(j==g.n-1)
                cout<<endl;
        }
}

void Prim(MatGraph g,int v)
{
    int lowcost[MAX],closest[MAX],MIN;
    for(int i=0;i<g.n;i++)
    {
        lowcost[i]=g.edge[v][i];
        closest[i]=v;
    }
    for(int j=1;j<g.n;j++)
    {
        int k;
        MIN=INF;
        for(int i=0;i<g.n;i++)
        {
            if(lowcost[i]!=0 && lowcost[i]<MIN)
            {
                MIN=lowcost[i];
                k=i;
            }
        }
        printf("(%d,%d)\tweight: %d\n",closest[k],k,lowcost[k]);
        //add to V set
        lowcost[k]=0;
        // handler U-V set
        for(int i=0;i<g.n;i++)
        {
            if(lowcost[i]!=0 && g.edge[k][i]<lowcost[i])
            {
                lowcost[i]=g.edge[k][i];
                closest[i]=k;
            }
        }
    }

}

bool cmp(Edge &e1,Edge &e2)
{
    return(e1.w<e2.w);
}

void Kruskal(MatGraph g)
{
    Edge e[MAX];
    int vset[MAX];
    int k=0;
    for(int i=0;i<g.n;i++)
        for(int j=0;j<i;j++)
        {
            if(g.edge[i][j]!=0 && g.edge[i][j]!=INF)
            {
                e[k].u=i;
                e[k].v=j;
                e[k].w=g.edge[i][j];
                k++;
            }
        }
    // sort e
    sort(e,e+g.e,cmp);
    //check
    /*
    for(int i=0;i<g.n;i++)
        printf("%d\n",g.n);
    */
    // e中边的下标
    int j=0;
    // 生成的边数
    k=1;
    //init assist vset
    for(int i=0;i<g.n;i++)
    {
        vset[i]=i;
    }
    while(k<g.n)
    {
        int ul=e[j].u;
        int vl=e[j].v;
        int sn1=vset[ul];
        int sn2=vset[vl];
        if(sn1!=sn2)
        {
            printf("(%d,%d)\t weight:%d \n",ul,vl,e[j].w);
            for(int i=0;i<g.n;i++)
            {
                if(vset[i] == sn2)
                    vset[i]=sn1;
            }
            k++;
        }
        j++;
    }


}

int main()
{
    int n,e;
    cout<< "Please input the number of vertex(n) and edge(e):"<<endl;
    cin>>n>>e;
    MatGraph T;
    CreateMat(T,n,e);
    DispMat(T);
    cout<< "Prim result" <<endl;
    Prim(T,0);
    cout<< "Krusal result" <<endl;
    Kruskal(T);
    return 0;
}

0x4 结果

0x5 总结

  作业就差一个了,准备好好研究下哈夫曼的算法实现。

​