在图表上执行BFS后，值顺序不符合预期？

Question

我正在尝试基于邻接列表创建图表。这是图的结构。

class Graph{
private:
    struct Vertex
    {
        int data;
        Vertex *next;
        set<int> anti;
    };
    struct Neighbors
    {
        Vertex *head;
    };
public:
    int Limit;
    list<int> print_list;
    Neighbors *adjacent;
    Graph(int Limit);
    Vertex* Add_Vertex(int data);
    void Connect(int before, int data);
    void Display();
    list<int> BFS(int v);
    list<int> DFS(int source);
};

代码编译完全正常，但是当我尝试复制为LINK或任何其他页面创建边缘的顺序时，我总是得到不同的顺序。

我的问题是，是什么导致我的命令与他们的不同？我认为我顺利地遵循逻辑，但不是产生2 0 3 1，而是产生2 3 0 1.尽可能地，我希望这些输出类似。

---

边缘和创作：

Graph::Vertex* Graph::Add_Vertex(int data)
{
    //Initialize vertex
    Vertex* temp = new Vertex;
    temp->data = data;
    temp->next = NULL;
    return temp;
}
void Graph::Connect(int first, int second)
{
    Vertex *temp;
    //Create a vertex and get pointer for second

    if (first != second) {
        //Create a vertex and get a pointer for first
        temp = Add_Vertex(first);
        //Connect created node to second vertex
        temp->next = adjacent[second].head;
        adjacent[second].head = temp;
    }
    temp = Add_Vertex(second); 
    //Connect created node to first vertex
    temp->next = adjacent[first].head; 
    adjacent[first].head = temp;


}

BFS实施（不包括主要电话）：

list<int> Graph::BFS(int from) {
    print_list.clear();
    bool *visited = new bool[Limit];
    for (int i = 0; i < Limit; i++)
        visited[i] = false;

    list<int> queue;
    visited[from] = true;
    queue.push_back(from);

    while (!queue.empty())
    {
        from = queue.front();
        print_list.push_back(from);
        queue.pop_front();

        Vertex *Displaying = adjacent[from].head;
        while (Displaying)
        {
            int adjacent_node = Displaying->data;
            if (!visited[adjacent_node])
            {
                visited[adjacent_node] = true;
                queue.push_back(adjacent_node);
            }
            Displaying = Displaying->next;
        }
    }
    return print_list;
}

另一个测试：

1 2, 2 3, 1 5, 1 4, 4 7, 7 8, 8 9, 2 6, 5 7

预期：

1 2 4 5 3 6 7 8 9

实际：

1 4 5 2 7 6 3 8 9

起始顶点为1。

Answer 1

在BFS中，您使用队列来跟踪您需要访问的节点。您从前面拉出下一个节点，并添加要访问的新节点到最后。

您想要使用的是堆栈 - 从末尾添加和删除节点。这将在访问的订单节点周围发生变化，并更改您生成的输出。

或者，您可以保持BFS中的代码不变，并更改Connect以将新节点添加到“邻居”列表的末尾，而不是在开头。