im trying to output my bfs in this manner, showing the connections rather than the individual nodes:

input
0 1 1 0
1 0 0 0
1 0 0 1
0 0 1 0

output
(0,1)
(0,2)
(2,3)


rather than:
0
1
2
3

this is my code so far, the ??? indicate where im not sure what code to use.

void bfs(int matrix[MAXSIZE][MAXSIZE], int current, int n)
{
   bool visited [MAXSIZE] = {false};
   queue <int> q;   
   visited [current] = true;
   q.push(current);
   
   while (!q.empty())
   {
       current = q.front();
       cout << "(" << ??? << "," << current << ")" << endl;
       q.pop();
       getAllAdjacent(matrix, current,visited,q, n);
   }
}

void getAllAdjacent(int matrix[MAXSIZE][MAXSIZE], int current, bool visited[], queue <int> &q, int n)
{
   // put all aunvisited vertices adjacent to current
   // onto queue
   for (int col= 0; col < n; col++)
      if (matrix[current][col]>=1  && !visited[col])
      {
          q.push(col);
          visited[col] = true;
      }
}

can you post the full code?

#include <iostream>
#include <queue>
#include <cstdlib>
using namespace std;
//function prototypes
const int MAXSIZE = 100;
void bfs(int matrix[MAXSIZE][MAXSIZE], int current, int n);
void getAllAdjacent(int matrix[MAXSIZE][MAXSIZE], int current, bool visited[], queue<int> &q, int n);
void readMatrix(int matrix[MAXSIZE][MAXSIZE], int &n);


int main ()
{
   int current = 0;
   int n = 0;
   int matrix[MAXSIZE][MAXSIZE] = {0};
   
   readMatrix(matrix,n); 
   bfs(matrix, current, n);
   
   system("pause");
   return 0;
}

void readMatrix(int matrix[MAXSIZE][MAXSIZE], int &n)
{
  // reads in number of vertices and sets n to number of vertices
  // reads in matrix
  // has some error checking but not idiot proof
  int num;
  cout << "Enter number of vertices " << endl;
  if (cin >> n && n > 0)
  {
    cout << "Enter matrix " << endl;
    for (int row = 0; row < n; row++)
      for (int col = 0; col < n; col++)
        if (cin >> num && num >= 0)
           matrix[row][col]= num;
  }
  else n = 0;
} 

void bfs(int matrix[MAXSIZE][MAXSIZE], int current, int n)
{
   bool visited [MAXSIZE] = {false};
   queue <int> q;   
   visited [current] = true;
   q.push(current);
   
   while (!q.empty())
   {
       current = q.front();
       cout << "(" << ??? << "," << current << ")" << endl;
       q.pop();
       getAllAdjacent(matrix, current,visited,q, n);
   }
}

void getAllAdjacent(int matrix[MAXSIZE][MAXSIZE], int current, bool visited[], queue <int> &q, int n)
{
   // put all unvisited vertices adjacent to current
   // onto queue
   for (int col= 0; col < n; col++)
      if (matrix[current][col]>=1  && !visited[col])
      {
          q.push(col);
          visited[col] = true;
      }
}

Why you are doing it as BFS,

so far i understand you just have to give output for the adjacent nodes, and that are already mention in the input,

0 1 1 0
1 0 0 0
1 0 0 1
0 0 1 0

there is already a path between (0,1), (0,2), (2,3)

you dont need BFS to give this ouput, just check the matrix, if there is a path between them give output.

for(i = 0; i < NumberOfNodes; I++)
  for(j = 0; j < i; j++)
     if(there is a path between i and j)
             give output
This article has been dead for over six months. Start a new discussion instead.