邻接矩阵中的 BFS

Question

使用下面的代码，当我调用 bfs 方法时，我得到了 123465247 的结果。我应该如何声明和使用 visited 变量，以便输出变为 1234657？

class Graph
{
    public int[] graph1VertexList = new int[] {1,2,3,4,5,6,7};
    public int[,] graph1=new int[7,7];

    public Graph()
    {
        //for the graph1
        graph1[0, 1] = 1;
        graph1[0, 2] = 1;
        graph1[1, 3] = 1;
        graph1[2, 5] = 1;
        graph1[3, 4] = 1;
        graph1[4, 1] = 1;
        graph1[5, 3] = 1;
        graph1[5, 6] = 1;
    }


    public void bfs()
    {
        Console.Write(graph1VertexList[0]);//print the first value
        for(int i = 0; i < graph1VertexList.Length; i++)
        {
            for(int z = 0; z < graph1VertexList.Length; z++)
            {
                if (graph1[i, z] == 1)
                {
                    Console.Write(graph1VertexList[z]);
                }
            }
        }
    }

}

Answer 1

你应该引入一个布尔数组来表示某个顶点是否已经被访问过。此外，应该检查数组是否跟随边缘并在这样做之后更新。这可以按如下方式完成。

public int[] graph1VertexList = new int[] { 1, 2, 3, 4, 5, 6, 7 };
public int[,] graph1 = new int[7, 7];

public bool[] visited = new bool[7]; // new array, initialized to false

public void bfs()
{
    Console.Write(graph1VertexList[0]);//print the first value
    for (int i = 0; i < graph1VertexList.Length; i++)
    {
        for (int z = 0; z < graph1VertexList.Length; z++)
        {
            if (graph1[i, z] == 1 && !visited[z])   // check for visit
            {
                visited[z] = true;                  // mark as visited
                Console.Write(graph1VertexList[z]);
            }
        }
    }
}

邻接矩阵中的 BFS

BFS in Adjacency Matrix

c#

breadth-first-search

adjacency-matrix