0

l - adiacency リスト
x - 開始頂点
dfst、q - 頂点サイズの空の配列

std::list <int> q;
std::vector<bool> visited(cols + 1); 
for(int i = 0; i < cols; i++) visited[i] = false;
visited[x] = true;
if(!l[x].empty())
for(std::list<int>::iterator i = l[x].begin(); i != l[x].end(); i++)
{
    q.push_back(x); q.push_back(* i);
}
while(!q.empty())
{
    y = q.back(); q.pop_back();
    x = q.back(); q.pop_back();
    if(!visited[y])
    {
        visited[y] = true;
        if(!l[y].empty())
        for(std::list<int>::iterator i = l[y].begin(); i != l[y].end(); i++)
        {
            q.push_back(y); q.push_back(* i);
        }
        dfst[x].push_back(y);
        dfst[y].push_back(x);
    }
}

なぜこれが間違った結果をもたらすのかわかりません...このアルゴリズムに精通しているかどうかはわかりませんが、知っている場合は、ここで何が問題なのかがわかると思います.

編集：

隣接リスト:
1: 2、3
2: 3
3: 4
4: 3

MST は次のようになります:
1: 2, 3
3: 4

しかし、代わりに:
2: 3
3: 2, 4
4: 3

そして、現在のコードは次のとおりです:(必要な場所に括弧を使用しました):

std::list <int> q;
std::vector<bool> visited(cols + 1); 
for(int i = 0; i < cols; i++) visited[i] = false;
visited[x] = true;
if(!l[x].empty())
{
    for(std::list<int>::iterator i = l[x].begin(); i != l[x].end(); i++)
    {
        q.push_back(x); q.push_back(* i);
    }
    while(!q.empty())
    {
        y = q.back(); q.pop_back();
        x = q.back(); q.pop_back();
        if(!visited[y])
        {
            visited[y] = true;
            if(!l[y].empty())
            for(std::list<int>::iterator i = l[y].begin(); i != l[y].end(); i++)
            {
                if(!visited[*i])
                {q.push_back(y); q.push_back(* i);}
            }
            dfst[x].push_back(y);
            dfst[y].push_back(x);
        }
    }
}
4

2 に答える 2

0

私はあなたのコードを調べましたが、正しいようです。ただし、入力ツリーにサイクルがある場合は、複数の DFS ツリーがあることに注意してください。得られるツリーは、頂点を処理する順序によって異なります。おそらくあなたの入力にはサイクルがありますか？その場合、コードがソリューションで処理される順序とは異なる順序でノードを処理している可能性があります。

たとえば、次の入力ツリーの隣接リストを使用します。ノードには文字が付けられています。

a: b,c
b: a,d
c: a,c,e
d: b,c,e
e: c,d

a から始めて、アルファベット順に基づいて次のノードの隣接リストを調べると、次の DFS ツリーが得られます。

a: b
b: a,d
c: d,e
d: b,d
e: c

ただし、アルゴリズムを使用すると、次のようになります。

a: c
b: d
c: a,e
d: b,e
e: c,d

これが発生している場合は、おそらく再帰的なアプローチを試してください。

ただし、これはあなたの問題ではない可能性があるため、いくつかのサンプル入力と出力を確認すると、この質問の回答にさらに役立ちます。

編集:無向グラフなど、サイクルが双方向の場合に、サイクルのあるグラフ内の複数の DFS ツリーが適用されることを明確にする必要があります。要点は、正しいと識別されたものと同じではなく、正しい DFS ツリーを見つけている可能性があるということです。

EDIT（再度）：別の問題：コードにステートメントがあるため、アルゴリズムは無向グラフ用dfst[x].push_back(y); dfst[y].push_back(x);のように見えますが、例で指定された入力グラフは有向のように見えます。2 番目のステートメント ( dfst[y].push_back(x);) を削除すると、これが修正されます。

于 2013-06-17T21:03:15.067 に答える