4

グラフをトラバースするために、深さ優先法と幅優先法を使用したいと思います。これは以前にノードの単純なリストで行ったことがありますが、隣接行列で試したことがなく、正直なところどこから始めればよいのかさえわかりません。

これが私のマトリックスです：

999999999 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 
1 999999999 0 3 1 0 0 0 0 0 0 0 0 0 0 0 
1 0 999999999 3 0 1 0 0 0 0 0 0 0 0 0 0 
0 3 3 999999999 0 0 0 8 0 0 0 0 0 0 0 0 
0 1 0 0 999999999 0 1 3 0 0 0 0 0 0 0 0 
0 0 1 0 0 999999999 0 3 1 0 0 0 0 0 0 0 
0 0 0 0 1 0 999999999 0 0 3 0 1 0 0 0 0 
0 0 0 8 3 3 0 999999999 0 8 8 0 3 0 0 0 
0 0 0 0 0 1 0 0 999999999 0 3 0 0 1 0 0 
0 0 0 0 0 0 3 8 0 999999999 0 0 0 0 3 0 
0 0 0 0 0 0 0 8 3 0 999999999 0 0 0 0 3 
0 0 0 0 0 0 1 0 0 0 0 999999999 0 0 1 0 
0 0 0 0 0 0 0 3 0 0 0 0 999999999 0 1 1 
0 0 0 0 0 0 0 0 1 0 0 0 0 999999999 0 1 
0 0 0 0 0 0 0 0 0 3 0 1 1 0 999999999 0 
0 0 0 0 0 0 0 0 0 0 3 0 1 1 0 999999999

このマトリックス（C＃）を作成した方法は次のとおりです。

private static int[,] CreateMatrix()
        {
            int A = 0;
            int B = 1;
            int C = 2;
            int D = 3;
            int E = 4;
            int F = 5;
            int G = 6;
            int H = 7;
            int I = 8;
            int J = 9;
            int K = 10;
            int L = 11;
            int M = 12;
            int N = 13;
            int O = 14;
            int P = 15;

            int[,] matrix = new int[16, 16];

            matrix[A, B] = 1;
            matrix[A, C] = 1;
            matrix[B, D] = 3;
            matrix[B, E] = 1;
            matrix[C, D] = 3;
            matrix[C, F] = 1;
            matrix[D, H] = 8;
            matrix[E, G] = 1;
            matrix[E, H] = 3;
            matrix[F, H] = 3;
            matrix[F, I] = 1;
            matrix[G, J] = 3;
            matrix[G, L] = 1;
            matrix[H, J] = 8;
            matrix[H, K] = 8;
            matrix[H, M] = 3;
            matrix[I, K] = 3;
            matrix[I, N] = 1;
            matrix[J, O] = 3;
            matrix[K, P] = 3;
            matrix[L, O] = 1;
            matrix[M, O] = 1;
            matrix[M, P] = 1;
            matrix[N, P] = 1;


            matrix[B, A] = 1;
            matrix[C, A] = 1;
            matrix[D, B] = 3;
            matrix[E, B] = 1;
            matrix[D, C] = 3;
            matrix[F, C] = 1;
            matrix[H, D] = 8;
            matrix[G, E] = 1;
            matrix[H, E] = 3;
            matrix[H, F] = 3;
            matrix[I, F] = 1;
            matrix[J, G] = 3;
            matrix[L, G] = 1;
            matrix[J, H] = 8;
            matrix[K, H] = 8;
            matrix[M, H] = 3;
            matrix[K, I] = 3;
            matrix[N, I] = 1;
            matrix[O, J] = 3;
            matrix[P, K] = 3;
            matrix[O, L] = 1;
            matrix[O, M] = 1;
            matrix[P, M] = 1;
            matrix[P, N] = 1;

            for (int i = 0; i < 16; i++)
            {
                for (int j = 0; j < 16; j++)
                {
                    if (matrix[i, j] == 0)
                        matrix[i, j] = 0;

                    if (i == j)
                        matrix[i, j] = 999999999;

                }
            }

            return matrix;
        }

