最小生成ツリー0.2

最小生成ツリー
0.2
目次

最小生成ツリー

基本概念

Primeアルゴリズム

基本構想

実装コード

最適化案

Kruscalアルゴリズム

コード実装

基本概念

                      ,            .            :     .

Primeアルゴリズム

           O(v^2),   O(e*log2v).e- ,v- .

基本的な考え方

ルートノード

として点を選択する.

は、その点に接続する各エッジを列挙し、配列

に格納する.

は、記憶するある点に到達するエッジよりも列挙されたエッジが短い場合に更新する.

配列から最短エッジ拡張を選択し、残りのエッジ

を保持する.

最短総額にこの辺権値

を加算

エッジがないか点がないまで2-5を繰り返す

.
インプリメンテーションコード

void prime()
{
    bool v[n+1]={0};
    int d[n+1];//            
    meeset(d,1,sizeof(d));
    q.push(1);
    d[1]=0;
    while(!q.empty())
    {
        int x=q.front(),mi=999999,co=0;
        q.pop();
        v[x]=true;
        for(int i=1;i<=n;i++)//     
            if(mi>d[t])
            {
                mi=d[t];
                co=t;
            }
        if(!co) return;
        ans+=mi;
        q.push(co);
        for(int i=1;i<=a[co][0];i++)
        //a[co][i]   co    ,a[i][0]   
            if(!v[a[co][i]]&&c[co][a[co][i]]

最適化シナリオ
miの所望値は常にd[]の最小値であることが明らかである.二重フォークスタックの最適化を導入する、ヘッドを取るたびによい.複雑度O(e*logv).

struct R
{
    int co,w;
}
priority_queueq;
void prime()
{
    bool v[n+1]={0};
    R t;
    t.w=0;
    t.co=1;
    q.push(t);
    while(!q.empty())
    {
        R x=q.top();
        q.pop();
        v[x.co]=true;
        if(!x.co) return;
        ans+=x.w;
        for(int i=1;i<=a[co][0];i++)
            if(!v[a[x.co][i]])
            {
                t.w=c[x.co][a[x.co][0]];
                t.co=a[x.co][i];
                q.push(t);
            }
    }
}

Kruscalアルゴリズム

Kruscalアルゴリズムは貪欲な思想を用い,毎回最短辺を加え,メンテナンスツリーの構造

を用いて調べ集めた.

Kruscalアルゴリズムは疎図、複雑度O(e*loge)に適用する.

コード実装

#include 
//      ,     
int find(int x);
bool he(int x,int y)//      
void Kruscal()
{
    int e=0;
    sort();
    for(int i=1;i<=ro&&e<=n-1;i++)
        if(he(a[i].co,a[i+1].co))
        {
            ans+=a[i].c;
            e++;
        }
    if(e1)//    
        ans=-1;
}