answers)
(C++)
Rewrite the code and make Graph Class stores nodes as integer
values using an adjacency list representation, and implement a
couple of breadth-first traversal methods one for print the graph
and one for finding nodes and paths in the graph.
Each subsequent line starts with the current node and then a
space separated list of adjacent nodes. The list is terminated with
a -1.
- Answer Only If You Know The Answer I Do Report Wrong Answers C Rewrite The Code And Make Graph Class Stores Nodes 1 (56.38 KiB) Viewed 27 times
#pragma once
#include<list>
#include<string>
using namespace std;
class Graph {
public:
Graph(std::string);
void addEdge(int src, int dest);
void BFT(int v);
void printBFT(std::ostream& out);
private:
std::list<int>* adjList; // Pointer to an
array containing adjacency lists
int numVertices; //// No. of vertices
bool* visited;
int v;
};
(Graphs.cpp)
#include"Graphs.h"
#include<fstream>
#include<stdexcept>
#include<cstdint>
#include<iostream>
using namespace std;
using std::ifstream;
using std::invalid_argument;
using std::list;
// creates a graph from the given filename. The file
format is specified below.
Graph::Graph(std::string) {
int v = numVertices;
adjList = new list<int>[v];
}
// Add edges to the graph
void Graph::addEdge(int src, int dest) {
adjList[src].push_back(dest);
adjList[dest].push_back(src);
}
//
void Graph::BFT(int v) {
// Mark all the vertices as not visited
bool* visited = new bool[v];
for (int i = 0; i < v; i++) {
visited = false;
}
}
//outputs the graph using a breadth-first traversal
void Graph::printBFT(std::ostream& out) {
int edg;
list<int> queue;
queue.push_back(v);
visited[v] = true;
while (!queue.empty()) {
edg = queue.front();
queue.pop_front();
cout << edg << " ";
visited[edg] = true;
list <int> ::iterator it;
for (it = adjList[edg].begin(); it !=
adjList[edg].end(); ++it) {
if (!visited[*it])
{
queue.push_back(*it);
}
}
}
out;
}
(Main.cpp)
#include"Graphs.h"
#include<iostream>
using std::cout;
using std::endl;
int main() {
Graph g1 ("../Graphs.txt");
}
(Graphs.txt)
4
1 3 2 5 3 2 -1
2 1 -1
1 1 -1
-1
Graph class • Must support the following public methods: Graph(std::string file) - creates a graph from the given filename. The file format is specified below. o printBFT(std::ostream&) - outputs the graph using a breadth-first traversal Breadth-First Traversal o . . Start with an empty queue Insert the starting node into the queue (Node 0 unless otherwise specified). while the queue is not empty o pop a node from the queue o visit the node (print, check if target value, etc) o for each neighbor of node . if neighbor is not marked as discovered • mark neighbor as discovered . add neighbor to queue