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

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

Dec. 29, 2017
6 minutes read time
1 likes
0 comments
7013 times viewed


header image

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:

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));
    }

    // Printing Adjacency List Graph
    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:

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));
    }

    // Printing Adjacency List Graph
    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

[0]--->[1][3]--->[2][5]
[1]--->[3][2]
[2]--->[3][1]
[3]--->[4][4]--->[5][8]
[4]--->[5][6]
[5]


We are done



Like this post

1   Like


Share this post on

Google Plus LinkedIn


About the author




Join the discussion

Nothing to preview

Post Comment



Comments