邻接矩阵BFS遍历结果异常：如何用visited变量修正输出

嘿，你的问题核心就是BFS遍历的时候没标记已经访问过的节点，导致有些节点被反复塞进队列、反复输出，所以才会出现123465247这种带重复数字的结果。要得到干净的1234657，咱们得加个visited数组来“盯紧”哪些节点已经处理过，绝不让它们再来凑热闹。

第一步：先把visited变量安排上 #

在bfs方法里，声明一个布尔类型的数组visited，长度和你的顶点列表graph1VertexList一样长，初始值全是false——意思就是一开始所有节点都没被碰过。

第二步：给BFS逻辑“补漏洞” #

正确的BFS流程得这么走：

1. 先把起始节点（也就是索引0对应的数字1）塞进队列，同时立刻标记它为已访问——别等，不然后面可能被重复加进来。
2. 只要队列里还有节点，就把队首的节点拿出来输出。
3. 接着遍历这个节点的所有邻居，但凡哪个邻居还没被访问过，就先标记它为已访问，再塞进队列里。

这样一来，每个节点只会被处理一次，自然就不会有重复输出了。

修正后的完整代码 #

using System;
using System.Collections.Generic;

class Graph {
    public int[] graph1VertexList = new int[] {1,2,3,4,5,6,7};
    public int[,] graph1=new int[7,7];
    
    public Graph() {
        // 初始化邻接矩阵，和你原来的配置一致
        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() {
        // 初始化visited数组，长度和顶点数一致，默认全为未访问状态
        bool[] visited = new bool[graph1VertexList.Length];
        // 用队列存储待访问的节点索引（邻接矩阵是按索引关联节点的）
        Queue<int> queue = new Queue<int>();
        
        // 从第一个节点（索引0，对应数值1）开始遍历
        int startIndex = 0;
        queue.Enqueue(startIndex);
        visited[startIndex] = true; // 入队时就标记已访问，从根源避免重复
        
        while (queue.Count > 0) {
            int currentIndex = queue.Dequeue();
            // 输出当前节点的数值
            Console.Write(graph1VertexList[currentIndex]);
            
            // 遍历所有可能的邻接节点
            for (int i = 0; i < graph1VertexList.Length; i++) {
                // 如果当前节点和i节点有连接，且i节点未被访问过
                if (graph1[currentIndex, i] == 1 && !visited[i]) {
                    visited[i] = true; // 先标记再入队，防止后续重复添加
                    queue.Enqueue(i);
                }
            }
        }
    }
    
    // 测试入口，运行就能看到正确输出
    static void Main(string[] args) {
        Graph myGraph = new Graph();
        myGraph.bfs(); // 现在输出就是1234657啦！
    }
}

为啥原来会重复？ #

给你掰扯清楚：原来的代码没标记已访问，当处理节点4的时候，它的邻居节点2还没被标记，于是又把2塞进队列了，后面就又输出了2、4，最后才轮到7。现在我们在节点第一次入队时就标记为已访问，后面再碰到这个节点直接跳过，自然就不会重复输出了。

内容的提问来源于stack exchange，提问作者beginner