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

计算机科学中的每一个问题，除了一个之外，都可以通过添加更多抽象来解决。

首先以最抽象的方式编写广度优先遍历：

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；传统上，这就是邻接矩阵的处理方式。我们想要接收一个顶点——一个整数——并返回一个顶点序列，这些顶点是它的邻居。

如果 vertex是 vertex 的邻居，我们有一个具有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 回答