Weighted Graph Implemetation

help
1

I have tried to implement basic weighted graph with adjacency list by making a list< list< pair<int,int>>> that is list of lists with pair for destination and weight but i am getting error can
anyone help me . Here is my code its showing error in addEdges function.

#include<bits/stdc++.h>
#include < utility >
#include< list >
#define ll long long
using namespace std;

class Graph{
int V;

list< list< pair<int,int> > >* adjList;

public:
Graph(int v){
V=v;
adjList = new list< list< pair<int,int> > >[V];
}

void addEdge(int u, int v, int wt){
adjList[u].push_back(make_pair(v,wt));
adjList[v].push_back(make_pair(u,wt));
}

void printGraph(){
for(int i=0;i<V;i++){
        cout<<"Node "<<i<<"=> ";
    for(list< pair<int,int> > element: adjList[i]){
        cout<<" ( "<<element.first<<" , "<<element.second<<" ) "<<" , ";
    }
    cout<<endl;
  }
}

};

int main(){

Graph g(4);

g.addEdge(0,1,10);
g.addEdge(0,2,20);
g.addEdge(0,3,25);
g.addEdge(1,3,30);
g.addEdge(2,3,35);

g.printGraph();

return 0;
}

2

List does not provide random access. So what you are trying to do is wrong. The inbuilt list in c++ is a doubly linked list. To allow random access is a bit tricky, can be done but its unnecessary when you have vectors. Vectors do allow random access. Hope this helps. For further reading on c++ list go here

1 Like
3

P.S. Just a suggestion :
I think you should add not having random access means you can't do object[i] in your comment, so that even new coders can understand.

4

@drag Thanks bro for pointing out but i have used vectors in place of list but still its not working

5

@drag
This is the geekforgeeks implementation but its using only vector<pair< int , int > >
so how its using only one vector to store different edges for any node …??

6

I would like to propose, that you use an array of vectors. It basically means that graph[i] is a vector, that contains all neighbors of node labelled/number i. So you have MAXN number of empty vectors initially, and when you input edges, let’s say, u and v are connected, then add v to graph[u], and similiarly add u to graph[v] ( unless it’s a directed graph, in which case only one of the above will be done ).

UPD: Also, answering your query, obviously a vector of pairs is enough to store information of all edges, because each edge is just {u,v}. But, that type of implementation might not prove to be very useful at times. Infact, I think even dfs might prove to be very non intuitive to implement in such a case.

7

Please try to take a book and learn about these libraries. You’ll understand only if you read it yourself since there is a lot of material to cover, which is not possible in a comment and is repetitive. I suggest reading ‘C++ Primer’ by Stanley B. Lippman, Josée Lajoie, and Barbara E. Moo.

1 Like
8

@drag Thanks for advice :slight_smile: