4

特定のグラフの MST を見つけるためのクルスカルのアルゴリズムを研究していましたが、最初はすべての頂点をフォレストと見なす必要があるという基本的な概念を理解しています。その後、最小エッジを見つけて、エッジの頂点を 1 つのツリーに結合する必要があります。そして、すべての頂点を含むツリーが 1 つだけになるまで、これを再帰的に実行します。

そして、このアルゴリズムの次の実装に出くわしました。

#include<iostream.h>

int p[10];

void kruskal(int w[10][10],int n)
{
    int min,sum=0,ne=0,i,j,u,v,a,b;
    for(i=1;i<=n;i++)
    p[i]=0;
    while(ne<n-1)
    {
        min=999;
        for(i=1;i<=n;i++)
        for(j=1;j<=n;j++)
        {
            if(w[i][j]<min)
            {
                    min=w[i][j];
                u=a=i;
                v=b=j;
            }
        }
        while(p[u])
            u=p[u];
        while(p[v])
            v=p[v];
        if(u!=v)
        {
            ne++;
            sum+=min;
            cout<<"\nedge "<<a<<"-->"<<b<<" is "<<min;
            p[v]=u;
        }
        w[a][b]=w[b][a]=999;
    }
    cout<<"\nmin cost spanning tree= "<<sum;
}

void main()
{
    int w[10][10],n,i,j;
    clrscr();
    cout<<"enter no.of vertices\n";
    cin>>n;
    cout<<"enter weight matrix\n";
    for(i=1;i<=n;i++)
        for(j=1;j<=n;j++)
            cin>>w[i][j];
    for(i=1;i<=n;i++)
        for(j=1;j<=n;j++)
            if(w[i][j]==0)
                w[i][j]=999;
    kruskal(w,n);
}

私が理解していないのは、次の必要性です：

while(p[u])
    u=p[u];
while(p[v])
    v=p[v];

これら 2 つの while ループは正確には何をするのでしょうか?

編集：そしてまた必要性-

for(i=1;i<=n;i++)
        for(j=1;j<=n;j++)
            if(w[i][j]==0)
                w[i][j]=999;
4

1 に答える 1

9

Kruskals アルゴリズムは、特定のエッジを追加したいと考えています(a, b)。ただし、そうする前に、aとbが既に接続されているかどうかを確認する必要があります (接続されている場合、エッジは追加されません)。

あなたの与えられた4つの行は、すでに接続されているかどうかを確認するだけですa。b

これを完全に理解するには、次のことを知っておく必要がありuます。配列には連結要素が格納されます。つまり、 の連結成分にあります。最初に、各頂点は、 で示される独自の接続コンポーネントを表すことに注意してください(つまり、コンポーネントは 0 に設定されています)。vabpp[x] = yxyp[n1] = 0, p[n2] = 0, ...

さらに、各連結要素は 1 つの頂点で表されることに注意してください。

がコンポーネントの代表者であるかどうかをwhile(p[u])チェックuします (uが代表者 iffp[u] == 0であり、これにより while ループが停止します)。したがって、uがコンポーネントの代表である場合は停止します。

より興味深い部分は次のとおりuです。その後、適宜更新されます ( )。p[u]uuu=p[u]

このゲーム全体をグラフと見なすことができます。連結要素を表す次の表を考えてみましょう。

   u  |  1  2  3  4  5  6  7  8  9
 p[u] |  2  0  2  3  2  1  0  9  0

これは、そのノードが で1表されるコンポーネントに属していることを意味します2。4は で表されるコンポーネントに3属し、それ自体は で表されるコンポーネントに属します2。2エントリがあるため、 は代表であることに注意してください0。

これをグラフとして視覚化できます。

  2      7  9
 /|\        |
1 3 5       8
| |
6 4

ご覧のとおり、現在、それぞれ 2、7、9 で表される 3 つのコンポーネントがあります。

新しいエッジを追加したい場合は(6,7)、代表者 2 と 7 がそれぞれ見つかるまで「ツリーを上る」必要があります。ご覧のとおり、代表者は同じではなく、エッジを追加します。

別の例: edge を追加したい(6, 5)ので、「ツリーを上って」2両方のケースで代表者を見つけます。したがって、エッジを追加しません。

「木に登る」は、あなたが明示的に述べたセリフによって行われます。

于 2011-11-20T12:06:25.743 に答える