邻接矩阵中的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]);

            }

        }

    }

}