1 year ago

#372454

test-img

drot

how to use bfs with random generated numbers in c++?

Hi can somebody help me please?

so far this is my code:

#include<iostream>
#include <list>

#define NOE 20
#define NOV 10
using namespace std;

class Graph
{
    int V;
    list<int>* adj;
public:
    Graph(int V); 
    void addEdge(int v, int w);
    void BFS(int s);
};

Graph::Graph(int V)
{
    this->V = V;
    adj = new list<int>[V];
}

void Graph::addEdge(int v, int w)
{
    adj[v].push_back(w); // Add w to vā€™s list.
}

void Graph::BFS(int s)
{
    bool* visited = new bool[V];
    for (int i = 0; i < V; i++)
        visited[i] = false;
    list<int> queue;

    visited[s] = true;
    queue.push_back(s);

    list<int>::iterator i;

    while (!queue.empty())
    {
        s = queue.front();
        cout << s << " ";
        queue.pop_front();
        for (i = adj[s].begin(); i != adj[s].end(); ++i)
        {
            if (!visited[*i])
            {
                visited[*i] = true;
                queue.push_back(*i);
            }
        }
    }
}

int main()
{
    bool jump = false;
    Graph g(NOV);
    int i, j, edge[NOE][2], count;
    i = 0;
    // Build a connection between two random vertex.
    while (i < NOE)
    {
        jump = false;
        edge[i][0] = rand() % NOV + 1;
        edge[i][1] = rand() % NOV + 1;

        if (edge[i][0] == edge[i][1])
            continue;
        else
        {
            for (j = 0; j < i; j++)
            {
                if ((edge[i][0] == edge[j][0] && edge[i][1] == edge[j][1]) || (edge[i][0] == edge[j][1] && edge[i][1] == edge[j][0]))
                {
                    i--;
                    jump = true;
                }
            }
            if (jump == false)
            {
                g.addEdge(edge[i][0], edge[i][1]); // here it throws error
            }
        }
        i++;
    }
    g.BFS(2);

    return 0;
}

so i want to generate a "tree" with 10 vertexes and 20 edges. Tree is generated succesfully but when it comes to bfs it throws exception. Im not sure why. Output looks like first 2 iterations works fine but then it crash. Can somebody help me please?

this is exception: Exception thrown at 0x00007FF7A7B1160D in ConsoleApplication6.exe: 0xC0000005: Access violation reading location 0xFFFFFFFFFFFFFFFF.

c++

breadth-first-search

0 Answers

Your Answer

Accepted video resources