DSA Graphs Implementation

DSA Graphs Implementation – Complete Practical Guide

(Adjacency Matrix • Adjacency List • BFS • DFS • Code • Complexity)

Implementing Graphs is a core DSA skill.
In exams & interviews, you are mainly expected to know two representations and two traversals.

1️⃣ Graph Implementation Methods

Graphs are implemented in two main ways:

Adjacency Matrix
Adjacency List (Most used)

2️⃣ Adjacency Matrix Implementation

Concept

Use a 2D array
matrix[i][j] = 1 → edge exists
matrix[i][j] = 0 → no edge

Example Graph

Adjacency Matrix

C++ Implementation

#include <iostream>
using namespace std;

int main() {
int V = 4;
int adj[4][4] = {0};

// Undirected graph
adj[0][1] = adj[1][0] = 1;
adj[0][2] = adj[2][0] = 1;
adj[0][3] = adj[3][0] = 1;
adj[1][3] = adj[3][1] = 1;
adj[2][3] = adj[3][2] = 1;

for(int i = 0; i < V; i++) {
for(int j = 0; j < V; j++)
cout << adj[i][j] << " ";
cout << endl;
}
return 0;
}

#include <iostream>

using namespace std;

int main() {

int V = 4;

int adj[4][4] = {0};

// Undirected graph

adj[0][1] = adj[1][0] = 1;

adj[0][2] = adj[2][0] = 1;

adj[0][3] = adj[3][0] = 1;

adj[1][3] = adj[3][1] = 1;

adj[2][3] = adj[3][2] = 1;

for(int i = 0; i < V; i++) {

for(int j = 0; j < V; j++)

cout << adj[i][j] << " ";

cout << endl;

}

return 0;

}

⏱ Complexity (Adjacency Matrix)

Metric	Value
Space	O(V²)
Edge check	O(1)
Traversal	O(V²)

3️⃣ Adjacency List Implementation (MOST IMPORTANT)

Concept

Each vertex stores a list of neighbors
Uses vector / list

Representation

C++ Implementation

#include <iostream>
#include <vector>
using namespace std;

int main() {
int V = 4;
vector<int> adj[V];

// Undirected graph
adj[0].push_back(1);
adj[0].push_back(2);
adj[0].push_back(3);

adj[1].push_back(0);
adj[1].push_back(3);

adj[2].push_back(0);
adj[2].push_back(3);

adj[3].push_back(0);
adj[3].push_back(1);
adj[3].push_back(2);

for(int i = 0; i < V; i++) {
cout << i << " → ";
for(int x : adj[i])
cout << x << " ";
cout << endl;
}
return 0;
}

#include <iostream>

#include <vector>

using namespace std;

int main() {

int V = 4;

vector<int> adj[V];

// Undirected graph

adj[0].push_back(1);

adj[0].push_back(2);

adj[0].push_back(3);

adj[1].push_back(0);

adj[1].push_back(3);

adj[2].push_back(0);

adj[2].push_back(3);

adj[3].push_back(0);

adj[3].push_back(1);

adj[3].push_back(2);

for(int i = 0; i < V; i++) {

cout << i << " → ";

for(int x : adj[i])

cout << x << " ";

cout << endl;

}

return 0;

}

⏱ Complexity (Adjacency List)

Metric	Value
Space	O(V + E)
Traversal	O(V + E)

4️⃣ BFS Implementation (Graph Traversal)

Breadth First Search

Uses Queue
Level-by-level traversal

BFS Code (C++)

#include <queue>

void BFS(int start, vector<int> adj[], int V) {
    vector<bool> visited(V, false);
    queue<int> q;

    visited[start] = true;
    q.push(start);

    while(!q.empty()) {
        int node = q.front();
        q.pop();
        cout << node << " ";

        for(int x : adj[node]) {
            if(!visited[x]) {
                visited[x] = true;
                q.push(x);
            }
        }
    }
}

#include <queue>

void BFS(int start, vector<int> adj[], int V) {

vector<bool> visited(V, false);

queue<int> q;

visited[start] = true;

q.push(start);

while(!q.empty()) {

int node = q.front();

q.pop();

cout << node << " ";

for(int x : adj[node]) {

if(!visited[x]) {

visited[x] = true;

q.push(x);

}

5️⃣ DFS Implementation

Depth First Search

Uses recursion / stack
Goes deep first

DFS Code (C++)

void DFS(int node, vector<int> adj[], vector<bool>& visited) {
    visited[node] = true;
    cout << node << " ";

    for(int x : adj[node]) {
        if(!visited[x])
            DFS(x, adj, visited);
    }
}

void DFS(int node, vector<int> adj[], vector<bool>& visited) {

visited[node] = true;

cout << node << " ";

for(int x : adj[node]) {

if(!visited[x])

DFS(x, adj, visited);

}

6️⃣ Complete Graph + BFS + DFS Example

#include <iostream>
#include <vector>
#include <queue>
using namespace std;

void BFS(int start, vector<int> adj[], int V) {
    vector<bool> visited(V, false);
    queue<int> q;
    visited[start] = true;
    q.push(start);

    while(!q.empty()) {
        int node = q.front(); q.pop();
        cout << node << " ";
        for(int x : adj[node]) {
            if(!visited[x]) {
                visited[x] = true;
                q.push(x);
            }
        }
    }
}

void DFS(int node, vector<int> adj[], vector<bool>& visited) {
    visited[node] = true;
    cout << node << " ";
    for(int x : adj[node]) {
        if(!visited[x])
            DFS(x, adj, visited);
    }
}

int main() {
    int V = 4;
    vector<int> adj[V];

    adj[0] = {1, 2};
    adj[1] = {0, 3};
    adj[2] = {0, 3};
    adj[3] = {1, 2};

    cout << "BFS: ";
    BFS(0, adj, V);

    cout << "\nDFS: ";
    vector<bool> visited(V, false);
    DFS(0, adj, visited);

    return 0;
}

#include <iostream>

#include <vector>

#include <queue>

using namespace std;

void BFS(int start, vector<int> adj[], int V) {

vector<bool> visited(V, false);

queue<int> q;

visited[start] = true;

q.push(start);

while(!q.empty()) {

int node = q.front(); q.pop();

cout << node << " ";

for(int x : adj[node]) {

if(!visited[x]) {

visited[x] = true;

q.push(x);

}

void DFS(int node, vector<int> adj[], vector<bool>& visited) {

visited[node] = true;

cout << node << " ";

for(int x : adj[node]) {

if(!visited[x])

DFS(x, adj, visited);

}

int main() {

int V = 4;

vector<int> adj[V];

adj[0] = {1, 2};

adj[1] = {0, 3};

adj[2] = {0, 3};

adj[3] = {1, 2};

cout << "BFS: ";

BFS(0, adj, V);

cout << "\nDFS: ";

vector<bool> visited(V, false);

DFS(0, adj, visited);

return 0;

}

7️⃣ Directed Graph Implementation

For directed graph, add edge in one direction only:

8️⃣ Adjacency Matrix vs List

Feature	Matrix	List
Space	O(V²)	O(V+E)
Sparse Graph	❌ Bad	✅ Best
Dense Graph	✅ OK	❌
Interview Use	❌	✅

Interview Questions (Graphs Implementation)

Q1. Which graph representation is most used?
👉 Adjacency List

Q2. BFS uses which data structure?
👉 Queue

Q3. DFS uses which data structure?
👉 Stack / Recursion

Q4. Time complexity of BFS/DFS?
👉 O(V + E)

Final Summary

✔ Graphs implemented using matrix or list
✔ Adjacency list is preferred
✔ BFS → Queue
✔ DFS → Stack / Recursion
✔ Core topic for DSA & interviews

DSA Graphs Implementation