最小生成树

忘是亡心i 2022-08-03 05:28 202阅读 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;
    }