遍历以邻接矩阵表示的图

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

任何帮助都将不胜感激！

此矩阵所代表的图形：

- JLott

---

我对您的邻接矩阵有些困惑，为什么它不是布尔矩阵？ - Eric Lippert

这是一个带权图。我会发布它所代表的图像。 - JLott

明白了。有些人使用邻接图和计数来表示两个节点之间有多少边，但在您的情况下这并不合理。 - Eric Lippert

http://pastebin.com/zYZ7MbgR，这是使用Int32而不是Vertex实现Eric Lippert的可能方法之一。 - Thanatos

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 ；这通常是使用邻接矩阵的方法。我们想要输入一个顶点--一个int--并返回其相邻顶点的序列。

我们有一个数组，具有该属性，即如果顶点j 是顶点i的邻居，则 array [i，j] 为非零。

同样，从抽象到具体实现：

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迭代器通常更简单，但初学者经常很难理解控制流。 尝试两种方式编写并查看效果。

- Eric Lippert

---

哈哈 是的，在这种情况下，这才是我的真正问题。:P - JLott

出于好奇，有哪个问题无法通过增加抽象化来解决？ - JLott

我的程序包含了太多的抽象概念。 - Eric Lippert

好的，我不会撒谎...我甚至不知道从哪里开始构建这个ListNeighbors<Vertex>方法...我已经尝试过查找，但是在这些情况下Google并不是最好的。 - JLott

@JLott：我添加了一些提示。当我作为实习生开始时，这就是我编写所有程序的方式，就像你在这里看到的那样。首先编写一个什么也不做但具有正确签名的方法，然后填写高级描述，接着将其分解成步骤，并不断细分，直到我能够编写每个步骤的代码。 - Eric Lippert