03. GraphRepresentationcpp.md

Graph representation

Matrix Representation

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

int main(){
    int n, m;
    cin>>n>>m;
    
    //declare the adjacency matrix for graph
    //as graph has one based indexing so you have to take the matrix of size 1 greater
    //if 0 based indexing, matrix size = mat[m][n]
    //if 1 based indexing, matrix size = mat[m+1][n+1]
    int mat[n+1][m+1];
    
    for(int i=0; i<m; i++){
        int u, v;
        cin>>u>>v;
        mat[u][v] = 1;
        mat[v][u] = 1;
    }
    
    return 0;
}

Space complexity : O(n^2) So, if the range of n is larger, then we can't create matrix, e.g, if n is 10^5 then we'd need the space of 10^10 to store the matrix, in that case we'd use, Adjacency List

Adjacency List representation

It would be a list of vectors, i.e there would be vector for each node and that will store the adjacent nodes list, i.e basically there would be n size array and at each element there would be vector which would store all the adjacent nodes, there would be 2XE adjacent elements in total (in case of undirected graph) where E is total no. of edges, because if there is an edge between 1 and 2 then there is an edge between 2 and 1 also.

vector adj[n] when we'll want to push an element into the adjacency list, we'd say adj[u].push_back(v) and adj[v].push_back(u), this is for undirected graph, but for directed graph only write adj[u].push_back(v)

In case if the graph is weighted then you have to declare it as vector<pair<int, int>> adj[n], so that you can store the weight, first will store the adjacent node and second will store the weight, and how you'll push it: adj[u].push_back({v, w}) where w represents weight, we'll see while solving questions.

Unweighted graph(0 based Indexing)

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

int main(){
   // n = no. of vertices
   //m = no. of edges
   int n, m;
   cin>>n>>m;
   
   //size will be n as graph is 0 based indexing in our case.
   vector<int> adj[n];
   
   
   for(int i=0; i<m; i++){
       int u, v;
       cin>>u>>v;
       
       adj[u].push_back(v);
       //if the graph is undirected then ommit the next line
       adj[v].push_back(u);
   }
   
   return 0;
}

Unweighted graph(1 based Indexing)

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

int main(){
   // n = no. of vertices
   //m = no. of edges
   int n, m;
   cin>>n>>m;
   
   //size will be n+1 as graph is 1 based indexing in our case.
   vector<int> adj[n+1];
   
   
   for(int i=0; i<m; i++){
       int u, v;
       cin>>u>>v;
       
       adj[u].push_back(v);
       //if the graph is undirected then ommit the next line
       adj[v].push_back(u);
   }
   
   return 0;
}

Space complexity : O(N + 2E)

Weighted Graph

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

int main(){
   // n = no. of vertices
   //m = no. of edges
   int n, m;
   cin>>n>>m;
   
   //size will be n+1 as graph is 1 based indexing in our case.
   //as graph is weighted so take pair
   vector<pair<int, int>> adj[n+1];
   
   for(int i=0; i<m; i++){
       int u, v, wt;
       cin>>u>>v>>wt;
       
       adj[u].push_back({v, wt});
       adj[v].push_back({u, wt});
   }
   
   return 0;
}

Space complexity : O(N + 2E) + 2E extra 2E because we are creating pair to store weights