基于邻接表的图BFS遍历结果顺序不符问题排查

嘿，我搞清楚问题所在了！核心原因是你构建邻接表时，新节点的插入顺序和边的创建顺序是反向的，而BFS是严格按照邻接表的顺序来遍历邻接点并加入队列的，这就导致了遍历结果和你的预期不一致。

我们来拆解你的Connect函数逻辑：
当你调用Connect(before, data)添加一条边时，你会创建一个新的顶点节点，然后直接把它插到邻接表的表头（也就是temp->next = adjacent[first].head; adjacent[first].head = temp;这两行）。举个具体的例子：

1. 先调用Connect(2, 0)：此时adjacent[2].head指向的是存储0的节点；
2. 再调用Connect(2, 3)：新创建的3节点会被放到adjacent[2].head的位置，原来的0节点变成它的后继。

这就导致2的邻接表顺序是3 → 0，而不是你添加边的顺序0 → 3。当BFS遍历2的邻接点时，会先访问3，再访问0，最终输出顺序就变成了2 3 0 1，和你的预期完全相反。

第二个测试场景也是同样的道理：你添加边的顺序是1-2、1-5、1-4，但因为每次插表头，1的邻接表顺序会变成4 →5 →2，所以BFS会先处理4，再5，再2，这就和你预期的1 2 4 5...不符了。

解决方案：把邻接表的插入方式改成表尾插入 #

要让BFS的遍历顺序和你添加边的顺序一致，你需要把新的邻接点插到邻接表的表尾，而不是表头。修改你的Connect函数即可：

void Graph::Connect(int first, int second) {
    if (first == second) {
        return; // 跳过自环，保持你原来的逻辑
    }

    // 给first的邻接表添加second节点（表尾插入）
    Vertex* secondVertex = Add_Vertex(second);
    if (adjacent[first].head == nullptr) {
        adjacent[first].head = secondVertex;
    } else {
        Vertex* temp = adjacent[first].head;
        // 找到表尾节点
        while (temp->next != nullptr) {
            temp = temp->next;
        }
        temp->next = secondVertex;
    }

    // 给second的邻接表添加first节点（表尾插入）
    Vertex* firstVertex = Add_Vertex(first);
    if (adjacent[second].head == nullptr) {
        adjacent[second].head = firstVertex;
    } else {
        Vertex* temp = adjacent[second].head;
        while (temp->next != nullptr) {
            temp = temp->next;
        }
        temp->next = firstVertex;
    }
}

这样修改后，邻接表中节点的顺序就和你添加边的顺序完全一致了，BFS的遍历结果也会符合你的预期。

另外还有个小提醒：你现在每次调用Connect都会创建新的Vertex节点，哪怕这个节点已经在邻接表里了，这会造成不必要的内存浪费。可以考虑加个检查逻辑，先判断邻接表中是否已经存在该节点，避免重复创建。

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