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 21 times
#pragma once
#include<list>
#include<string>
struct Pair {
Pair(int n, int w) {
node = n;
weight = w;
}
int node;
int weight;
};
class Graph {
public:
Graph(std::string);
int shortestCost(int start, int finish);
private:
std::list<Pair>* adjList;
int numNodes;
};
------------------------------------------------------------------------------------------------------------
(CppFile.cpp)
#include"Graphs.h"
#include<fstream>
#include<stdexcept>
#include<cstdint>
using std::ifstream;
using std::invalid_argument;
using std::list;
Graph::Graph(std::string filename) {
ifstream input;
input.open(filename);
if (!input) {
throw invalid_argument("Could not read file");
} //end if
input >> numNodes;
adjList = new list<Pair>[numNodes];
for (int i = 0; i < numNodes; i++) {
int value;
int cost;
input >> value;
while (value >= 0) {
input >> cost;
adjList.push_back(Pair(value, cost));
input >> value;
} //end while
} //end for
}
int Graph::shortestCost(int start, int finish) {
int* dist = new int[numNodes];
list<int> remaining;
list<int> finished;
for (int i = 0; i < numNodes; i++) {
if (i == start) {
dist = 0;
} //end if
else {
dist = INT_MAX;
} //end else
remaining.push_back(i);
} //end for
while (!remaining.empty()) {
int minDist = INT_MAX;
int minIndex = -1;
for (list<int>::iterator listIt = remaining.begin(); listIt
!= remaining.end(); listIt++) {
if (dist[*listIt] < minDist) {
minDist = dist[*listIt];
minIndex = *listIt;
} //end if
} //end for
int cur = minIndex;
if (!adjList[cur].empty()) {
for (list<Pair>::iterator listIt = adjList[cur].begin();
listIt != adjList[cur].end(); listIt++) {
int next = (*listIt).node;
int nextWeight = (*listIt).weight;
if (dist[cur] + nextWeight < dist[next]) {
dist[next] = dist[cur] + nextWeight;
}
}
}
remaining.remove(cur);
finished.push_back(cur);
}
int shortestCost = dist[finish];
delete[] dist;
return shortestCost;
}
-----------------------------------------------------------------------------------------------
(MainCpp.cpp)
#include"Graphs.h"
#include<iostream>
using std::cout;
using std::endl;
int main() {
Graph g1("Graphs.txt");
cout << "0->3:" << g1.shortestCost(0, 3) <<
endl;
cout << "0->1:" << g1.shortestCost(0, 1) <<
endl;
cout << "0->2:" << g1.shortestCost(0, 2) <<
endl;
}
--------------------------------------------------------------------------------------------
(TextFile1.txt)
4
0 1 2 3 -1
1 0 3 -1
2 0 3 -1
3 0 1 2 -1
---------------------------------------------------------------
(TextFile2.txt)
8
0 1 -1
1 2 3 -1
2 4 -1
3 5 -1
4 6 -1
5 -1
6 -1
7 -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