どんな助けでもいただければ幸いです!!

この行列が表すグラフ：

ここに画像の説明を入力してください

4

1 に答える 1

19

コンピュータサイエンスのすべての問題は、1つを除いて、抽象化を追加することで解決できます。

可能な限り最も抽象的な方法で幅優先探索を書くことから始めます。

void BreadthFirstTraversal(Graph graph, Vertex start)
{
    /* A miracle happens */
}

やりたいことをする方法があります。まだ書かれていないことを除いて。したがって、少し抽象化を少なくして記述してください。

void BreadthFirstTraversal(Graph graph, Vertex start)
{
    /* make a queue of vertices */
    /* make a mark set of vertices */
    /* enqueue and mark start */
    /* while the queue is not empty */
        /* dequeue a vertext */
        /* enqueue and mark all the unmarked neighbours of the vertex */
}

続けて、ますます抽象化を削除します。

void BreadthFirstTraversal(Graph graph, Vertex start)
{
    var queue = new VertexQueue();
    var markSet = new VertexMarkSet();
    queue.Enqueue(start);
    markSet.Add(start);
    while(queue.NotEmpty())
    {
        var vertex = queue.Dequeue();
        foreach(Vertex neighbour in graph.ListNeighbours(vertex))
        {
            if (!markSet.Contains(neighbour))
            {
                markSet.Add(neighbour);
                queue.Enqueue(neighbour);
            }
        }
     }
}

これで、内部での表現に関係なく、どのグラフでも機能するアルゴリズムができました。だからあなたがしなければならないのは書くことだけでListNeighbours(Vertex)あり、あなたは終わりです。（キューとセットの記述方法をすでに知っているか、基本クラスライブラリに付属している型を使用する意思があると仮定します。）それをどのように行いますか？

そこで抽象化をどのように使用したかわかりますか？隣接行列であるか隣接リストであるかは本当に気にしません。気になるのは、グラフが頂点の隣接行列を提供するサービスを提供することだけです。

ListNeighbours(Vertex)では、隣接行列を考慮 して、どのように記述しますか？

調査する2つの可能な解決策：

  • メソッドGraph.ListNeighbours(Vertex)がを返すようにしList<Vertex>ます。リストを作成して配布します。

  • それを返して、隣接する頂点のシーケンスを生成するためにIEnumerable<Vertex>使用します。yield return

更新：わかりました。では、隣接行列から実際に隣接行列を作成するにはどうすればよいでしょうか。

すべての頂点に番号が付けられていると仮定しましょう。Vertex実際にはint; これは伝統的に、隣接行列を使って物事が行われる方法です。頂点（int）を取り込んで、隣接する頂点のシーケンスを返します。

頂点が頂点に隣接しているarray[i, j]場合、ゼロ以外のプロパティを持つ配列があります。ji

繰り返しになりますが、抽象化を開始し、実装に向けて作業を進めてください。

public List<int> ListNeighbours(int vertex)
{
    /* a miracle happens */
}

その奇跡を起こすために私たちは何をする必要がありますか？

public List<int> ListNeighbours(int vertex)
{
    /* create a new list */
    /* for each vertex j in the graph */
        /* if j is a neighbour of i then add it to the list */
    /* return the list */
}

または、を使用yield returnしてシーケンスを作成することもできます。

public IEnumerable<int> ListNeighbours(int vertex)
{
    /* for each vertex j in the graph */
        /* if j is a neighbour of i then yield return j */
}

yield returnイテレータは単純になる傾向がありますが、初心者のプログラマーは制御フローを推測するのに苦労することがよくあります。 両方の方法で書いてみて、どうなるか見てみましょう。

于 2013-03-09T16:13:22.517 に答える