最小生成ツリー-最小ウェイト値

二つの方法
1.kruskal:集計エッジ格納方式:隣接テーブル時間複雑度:O(eloge)適用:疎網
2.Primアルゴリズム:集計点記憶方式:マトリックス時間複雑度:O(n^2)適合:稠密網
(1)Kruskal
SL:エッジを小さい順に並べ替え,親ノードが同じかどうかを判断することにより,異なる集計可能,集計回数n−1

/*
Kruskal：     
  ：   ； 
*/
#include
#include
using namespace std;
const int Max=10005; 
struct Node
{
	int u,v;
	int w;
}e[Max];
int fa[Max];
int cnt=0;
bool cmp(Node a,Node b)
{
	return a.w>n>>m;
   init(n);
   cout<>e[i].u>>e[i].v>>e[i].w;
   }
   //    
   sort(e+1,e+1+m,cmp);	
   cout<

(2)Prim

/*
**     :
  ：       
**    :
1.    
**  ：
1.Prim 
2.Kruscal 
*/
#include
using namespace std;
const int Max=10005;
const int INF=99999999; 
int mp[Max][Max];
int path[Max];
int dis[Max],vis[Max]; 
int cnt=0;
int Prim(int n)
{
	cout<dis[j]&&!vis[j])
		  {
		  	Min=dis[j];
		  	p=j;
		  }	
		}
		vis[p]=1;
		sum+=dis[p];
		path[++cnt]=p;
		for(int k=1;k<=n;k++)
		{
			if(dis[k]>mp[p][k])
			dis[k]=mp[p][k];
		}
	}
	return sum;
}
int main()
{
	int n,m,u,v,vl,c;
	cout<>c;
	if(c==2)
	{
  	cout<>n>>m;
    
	}
	else
	{
		n=3,m=3;
	}
  	//    
  	for(int i=1;i<=n;++i)
  	{
  	  for(int j=1;j<=n;j++)
  	  mp[i][j]=INF;
	} 
	if(c==2)
	{
	cout<>u>>v>>vl;
	 if(mp[u][v]>vl)
	 mp[u][v]=mp[v][u]=vl;//            。     
	} 
    }
    else
    {
	 mp[1][2]=mp[2][1]=1;
	 mp[2][3]=mp[3][2]=1;
	 mp[1][3]=mp[3][1]=4;	
	}
	int sum=Prim(n);
	cout<";
    }
	cout<"<