Некоторый код в моей C ++ программе приводит к сбою программы. Я реализую алгоритм BFS - PullRequest
Новая
       27

Некоторый код в моей C ++ программе приводит к сбою программы. Я реализую алгоритм BFS

1 голос
/ 18 апреля 2020

Я использую алгоритм BFS . Я написал этот код в моей IDE .
SYSTEM:
Windows 10
Dev c ++

Может быть ошибка в функции bfs () . Я разместил весь свой код только из-за ссылки.
Мой C ++ код: 


#include<bits/stdc++.h>
using namespace std;

class Graph{
    int v; // number of vertices
    vector<int>*adj;
    public:
        /**
         * Constructor to initialize the graph.
         * @param v an integer: number of nodes in the graph
         */
        Graph(int V){
            this->v=V;
            this->adj=new vector<int>[V];
        }

        /**
         * This function add a new edge to the graph.
         * @param u an integer: representing a node in the graph.
         * @param v an integer: representing a node in the graph.
         * @param biDir a bool: true denotes bidirectional edge, unidirectional otherwise.
         */
        void addEdge(int u,int v,bool biDir=false){
            adj[u].push_back(v);
            if(biDir)
                adj[v].push_back(u);
        }
        /**
         * This function traverse the given graph using BFS traversal technique.
         * @param src a node: function starts traversing from this node.
         */
        void bfs(int src){
            // create a array of boolean to keep track of visited nodes.
            vector<bool>visited(this->v,false);
           // visited[0]=true;
            // make a queue and insert src into it
            queue<int>q;
            q.push(src); // insert src into queue
            // mark first node as visited
            visited[src]=true;
            while(!q.empty()){
                int node=q.front();
                // visit
                cout<<node<<" ";
                // remove this node from queue
                q.pop(); 
                // visit every node adjacent to node 'node' 
                // if that node not visited then visit and enque it.
                for(int adjNode:adj[node]){
                    if(!visited[adjNode]){
                        visited[adjNode]=true;
                        q.push(adjNode);
                    }
                }
            }

        }
         void print(){
            // for every vertex
            for(int i=1;i<this->v;i++){
                // every connected edge from vertex
                cout<<i<<"-> ";
                for(int node:adj[i]){
                    cout<<node<<" ";
                }
                cout<<endl;
            }
        }
};
int main(){
    Graph g(5+1);
    g.addEdge(1,2);
    g.addEdge(1,4);
    g.addEdge(4,6);
    g.addEdge(3,6);
    g.addEdge(2,5);
    g.addEdge(5,2);
    g.addEdge(6,3);
    g.addEdge(6,4);
    g.print();
    cout<<endl;cout<<endl;cout<<endl;cout<<endl;
    g.bfs(1);
    return 0;
}

Хотя эта программа компилируется нормально. Но во время работы выполняется только функция print () . Функция bfs () не выполняется.
Создает следующую OUTPUT: , генерируемую функцией print () . 

1-> 2 4
2-> 5
3-> 6
4-> 6
5-> 2

Когда я изменил этот код в bfs () 

vector<bool>visited(this->v,false);

TO 

 bool visited[this->v];
            for(int i=0;i<this->v;i++)
                visited[i]=false;

этот код также не выполняется bfs ().

Ответы [ 2 ]

1 голос
/ 18 апреля 2020

Как я вижу, вы используете индексирование 1 для значения узла. Я имею в виду, что вы не рассматриваете 0 как узел на вашем графике. Любой узел в вашем графике начинается с 1. При инициализации графика вы можете установить значение размера графика равное number of nodes + 1.
Я имею в виду, 

Graph(int V){
            this->v=V+1;
            this->adj=new vector<int>[V];
        }

Это может решить вашу проблему.

1 голос
/ 18 апреля 2020

Вы можете просто установить размер до 7, и он будет работать. Ваша проблема в том, что вы изменяете размер графика, чтобы иметь 6 узлов, но при этом получаете доступ к 7-му узлу (узел с номером 6 считается 7-м узлом, поскольку индексы начинаются с 0). Но в любом случае это не лучший способ решить проблему. Если вы хотите, чтобы число 6 было включено, тогда пусть размер графика будет V + 1. Также я заметил, что вы используете указатель на вектор в графе. Я думаю, что было бы лучше, если бы вместо этого вы использовали вектор векторов. Вот код, который делает то же самое с исправленными проблемами. 

#include <iostream>
#include <vector>
#include <queue>

class Graph
{
    std::vector<std::vector<int>> _graph;

public:

    Graph(int size)
    {
        // nodes within the range [0..size] are valid.
        _graph.resize(size + 1);
    }

    void addEdge(int from, int to, bool undirected = false)
    {
        _graph[from].push_back(to);

        if (undirected)
            _graph[to].push_back(from);
    }

    void bfs(int source)
    {
        std::vector<bool> visited(_graph.size(), false);

        std::queue<int> queue;

        queue.push(source); 

        int depth = 0;

        while (!queue.empty())
        {
            int size = queue.size();

            std::cout << "Depth Level " << depth << " (with " << size << " unvisited nodes): ";

            while (size--)
            {
                int current = queue.front(); 

                std::cout << current << ' ';

                visited[current] = true;
                queue.pop();

                for (int node : _graph[current])
                    if (!visited[node])
                        queue.push(node);
            }

            std::cout << std::endl;
            depth++;
        }
    }
};

int main() {

    Graph g(6);
    g.addEdge(1, 2);
    g.addEdge(1, 4);
    g.addEdge(4, 6);
    g.addEdge(3, 6);
    g.addEdge(2, 5);
    g.addEdge(5, 2);
    g.addEdge(6, 3);
    g.addEdge(6, 4);

    g.bfs(1);
}

Вывод: 

Depth Level 0 (with 1 unvisited nodes): 1
Depth Level 1 (with 2 unvisited nodes): 2 4
Depth Level 2 (with 2 unvisited nodes): 5 6
Depth Level 3 (with 1 unvisited nodes): 3
...