Data Structure in C++ Graphs and Breadth-first Search Please fix and implement t

ID: 3844199 • Letter: D

Question

Data Structure in C++

Graphs and Breadth-first Search

Please fix and implement this homework.

Here is my unfinished code:

#include <iostream>
#include <sstream>
#include <string>
#include <list>
#include <algorithm>
#include <vector>
#include <functional>
#include <queue>
using namespace std;

using graph = vector<list<int>>;

class graph {
int V;
list *adj;

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

struct edge_type {
float weight;
int destination;
};

void create(int src, int dest){
edges.at(src).push_back(edge_type{w, dest});
}

void print(string reg){
cout << adj[reg] << endl;
}

void arc(string r1, string r2, string result){

}

void biarc(string r1, string r2, string result){

}

void bfs(string r1, string r2, string result){

}

};

int main(){
using std::cin;
using std::cout;
using std::endl;
string line;
graph execute = graph();
while(true){
cout << "> ";
getline(cin,line);
string word; // Have a buffer string
std::stringstream ss(line); // Insert the string into a stream
vector words; // Create vector to hold our words
while (ss >> word)
words.push_back(word);

if(words[0] == "create"){
int val = atoi(words[1].c_str()); // Change string into$
execute.create(val, words[2]);
}

else if(words[0] == "print"){
execute.print(words[1]);
}

else if(words[0] == "arc"){
execute.arc(words[1], words[2], words[3]);
}

else if(words[0] == "biarc"){
execute.biarc(words[1], words[2], words[3]);
}

else if(words[0] == "bfs"){
execute.bfs(words[1], words[2], words[3]);
}

else if(words[0] == "stop"){
return 0;
}

else{
cout << "No command with that name exists" << endl;
}
}
}

Part 1: Adj. list graphs Write an implementation of the adjacency listgraph representation. You may assume that nodes are integers which start at 0 Using your implementation, implement the breadth-first-search algorithm. as a function which takes a graph a starting node and a target node, and searches for a path between them. Your BFS function should return the shortest distance from the source node to the target node, or -1 if no path exists Part 2: Commands Implement the following commands Command Description create nr Create a new empty graph in register r. with n nodes print r Print some representation of the graph in r arc a br n the graph in register r, create an arc from node a to b biarc abr Create a bidirectional arc from ato bin r bfs a br Perform a breadth-first search from a to b in r, printing the distance Write the register commands necessary to create the following graph: and place them in a comment in your source code. What is the distance from node 9 to node 6?

Explanation / Answer