BFS дает ошибку сегментации при создании графа, пытается отладить, не уверен, что происходит не так - PullRequest
Новая
       21

BFS дает ошибку сегментации при создании графа, пытается отладить, не уверен, что происходит не так

0 голосов
/ 21 января 2020

Я начал изучать теорию графов и задавал вопрос от Хакерранка https://www.hackerrank.com/challenges/bfsshortreach/problem, который в основном просит выполнить BFS, пометить все элементы на одном уровне с уровнем 6 * и отметить все -достижимые узлы как -1. Я попытался сделать это следующим образом, при создании моего adjList я получил ошибку сегмента. Неправильный ли доступ ко входу vector<vector<int>> edges? Или что-то еще. Это мой код 2-3 bfs, поэтому я также хотел знать, в порядке ли моя реализация, и делает ли он то, что должен, или я выключен? (Я знаю, что вопрос требует, чтобы ans vector было 1-n, а не порядком посещений, как в настоящее время, может быть, я мог бы использовать карту, или гистограмму, или пару с исходным значением и отсортировать их по секундам позже или что-то в этом роде, Я не разобрался с этой частью) Спасибо.

Код: 

vector<vector<int>> Graph(vector<vector<int>>& edges) {
    vector<vector<int>> ans;
    for(auto i: edges) {
        ans[i[0]].push_back(i[1]);
        ans[i[1]].push_back(i[0]);
    } return ans;
}

vector<int> bfs(int n, int m, vector<vector<int>>& edges, int s) { // no. of vertex, no. of edges, edges, start
    vector<vector<int>> adjList;
    // adjList.resize(n);
    adjList = Graph(edges);
    vector<int> ans(n + 1);
    vector<bool> visited(n + 1);
    queue<int> q;
    visited[s] = true;
    q.push(s);
    int i = 0;
    while(!q.empty()) {
        int temp = q.front(); q.pop();
        // int len = q.size();
        for(int j: adjList[temp]) {
            if(!visited[j]) {
                ans.push_back(6*i);
                visited[j] = true;
                q.push(j);
            }
        } i++;
    }
    for(int i = 1; i <= n; i++) if(i % 6 != 0 && i != s) ans[i] = -1;
    ans.erase(ans.begin() + s);
    return ans;
}

Проверено на 

int main() {
    vector<vector<int>> edges = {{1, 2}, {1, 3} };
    vector<int> som = bfs(4, 2, edges, 1);
    return 0;
}

1 Ответ

0 голосов
/ 21 января 2020

Размер vector<vector<int>> ans должен быть изменен на количество вершин в Graph.

Рабочий код: 

vector<vector<int>> Graph(vector<vector<int>>& edges, int n) {
    vector<vector<int>> ans(n);
    for(auto i: edges) {
        ans[i[0]].push_back(i[1]);
        ans[i[1]].push_back(i[0]);
    } return ans;
}

vector<int> bfs(int n, int m, vector<vector<int>>& edges, int s) {
    vector<vector<int>> adjList;
    adjList = Graph(edges, n + 1);
    vector<int> ans(n + 1, -1);
    ans[s] = 0;                          // starting point
    vector<bool> visited(n + 1);
    queue<int> q;
    visited[s] = true;
    q.push(s);
    while(!q.empty()) {
        int temp = q.front(); q.pop();
        for(int i: adjList[temp]) {
            if(!visited[i]) {
                ans[i] = 6 + ans[temp];   // just use it as DP array!
                visited[i] = true;
                q.push(i);
            }
        }
    }
    ans.erase(ans.begin() + s); // remove starting point(as per question)
    ans.erase(ans.begin());     // remove 0 (graph starts from 1)
    return ans;
}
...