# Adjacency list graph representation using C++ STL in competitive programming.

## Adjacency list graph representation using C++ STL in competitive programming.

Dec. 29, 2017
1 likes
8812 times viewed #### Description

Representation of a graph using adjacency list.Adjacency list representations of graphs take a more vertex-centric approach. There are many possible implementations of adjacency lists representation of graph. Here we will implement it in 2 ways:- one using array of vectors and another using vector of lists.

#### Content

The representation of graph is implemented using adjacency list. It makes use of STL(Standard Template Library of C++).

Extremely helpful in competitive coding problems as it makes use of STL containers `vector` and `list` and utility function `make_pair` from utility library includes in `stdc++.h`.

## Implementation using Array of Vectors

Features:

• The graph is implemented using array of n vertices:- G[n]: [V1,V2,V3, …,Vn].

• Each vertex is implemented using vector of connected vertices:- V[i]: [ V[x], V[y], V[z] ]

• Each connected vertex in vector is represented using pair:- pair.first: connected vertex, pair.second: connected edge’s weight.
`vector< pair<int, int> > G[n]; <------ Array of vectors`

• If graph is not weighted simply remove the `make_pair` and proceed without weight.

• If graph is undirected:
`G[v1].push_back(make_pair(v2, w));`
`G[v2].push_back(make_pair(v1, w));`

code

``````#include <bits/stdc++.h>
using namespace std;

int main(){
int n,e,w,v1,v2;

// Enter no. of vertices(n) and no. of edges(e)
cin>>n>>e;

// Array of vectors
vector < pair <int, int > > v[n];

for(int i=0;i<e;i++){
// Enter the v1, v2 and weight(w)
cin>>v1>>v2>>w;

// Adding Edge to the Graph
v[v1].push_back(make_pair(v2,w));
}

for(int i=0; i<n; ++i){
cout<<"["<<i<<"]";
for(int j=0; j<v[i].size(); ++j){
cout<<"--->["<<v[i][j].first<<"]["<<v[i][j].second<<"]";
}
cout<<endl;

}
return 0;
}

``````

## Implementation using Vector of lists

Features:

• The graph is implemented using vector of n vertices:- G(n): [V1,V2,V3, …,Vn].

• Each vertex is implemented using list of connected vertices:- V[i]: Vx–>Vy—>Vz

• Each connected vertex in list is represented using pair:- pair.first: connected vertex, pair.second: connected edge’s weight.
`vector< list< pair<int, int> > > G(n); <----- Vector of lists`

code

``````#include<bits/stdc++.h>
using namespace std;

int main(){
srand( time( 0 ) );
ios_base::sync_with_stdio(false);

int n, e, v1, v2, w;

// Enter the number of vertices(n) and edges(e)
cin>>n>>e;

// Vector of lists
vector< list< pair<int, int> > > G(n);

for (int i = 0; i < e; ++i) {
// Enter the v1, v2 and weight(w)
cin>>v1>>v2>>w;

// Adding Edge to the Graph
G[v1].push_back(make_pair(v2, w));
}

for (int i = 0; i < n; ++i) {
cout<<"["<<i<<"]";

list< pair<int, int> >::iterator itr = G[i].begin();

while (itr != G[i].end()) {
cout<<"--->"<<(*itr).first<<"("<<(*itr).second<<")";
++itr;
}
cout<<endl;
}

return 0;
}
``````

Input for the above graph:

``````6 7
0 1 3
0 2 5
1 3 2
2 3 1
3 4 4
3 5 8
4 5 6
``````

Output

``````--->--->
--->
--->
--->--->
--->

``````