Граф BFS Traversal - C ++ - PullRequest
Новая
       71

Граф BFS Traversal - C ++

0 голосов
/ 02 мая 2020

Учитывая неориентированный и отключенный граф G (V, E), выведите его обход BFS. Здесь вам нужно учесть, что вам нужно вывести путь BFS, начиная только с вершины 0. V - число вершин, присутствующих в графе G, и вершины пронумерованы от 0 до V-1. E - число ребер, присутствующих в графе G. Примечание: 1. Возьмите граф, введенный в матрицу смежности. 2. Дескриптор и для отключенных графиков. Формат ввода: Строка 1: два целых числа V и E (разделенные пробелом). Следующие строки 'E', каждая из которых содержит два целых числа, разделенных пробелом, 'a' и 'b', обозначая, что существует ребро между вершиной «а» и вершиной «б». Формат вывода: Обход BFS (разделенный пробелом) Ограничения: 2 <= V <= 1000 1 <= E <= 1000 Пример ввода 1: 4 4 0 1 0 3 1 2 2 3 Пример вывода 1: 0 1 3 2 Пожалуйста, сообщите что не так в коде. </p>

Вот код: 

#include <iostream>
using namespace std;
#include <queue>

void print(int** edges, int V, int sv, bool* visited){
    queue<int> pq;
    pq.push(sv);
    visited[sv] = true;

    while(!pq.empty()){
        int ans = pq.front();
        cout << ans << " ";
        pq.pop();

        for(int i = 0; i < V; i++){
            if(ans == i){
                continue;
            }
            if(edges[ans][i] == 1 && !visited[i]){
                pq.push(i);
                visited[i] = true;
            }
        }

    }

}   
void BFS(int** edges, int V){
    bool* visited = new bool[V];
    for(int i = 0; i < V; i++){
        visited[i] = false;
    }
    for(int i = 0; i < V; i++){
        if(!visited[i]){
            print(edges, V, i, visited);
        }
    }
    delete [] visited;
}






int main() {
    int V, E;
    cin >> V >> E;

    int**edges = new int*[V];
    for(int i = 0; i < V; i++){
        edges[i] = new int[V];
        for(int j = 0; j < V; j++){
            edges[i][j] = 0;
        }
    }
    for(int i = 0; i < E; i++){
        int f, s;
        cin >> f >> s;
        edges[f][s] == 1;
        edges[s][f] == 1;
    }



    BFS(edges, V);

    for(int i = 0; i < V; i++){
        delete [] edges[i];
    }
    delete [] edges;

  /*

       Write Your Code Here
       Complete the Rest of the Program
       You have to take input and print the output yourself

  */


}
...