c# - 遍历以邻接矩阵表示的图

Question

我想使用深度优先和广度优先方法来遍历图形。我以前在一个简单的节点列表上做过这个，但我从来没有用邻接矩阵尝试过，老实说，我什至不知道从哪里开始。

这是我的矩阵:

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;
        }

如有任何帮助，我们将不胜感激!

这个矩阵表示的图:

Answer 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)给定你的邻接矩阵？

两种可能的调查解决方案:

• 制作Graph.ListNeighbours(Vertex)方法返回 List<Vertex> .构建列表并分发。

• 让它返回IEnumerable<Vertex>并使用 yield return产生一系列相邻顶点。

---

更新:好的，那么我们实际上如何从邻接矩阵中生成一系列邻居？

假设每个顶点都有编号，所以 Vertex真的是int ;传统上，这就是邻接矩阵的处理方式。我们想要接收一个顶点——一个整数——并返回一个顶点序列，这些顶点是它的邻居。

我们有一个数组，其属性为 array[i, j]如果顶点 j 非零是顶点 i 的邻居.

再次，从抽象开始，朝着实现的方向努力:

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迭代器往往更简单，但新手程序员通常很难确定控制流。 尝试用两种方式编写，看看效果如何。