I need help with writing an adjacency matrix in c++ for a BFS algorithm. Here is
ID: 3568273 • Letter: I
Question
I need help with writing an adjacency matrix in c++ for a BFS algorithm.
Here is what I have so far:
int main()
{
int d[9];
string pi[9];
string adj[9][9];
string edges;
string vert;
string vert1;
int index;
int index2;
int weight;
for (int i = 0; i < 9; i++) // for loop that goes through 9 getlines to fill out the edges and verticies in the adj matrix
{
string delimiter = " ";
string delimiter2 = "/";
getline(cin, edges);
vert = edges.substr(0,edges.find(delimiter)); // this gets the head of the verticies
edges.erase(0,edges.find(delimiter)+ delimiter.length());
vert1 = vert[0];
index = atoi(vert1.c_str())-65; // Sets the first index based on the first letter of the name "A" = 0
if (edges.length() != NULL)
{
while (edges.length() != 0) // while the end of the line is not reached
{
vert = edges.substr(0,edges.find(delimiter2)); // Gets the second vertex that has an edge to the first vertex
edges.erase(0,edges.find(delimiter2)+ delimiter2.length());
vert1 = vert[0];
index2 = atoi(vert1.c_str())-65; // gets the second index based off of the first letter of the second vertex
weight = atoi(edges.substr(0,edges.find(delimiter)).c_str()); // gets the weight after the / of the vertex
edges.erase(0,edges.find(delimiter2)+ delimiter2.length());
adj[index][index2] = weight; // sets the weight in the matrix based on the first letter of each vertex
}
for(int a=0; a<9; a++) //This loops on the rows.
{
for(int j=0; j<9; j++) //This loops on the columns
{
cout << adj[a][j] << " ";
}
cout << endl;
}
}
}
}
The problem I am having is it doesn't put anything into the matrix, and my delimiter parsing doesn't work right. I have no idea how to fix any of this.
I am supposed to take in input such as:
where the first number is the number of nodes/vertices followed by a blank line, then each line after that is a vertex name followed by other vertices reachable with a cost; line 3 indicates from Helium there is an edge to Fluorine (weight 5), and to Calcium (weight 6).
Note: all edges are directed and that edges may appear more than once: Aluminum to Dysprosium, Dysprosium to Aluminum. You might see a line with a vertex name without any other vertices following. That means that there is no edge coming from the vertex (see the test case 2). Also, there is an unspecified number of spaces between vertex names in each line.
Input will end with a blank line (after node and edge information, a user hits return).
1. Using the given input, store this information as an adjacency list or an adjacency matrix. You should store them in alphabetical order.
2. Second, using the same data set, perform the Breadth First Search, starting with the vertex "Aluminum" (and visit its adjacent notes in alphabetical order). And print the content of the queue for each outer loop (when one node is dequeued and its adjacency nodes are enqueued) as follows:
Explanation / Answer
#include<conio.h>
#include<stdio.h>
#define max 10
typedef struct que
{
int R,F;
int data[max];
}que;
que p;
int empty( );
int full();
void enqueueue(int );
int dequeueue();
void BFS(int);
void DFS(int);
int G[max][max];
int n=0;
int visited[max];
void main()
{
int i,j,v,op,e,x;clrscr();
printf(" Enter no of vertices : ");
scanf("%d",&n);
printf(" Enter no of edges : ");
scanf("%d",&e);
printf(" Enter the edges (STARTING VERTEX 0): ");
for(x=0;x<e;x++)
{printf(" Enter the edge(%d): ",x+1);
scanf("%d%d",&i,&j);
G[i][j]=G[j][i]=1;
}
printf(" The adjecendy matrix of graph is: ");
for(i=0;i<n;i++)
{for(j=0;j<n;j++)
printf("%d ",G[i][j]);
printf(" ");
}
do{
printf(" 1)DFS 2)BFS 3)QUIT");
printf(" Enter Your choice : ");
scanf("%d",&op);
switch(op)
{ case 1:printf(" Enter the starting vertex for DFS : ");
scanf("%d",&v);
for(i=0;i<n;i++)
visited[i]=0;
DFS(v);break;
case 2:printf(" Enter the starting vertex for BFS : ");
scanf("%d",&v);
BFS(v);break;
}
}while(op!=3);
}
void BFS(int v)
{
int visited[max],i;
//que p;
p.R=p.F=-1;
for(i=0;i<n;i++)
visited[i]=0;
enqueueue(v);
printf(" visit %d",v);
visited[v]=1;
while(!empty())
{
v=dequeueue();
// visit and add adjecency vertices
for(i=0;i<n;i++)
if(visited[i]==0 && G[v][i]!=0)
{
enqueueue(i);
visited[i]=1;
printf(" %d",i);
}
}
}
int empty()
{
if(p.R==-1)
return(1);
return(0);
}
int full()
{
if(p.R==max-1)
return(1);
return(0);
}
void enqueueue(int x)
{
if(p.R==-1)
{
p.R=p.F=0;
p.data[p.R]=x;
}
else
{
p.R=p.R+1;
p.data[p.R]=x;
}
}
int dequeueue()
{
int x;
x=p.data[p.F];
if(p.R==p.F)
{
p.R=-1;
p.F=-1;
}
else
p.F=p.F+1;
return(x);
}
void DFS(int i)
{
int j;
printf(" %d",i);
visited[i]=1;
for(j=0;j<n;j++)
if(!visited[j] && G[i][j]==1)
DFS(j);
}
/*
*** OUTPUT ***
Enter no of vertices : 4
Enter no of edges : 5
Enter the edges (STARTING VERTEX 0):
Enter the edge(1): 0 1
Enter the edge(2): 1 2
Enter the edge(3): 2 3
Enter the edge(4): 3 0
Enter the edge(5): 1 3
The adjecendy matrix of graph is:
0 1 0 1
1 0 1 1
0 1 0 1
1 1 1 0
1)DFS
2)BFS
3)QUIT
Enter Your choice : 1
Enter the starting vertex for DFS : 0
0
1
2
3
1)DFS
2)BFS
3)QUIT
Enter Your choice : 2
Enter the starting vertex for BFS : 0
visit
0
1
3
2
1)DFS
2)BFS
3)QUIT
Enter Your choice : 2
Enter the starting vertex for BFS : 1
visit
1
0
2
3
1)DFS
2)BFS
3)QUIT
Enter Your choice :3
*/