Data Structures c++ I need help implementing a weighted adjacency list graph wit
ID: 3918677 • Letter: D
Question
Data Structures c++
I need help implementing a weighted adjacency list graph with the following methods. It must be a weighted adjacency list. I haven't been able to find any good resources online to help me with this, so your help would be appreciated.
class Graph
{
private:
???
public:
Graph(); // constructor must NOT have an input
void insertVertex(int vertex); //inserts new vertex in graph
void insertEdge(int from, int to, int weight); //inserts new edge in graph
bool isEdge(int from, int to); //returns true if there is an edge between the vertices from and to
int getWeight(int from, int to); //returns the weight of the edge between the vertices from and to
vector<int> getAdjacent(int vertex); //return an array of integers representing vertices adjacent to vertex
};
Explanation / Answer
---------------------Code---------------------
#include <iostream>
#include <vector>
#include <map>
#define MAXSIZE 1000
using namespace std;
class Graph{
private:
vector<pair<int,int> > V[MAXSIZE];
map<int, int> getIndex;
int size;
public:
Graph(){
size = 0;
}
void insertVertex(int vertex){
getIndex[vertex] = size;
size++;
}
void insertEdge(int from, int to, int weight){
from = getIndex[from];
V[from].push_back(make_pair(to,weight));
}
bool isEdge(int from, int to){
from = getIndex[from];
for(int i=0;i<V[from].size();i++){
if(V[from][i].first==to){
return true;
}
}
return false;
}
int getWeight(int from, int to){
from = getIndex[from];
for(int i=0;i<V[from].size();i++){
if(V[from][i].first==to){
return V[from][i].second;
}
}
return -1;
}
vector<int> getAdjacent(int vertex){
int from = getIndex[vertex];
vector<int> ret;
for(int i=0;i<V[from].size();i++){
ret.push_back(V[from][i].first);
}
return ret;
}
};
void printVect(vector<int> V){
for(int i=0;i<V.size();i++){
cout << V[i] << " ";
}
cout << endl;
}
int main(){
Graph g;
g.insertVertex(2);
g.insertVertex(5);
g.insertVertex(10);
g.insertEdge(2,5,2);
g.insertEdge(2,10,2);
printVect(g.getAdjacent(2));
}
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.