BFS and DFS Assignment The paths between nodes are represented as an nxn matrix,
ID: 3607638 • Letter: B
Question
BFS and DFS Assignment
The paths between nodes are represented as an nxn matrix, where n is the number of nodes. Each slot in the matrix represent the weight of the path between corresponding nodes. Zero and Negative values represents non-exiting path.
The matrix usually stored in a file in the following format, where the fist line representing the node names, and subsequence lines representing the weight between the any two nodes between the corresponding row and column.
A B C D E F …
0 1 2 0 2 1
1 0 0 0 1 1
…
You are required to implement a program that:
Prompts the user to enter the name of the file containing the matrix, the name of the starting node, and the name of the ending node.
Find and display a path (preferably shortest path ) between the starting node and the ending node by Breath First Search
Find and display a path (preferably shortest path ) between the starting node and the ending node by Depth First Search
Hints: it would be easier to handle your graph if each node is encapsulated with at least: node name, distance from the source node, and the preceding node name on the path for that distance
Explanation / Answer
#include<iostream>
#include<map>
#include<string>
#include<sstream>
#include<vector>
#include<fstream>
#include<stack>
#include<queue>
using namespace std;
map<string,int> name;
vector<string> name2;
void bfs(vector<vector<int>> adj,int src,int dest){
cout<<"::::BFS:::: ";
vector<vector<int>> parent;
vector<int> v(adj.size());
parent.push_back(v);//parent
parent.push_back(v);//weight till that node
queue<int> q;
int i,n,el;
n=adj.size();
for(i=0;i<n;i++){
parent[0][i]=i;//par
parent[1][i]=99999;//wt
}
parent[1][src]=0;
q.push(src);
while(!q.empty()){
el=q.front();
q.pop();
for(i=0;i<n;i++){
if(adj[el][i]>0&&parent[1][i]>parent[1][el]+adj[el][i]){
parent[1][i]=adj[el][i]+parent[1][el];
parent[0][i]=el;
q.push(i);
}
}
}
cout<<"shortest part dist="<<parent[1][dest]<<" path="<<name2[dest]<<"<-";
el=parent[0][dest];
while(el!=src){
cout<<name2[el]<<"<-";
el=parent[0][el];
}
cout<<name2[src];
}
void dfs(vector<vector<int>> adj,int src,int dest){
cout<<" ::::DFS:::: ";
vector<vector<int>> parent;
vector<int> v(adj.size());
parent.push_back(v);//parent
parent.push_back(v);//weight till that node
stack<int> stk;
int i,n,el;
n=adj.size();
for(i=0;i<n;i++){
parent[0][i]=i;//par
parent[1][i]=99999;//wt
}
parent[1][src]=0;
stk.push(src);
while(!stk.empty()){
el=stk.top();
stk.pop();
for(i=0;i<n;i++){
if(adj[el][i]>0&&parent[1][i]>parent[1][el]+adj[el][i]){
parent[1][i]=adj[el][i]+parent[1][el];
parent[0][i]=el;
stk.push(i);
}
}
}
cout<<"shortest part dist="<<parent[1][dest]<<" path="<<name2[dest]<<"<-";
el=parent[0][dest];
while(el!=src){
cout<<name2[el]<<"<-";
el=parent[0][el];
}
cout<<name2[src];
}
int main(){
stringstream ss;
string file,s,src,dest;
ifstream infile;
int i=0,k,n;
vector<vector<int>> adj;
vector<int> v;
cout<<"Enter the nape of the input file:"; //full name like input.txt (in same folder as this cpp file)
cin>>file;
infile.open(file);
getline(infile,s);
ss<<s;
while(ss>>s){
name[s]=i;
name2.push_back(s);
i++;
}
std::map<string,int>::iterator it=name.begin();
while(getline(infile,s)){
v.clear();
ss.clear();
ss<<s;
while(ss>>k){
v.push_back(k);
}
adj.push_back(v);
}
cout<<"Enter the name of the source: ";
cin>>src;
cout<<"Enter the name of the destination: ";
cin>>dest;
bfs(adj,name.find(src)->second,name.find(dest)->second);
dfs(adj,name.find(src)->second,name.find(dest)->second);
return 0;
}
/*
input eg:
>>input.txt
a b1 b2 c1 c2 c3
0 1 1 0 0 0
1 0 0 1 2 0
1 0 0 0 1 1
0 0 0 0 0 0
0 0 0 0 0 0
0 0 0 0 0 0
>>on cmd
input.txt
a
c2
>>output
Enter the nape of the input file:in.txt
Enter the name of the source: a
Enter the name of the destination: c2
::::BFS::::
shortest part dist=2
path=c2<-b2<-a
::::DFS::::
shortest part dist=2
path=c2<-b2<-a
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.