Значение порядка не так, как ожидалось, после выполнения BFS на графике? - PullRequest
Новая
       72

Значение порядка не так, как ожидалось, после выполнения BFS на графике?

0 голосов
/ 09 марта 2019

Я пытаюсь создать график на основе списков смежности. Это структура графика. 

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.

1 Ответ

1 голос
/ 09 марта 2019

В BFS вы используете очередь для отслеживания узлов, которые вам необходимо посетить. Вы вытягиваете следующий узел спереди и добавляете новые узлы для посещения до конца.

Вместо этого вы хотите использовать стек - добавляйте и удаляйте узлы с конца. Это изменит порядок посещения узлов заказа и изменит вывод, который вы генерируете.

Кроме того, вы можете оставить код в BFS без изменений и изменить Connect, чтобы добавить новые узлы в конец списка соседей, а не в начале.

...