最小生成ツリー--プリムとクルーズカール

###最小生成ツリー定義:1つの無方向図、任意の2つの頂点が接続され、1つのツリーであり、このツリーを生成ツリーと呼びます.エッジに重みがある場合は、エッジの重みと最小の生成ツリーを最小生成ツリーと呼びます.最小生成ツリーを解くには2つのアルゴリズム、クルスカル(Kruskal)アルゴリズムとプリム(Prim)アルゴリズムがあります.###注意:完全な最小生成ツリーは、頂点の数を1つ減らしてエッジを1つ減らすだけです.まず、クルーズカール:エッジの重み値を小さくから大きく見て、ループを生成しない場合は、現在のエッジを生成ツリーに追加します.ループが発生するか否かをどのように判断するかは,頂点vとuを接続する辺eを樹種に加えると仮定し,uとvが同じ連通成分に含まれていなければ,eを加えてもループは発生しない.2つの頂点が1つの連通成分にあるかどうかを判断するには、セットを調べます.複雑度O(E*log V)Eは辺の個数、Vは頂点の個数である.###テンプレートコード:

struct edge
{
    int u,v,cost;
};
bool cmp1(const edge &a,const edge &b)
{
    return a.cost=n-1)
                break;
        }
    }
    return res;
}

###プリム###コードテンプレート:

int prime()
{
    for(int i=1;i<=n;i++)
    {
        mincost[i]=INF;
        used[i]=false;
    }
    mincost[1]=0;
    int res=0;
    while(true)
    {
        int v=-1;
        for(int i=1;i<=n;i++)
        {
            if(!used[i]&&(v==-1||mincost[i]