最小生成树-蒲公英云

最小生成树

忘是亡心i 2022-08-03 05:28 331阅读 0赞

一个有 n 个结点的连通图的生成树是原图的极小连通子图，且包含原图中的所有 n 个结点，并且有保持图连通的最少的边。

最小生成树在n个顶点的情形下，有n-1条边。生成树是对连通图而言的，是连同图的极小连通子图，包含图中的所有顶点，有且仅有n-1条边。非连通图的生成树则组成一个生成森林；若图中有n个顶点，m个连通分量，则生成森林中有n-m条边。

#include "stdafx.h"
#include<vector>
#include<algorithm>
using namespace std;
#define N 9  
#define MIN 1000000  
typedef struct{
    int vexnum, arcnum;
    char vexs[N];
    int matirx[N][N];
}graph;
graph g;
int mx[N][N];
// 初始化图数据      
// 0---1---2---3---4---5---6---7---8---      
// A---B---C---D---E---F---G---H---I---      
void initiate_graph()
{
    // A-B, A-D, A-E    
    g.matirx[0][1] = 10;
    g.matirx[1][0] = 10;
    g.matirx[0][3] = 5;
    g.matirx[3][0] = 5;
    g.matirx[0][4] = 7;
    g.matirx[4][0] = 7;
    // B-C      
    g.matirx[1][2] = 18;
    g.matirx[2][1] = 18;
    // C-F      
    g.matirx[2][5] = 3;
    g.matirx[5][2] = 3;
    // D-E, D-G      
    g.matirx[3][4] = 9;
    g.matirx[4][3] = 9;
    g.matirx[3][6] = 25;
    g.matirx[6][3] = 25;
    // E-F, E-H      
    g.matirx[4][5] = 1;
    g.matirx[5][4] = 1;
    g.matirx[4][7] = 14;
    g.matirx[7][4] = 14;
    // F-H, F-I      
    g.matirx[5][7] = 8;
    g.matirx[7][5] = 8;
    g.matirx[5][8] = 30;
    g.matirx[8][5] = 30;
    // G-H      
    g.matirx[6][7] = 6;
    g.matirx[7][6] = 6;
    // H-I      
    g.matirx[7][8] = 20;
    g.matirx[8][7] = 20;
}
bool UDless(pair<pair<int, int>,int> elem1, pair<pair<int, int>,int> elem2)
{
    return elem1.second < elem2.second;
}
//广度优先遍历一遍，如果不能经过所有节点，则不是连通图  
bool IsConnectedGraph()
{
    int a[N] = { 0 };
    vector<int>vec;
    vector<int>aa;
    int k = 0;
    vec.push_back(0);
    a[0] = 1;
    while (vec.size() != 0)
    {
        while (k < vec.size())
        {
            int mm = 0;
            while (mm < N)
            {
                if (mx[vec[k]][mm]>0 && a[mm]==0)
                {
                    aa.push_back(mm);
                    a[mm] = 1;
                }
                mm++;
            }
            k++;
        }
        vec = aa;
        k = 0;
        aa.clear();
    }
    for (int i = 0; i < N; i++)
        if (a[i] == 0)
            return false;
    return true;
}
bool is_erasable(int ii,int jj)
{
    mx[ii][jj] = 0;
    mx[jj][ii] = 0;
    if (IsConnectedGraph())
        return true;
    else
        return false;
}
void MST(graph g)
{
    int sv = 0;
    vector<pair<pair<int, int>, int>>ve;
    for (int i = 0; i < N; i++)
        for (int j = i; j < N; j++)
        {
        if (g.matirx[i][j])
        {
            sv++;
            pair<int, int > aa = make_pair(i, j);
            pair<pair<int, int>, int>a = make_pair(aa, g.matirx[i][j]);
            ve.push_back(a);
        }
        }
    for (int i = 0; i < N; i++)
        for (int j = 0; j < N; j++)
        {
        mx[i][j] = g.matirx[i][j];
        }
    int k = sv - N + 1;
    sort(ve.begin(), ve.end(),UDless);
    while (k > 0)
    {
        pair<pair<int, int>, int>a = ve.back();
        ve.pop_back();
        while (!is_erasable(a.first.first, a.first.second))
        {
            mx[a.first.first][a.first.second] = a.second;
            mx[a.first.second][a.first.first] = a.second;
            a = ve.back();
            ve.pop_back();
        }
        k--;
    }
}
int _tmain(int argc, _TCHAR* argv[])
{
    initiate_graph();
    MST(g);
    system("pause");
    return 0;
}