ERROR IN BFS IMPLEMENTATION

general
1

While implementing the ans is not correct. PLz help

#include<iostream>
#include<conio.h>
using namespace std;

struct node
{
	int x;
	node*link;
};

node*r = NULL;
node*f = NULL;

void enq(int y)

{

	node* obj = new node;

	obj->x = y;

	obj->link = NULL;

	if (r == NULL && f == NULL)
	{
		f = r = obj;
		return;
	}

	else
	{
		r->link = obj;
		r = obj;

	}
}

int isempty()
{
	return (f == NULL);
}

int deq()
{
	int data;

	if (isempty())
	{
		cout << "Queue is empty\n";
		return 0;
	}

	else
	{
		data = f->x;
		f = f->link;
		return data;
	}

}


int mat[30][30] = { 0 }, visit[30] = { 0 }, q[30];

void bfs(int k,int v)

{
	int i, u;

      enq(k);
	
	while (!isempty())

{
		u = deq();

cout << u+1 << endl;

		visit[u] = 1;

		for (i = 0; i < v; i++)

		{

			if (!visit[i] && mat[k][i])

				enq(i);
			
		}
		
	}

}

void bfst(int v)

{

	int i;

	for (i = 0; i < v; i++)

	{

		if (!visit[i])

			bfs(i, v);

	}

}
int main()
{
	int i, j, k, v, e, l, m;

cout << "Enter the number of vertices and edges\n";

	cin >> v >> e;

	

	cout << "Enter the adjacenecy matrix\n";
	
	for (i = 0; i < e; i++)
	{
		cin >> l >> m;
		mat[l - 1][m - 1] = 1;
		mat[m - 1][l - 1] = 1;
	}
	bfst(v);
	
	return 0;
}
2

This is your corrected code:

#include<iostream>
using namespace std;

struct node
{
    int x;
    node*link;
};

node*r = NULL;
node*f = NULL;

void enq(int y)

{

    node* obj = new node;

    obj->x = y;

    obj->link = NULL;

    if (r == NULL && f == NULL)
    {
        f = r = obj;
        return;
    }

    else
    {
        r->link = obj;
        r = obj;

    }
}

int isempty()
{
    return (f == NULL);
}

int deq()
{
    int data;

    if (isempty())
    {
        cout << "Queue is empty\n";
        return 0;
    }

    else
    {
        data = f->x;
        f = f->link;
        if(f==NULL)        // 'r' wasnt being reinitialized to NULL!!!
                r=NULL;
        return data;
    }

}


int mat[30][30] = { 0 }, visit[30] = { 0 }, q[30];

void bfs(int k,int v)

{
    int i, u;

      enq(k);

    while (!isempty())

{
        u = deq();

cout << u+1 << endl;

        visit[u] = 1;

        for (i = 0; i < v; i++)

        {

            if (!visit[i] && mat[u][i])     // "[u][i]" instead of [k][i]
            {
                //cout<<"++++"<<i+1<<endl;
                enq(i);
            }

        }

    }

}

void bfst(int v)

{
	/*for(int i=0;i<v;i++,cout<<endl)
		for(int j=0;j<v;j++)
			cout<<mat[i][j]<<"\t";*/
    int i;

    for (i = 0; i < v; i++)

    {

        if (!visit[i])
		
            bfs(i, v);
            

    }

}
int main()
{
    int i, j, k, v, e, l, m;

cout << "Enter the number of vertices and edges\n";

    cin >> v >> e;



    cout << "Enter the adjacenecy matrix\n";

    for (i = 0; i < e; i++)
    {
        cin >> l >> m;
        mat[l - 1][m - 1] = 1;
        mat[m - 1][l - 1] = 1;
    }
    bfst(v);

    return 0;
}

OR

LINK to the code…from next time onwards you can use this site to share your codes!!!

Hope this helps…:slight_smile:

3

thanks a lot!!

1 Like
4

glad could help…:slight_smile: