Graph

• Non-linear data structure consisting of Nodes and Edges.
• Used to represent Networks.

The following two are the most commonly used representations of a graph.

1. Adjacency Matrix
2. Adjacency List

Adjacency Matrix

• Space required: Θ(V * V)
• Check if u and v are adjacent: Θ(1)
• Find all vertices adjacent to u: Θ(V)
• Find degree of u: Θ(V)
• Add/Remove an edge: Θ(1)
• Add/Remove a vertex: Θ(V * V)

Adjacency List

• Space required for directed graph: Θ(V + E)
• Space required for undirected graph: Θ(V + 2*E)
• Check if u and v are adjacent: Θ(V)
• Find all vertices adjacent to u: Θ(degree(u))
• Find degree of u: Θ(V)
• Add an edge: Θ(1)
• Remove an edge: Θ(V)

In general, Adjacency Lists are better than Adjacency Matrix. Lets see its implementation.

Adjacency List Implementation

we use dynamic arrays (vector in C++) to represent adjacency lists instead of the linked list. The vector implementation has advantages of cache friendliness.

#include<bits/stdc++.h> 
using namespace std; 
  
void addEdge(vector<int> adj[], int u, int v) { 
    adj[u].push_back(v); 
    adj[v].push_back(u); 
} 
   
void printGraph(vector<int> adj[], int V) { 
    for (int i = 0; i < V; i++) { 
        for (int x : adj[i]) 
           cout << x <<" "; 
        cout<<"\n"; 
    } 
} 
  
int main() { 
    int V = 4; 
    vector<int> adj[V]; 
    addEdge(adj, 0, 1); 
    addEdge(adj, 0, 2); 
    addEdge(adj, 1, 2); 
    addEdge(adj, 1, 3); 
    
    printGraph(adj, V); 
    return 0; 
}