邻接矩阵中的 BFS
BFS in Adjacency Matrix
使用下面的代码,当我调用 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]);
}
}
}
}
}
你应该引入一个布尔数组来表示某个顶点是否已经被访问过。此外,应该检查数组是否跟随边缘并在这样做之后更新。这可以按如下方式完成。
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
方法时,我得到了 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]);
}
}
}
}
}
你应该引入一个布尔数组来表示某个顶点是否已经被访问过。此外,应该检查数组是否跟随边缘并在这样做之后更新。这可以按如下方式完成。
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]);
}
}
}
}