DSA — Non-Linear DS

Graph

Set of vertices connected by edges. Directed or undirected, weighted or unweighted. Drag nodes to rearrange.

— min read
V+ESpace
Directed& Undirected
WeightedPaths
CyclicAcyclic
Adj ListAdj Matrix
// GRAPH
Interactive visualization
Representations
Python Code
Complexity
Quiz
Practice
01
Adjacency List
Each vertex stores list of neighbors. Space: O(V+E).
graph = {0:[1,2], 1:[2]}
02
Adjacency Matrix
V×V matrix. Space: O(V²). O(1) edge lookup.
matrix[u][v] = 1
03
Edge List
List of all (u,v) pairs. Compact.
edges = [(0,1),(1,2)]
04
When to Use
List: sparse. Matrix: dense or need O(1) edge check.
python 
from collections import defaultdict, deque

graph = defaultdict(list)
graph[0].append(1); graph[0].append(2)
graph[1].append(3)

def bfs(graph, start):
    visited, q = {start}, deque([start])
    while q:
        node = q.popleft()
        for nb in graph[node]:
            if nb not in visited:
                visited.add(nb); q.append(nb)
O(V+E)
BFS/DFS
Visit every vertex and edge once
O(V²)
Matrix Space
Dense graph representation
O(V+E)
List Space
Sparse graph representation
O(V+E)
Topological
Kahn's BFS or DFS approach
For a sparse graph, the best representation is:
Progress 0 / 10 solved
10 problems · 7 PBC · 3 Startup
#096 Number of Islands Amazon, Google, Meta PBC →
#097 Clone Graph Google, Meta PBC →
#098 Course Schedule Meta, Microsoft PBC →
#099 Pacific Atlantic Water Flow Amazon PBC →
#100 Detect Cycle in Directed Graph Google PBC →
#101 Check Bipartite Graph Google, Amazon PBC →
#102 Topological Sorting Amazon PBC →
#107 Detect Cycle in Undirected Graph Zomato STARTUP →
#109 Minimum Spanning Tree (Prim's) Meesho STARTUP →
#110 Kruskal's Algorithm Cogoport STARTUP →
← Hash Table