4

次のグラフがあり (矢印は接続の方向を示します)、黒いノードのクラスターのサイズを数えたいとします。

無向正方格子グラフ。

これは、各ノードが隣接ノードのリストを持つように、ノードのリストとしてメモリに編成されます。node[i].State == 1任意のノードから始めて、指定されたノードも状態 1 である場合、何個のノードが を持っているかを数えたいと考えていますNode.GetClusterSize()。 ):

public class Node
{
    public Int32 State { get; private set; } // 0 = white; 1 = black;

    public Boolean Visited { get; private set; }

    public List<Node> InputNeigh { get; private set; } // list of references to
                                                       // neighbors nodes

    public Int32 GetClusterSize()
    {
        this.Visited = true;
        if (this.State == 1)
        {
            Int32 s = 1, i = 0;
            while (i < this.InputNeigh.Count)
            {
                if (!this.InputNeigh[i].Visited)
                {
                    s += this.InputNeigh[i].GetClusterSize();
                }
                i++;
            }
            this.Visited = false; // this is an important step, I'll explain why
            return s;
        }
        else
        {
            return 0;
        }
    }
    public void Evolve() { /* doesn't matter for this question */ }
}

ここで、メイン シミュレーションのすべてのタイム ステップですべてのノードのクラスター サイズをカウントするため、ノードを未訪問としてマークする必要があります(ノードの状態は時間とともに変化するため、次のタイム ステップでクラスターのサイズが変わる可能性があります)。

この問題は、オブジェクトのフラグの代わりに、特定の要素が node :に対応するNodeブール値の外部リストがあり、このリストを function への参照として渡すと、簡単に修正できます。しかし、その後、タイムステップごとにこのリストをリセットする必要があり、コードの速度が低下します (パフォーマンスが重要です!)。iiList<Boolean> nodeStatusNode.GetClusterSize()

上記のコードの失敗は、隣接ノードを反復処理した後、ノードを未訪問として正確にマークしていることです。この状況は、次のツリーでよりよく視覚化されます (左から右にアクセスし、最初に を呼び出すと仮定しますnode[0].GetClusterSize())。

クラスターサイズをカウントするアルゴリズム

深さ優先検索は、上記のツリーの青いパスを反復し、ノード に到達すると、3すべての隣接ノードが既に訪問されていることを認識し、3未訪問としてマークして を返しますs = 1。3の次の隣人2が訪問され、未訪問として3マークされているため (既に訪問されていますが)、再度チェックし、アルゴリズムはStackOverflow例外に入るか、せいぜい間違ったサイズのクラスターを返します。

したがって、私は2つのアイデアを思いつきましたが、それらを実装する方法はまだわかりません:

1) 幅優先検索アルゴリズムを実装します。この概念を提示された状況に適用する方法はわかりませんが。

2) 深さ優先検索を (再帰的ではなく) シーケンシャルに実装します。それにもかかわらず、私はそれがどのように可能か想像できません。

この問題を無効にするアイデアはありますか? なにか提案を？

前もって感謝します！

PS:グラフはこの例よりもはるかに大きくなる可能性があり、ネットワーク内に複数の黒いクラスターが同時に存在し、互いに切断されている可能性があります。したがって、単に黒い要素を数えるという問題ではありません。

4

3 に答える 3

3

リストを使用して Visited フラグをリセットする順次幅優先検索:

public int GetClusterSize()
{
    if (State != 1) return 0;

    List<Node> cluster = new List<Node>();

    Stack<Node> stack = new Stack<Node>();
    stack.Push(this);
    while (stack.Count > 0)
    {
        Node node = stack.Pop();
        if (node.Visited) continue;

        node.Visited = true;
        cluster.Add(node);
        foreach (var neigh in node.InputNeigh)
        {
            if (neigh.State == 1 && !neigh.Visited)
            {
                stack.Push(neigh);
            }
        }
    }

    int clusterSize = cluster.Count;
    foreach (var node in cluster)
    {
        node.Visited = false;
    }

    return clusterSize;
}

別の方法として、訪問済みフラグの代わりに世代タグを使用することもできます。世代がターゲットと一致する場合、ノードは訪問済みと見なされます。このアプローチでは、アルゴリズムの終了後に値をリセットする必要はありません。

private static int NextGeneration = 0;

public int Generation { get; private set; }

public int GetClusterSize()
{
    return GetClusterSizeInternal(NextGeneration++);
}

private int GetClusterSizeInternal(int target)
{
    if (State != 1) return 0;

    Generation = target;

    int sum = 0;
    foreach (var neigh in InputNeigh)
    {
        if (neigh.State == 1 && neigh.Generation != target)
        {
            sum += neigh.GetClusterSizeInternal(target);
        }
    }

    return sum;
}

同じですが、再帰はありません:

private static int NextGeneration = 0;

public int Generation { get; private set; }

public int GetClusterSize()
{
    if (State != 1) return 0;

    int target = NextGeneration++;

    Stack<Node> stack = new Stack<Node>();
    stack.Push(this);

    int count = 0;
    while (stack.Count > 0)
    {
        Node node = stack.Pop();
        if (node.Generation == target) continue;

        node.Generation = target;

        count++;
        foreach (var neigh in node.InputNeigh)
        {
            if (neigh.State == 1 && neigh.Generation != target)
            {
                stack.Push(neigh);
            }
        }
    }

    return count;
}
于 2013-09-30T21:21:05.667 に答える