Обход BFS дает неправильный вывод - PullRequest
Новая
       59

Обход BFS дает неправильный вывод

0 голосов
/ 25 октября 2019

Я пытаюсь решить проблему, используя список смежности. Но проблема, с которой я здесь сталкиваюсь, заключается в том, что, когда я пытаюсь вставить элемент в список смежности, он сохраняет значение в последовательности, которую я ввел. Например, для теста: 

5 8 0 1 0 4 1 2 2 0 2 4 3 0 3 2 4 3

Мой вывод: 

0 1 4 2 3

Ожидаемый вывод: 

0 1 2 3 4.

Это потому, что мой список смежности хранитзначение в моде не было введено в отсортированном виде. Как бы я сохранил это в отсортированном виде? Если я сортирую это, это только увеличивает сложность кода. Пожалуйста, помогите. 

#include<bits/stdc++.h>
using namespace std; 
typedef long long int ll;

void addEdge(vector<ll> edges[], ll u, ll v)
{
    edges[u].push_back(v);
    edges[v].push_back(u);
}

void BFS(vector<ll> edges[], ll v, bool * visited, queue<ll> q)
{
    while(!q.empty())
    {
        ll s = q.front();
        cout << s << " ";
        q.pop();
        for(ll i = 0; i < edges[s].size(); i++)
        {
            if(!visited[edges[s][i]])
            {
                visited[edges[s][i]] = true;
                q.push(edges[s][i]);
            }
        }
    }
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    ll v, e;
    cin >> v >> e;

    vector<ll> edges[v];
    for(ll i = 0 ; i < e; i++)
    {
        int x, y;
        cin >> x >> y;
        addEdge(edges, x, y);
    }

    bool * visited = new bool[v];
    memset(visited, false, sizeof(visited));
    queue<ll> q;
    q.push(0);
    visited[0] = true;

    BFS(edges, v, visited, q);
    return 0;
}

1 Ответ

0 голосов
/ 25 октября 2019

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

...