在图形上执行 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 以将新节点添加到 Neighbors 列表的 end，而不是比开始的时候.

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

Value order not as expected, after performing a BFS on the graph?

c++

graph

breadth-first-search

adjacency-list

data-structures