๐บ๏ธ Graphs
One-line summary: Nodes connected by edges โ BFS for shortest path, DFS for connectivity/cycle, topological sort for dependencies, Union-Find for dynamic connectivity.
Enhanced Visualizationโ
Interactive demonstration of BFS, DFS, and Dijkstra's algorithm with path finding and performance analysis
Core Graph Conceptsโ
The enhanced animation above demonstrates three fundamental graph algorithms:
๐ต Breadth-First Search (BFS)โ
- Strategy: Explores nodes level by level using a queue
- Path: A โ B โ C โ F (shortest in unweighted graphs)
- Time: O(V + E) | Space: O(V)
- Use Cases: Shortest path, social networks, web crawling
๐ฃ Depth-First Search (DFS)โ
- Strategy: Explores as far as possible using recursion/stack
- Path: A โ D โ E โ F (explores deeply first)
- Time: O(V + E) | Space: O(V)
- Use Cases: Topological sorting, cycle detection, connectivity
๐ก Dijkstra's Algorithmโ
- Strategy: Uses priority queue for weighted shortest paths
- Path: A โ B โ E โ F (Distance: 7 - optimal weighted path)
- Time: O((V + E) log V) | Space: O(V)
- Use Cases: GPS navigation, network routing, flight planning
Graph Fundamentalsโ
G = (V, E). Types: directed, undirected, weighted, DAG.
Representations:
- Adjacency List:
Map<node, neighbors[]>โ O(V+E) space โ preferred. - Adjacency Matrix:
matrix[u][v]โ O(Vยฒ) โ dense graphs.
Also covers: BFS pattern, DFS pattern, topological sort, Union-Find, Dijkstra, Bellman-Ford.
Time & Space Complexityโ
| Algorithm | Time | Space |
|---|---|---|
| BFS / DFS | O(V + E) | O(V) |
| Dijkstra (min-heap) | O((V+E) log V) | O(V) |
| Topological Sort (Kahn) | O(V + E) | O(V) |
| Union-Find (with compression) | O(ฮฑ(n)) per op | O(n) |
Common Patternsโ
BFS (Shortest Path)โ
function bfs(graph, start) {
const visited = new Set([start]),
queue = [start];
while (queue.length) {
const node = queue.shift();
for (const nb of graph.get(node) || [])
if (!visited.has(nb)) {
visited.add(nb);
queue.push(nb);
}
}
}
DFS (Connected Components)โ
function dfs(graph, node, visited = new Set()) {
visited.add(node);
for (const nb of graph.get(node) || []) if (!visited.has(nb)) dfs(graph, nb, visited);
}
Topological Sort (Kahn's BFS)โ
function topoSort(n, edges) {
const inDeg = new Array(n).fill(0),
adj = Array.from({ length: n }, () => []);
for (const [a, b] of edges) {
adj[b].push(a);
inDeg[a]++;
}
const queue = [],
order = [];
for (let i = 0; i < n; i++) if (!inDeg[i]) queue.push(i);
while (queue.length) {
const node = queue.shift();
order.push(node);
for (const nb of adj[node]) if (--inDeg[nb] === 0) queue.push(nb);
}
return order.length === n ? order : []; // empty = cycle
}
Union-Findโ
const parent = Array.from({ length: n }, (_, i) => i);
function find(x) {
return parent[x] === x ? x : (parent[x] = find(parent[x]));
}
function union(x, y) {
parent[find(x)] = find(y);
}
Pitfallsโ
- Forgetting to mark visited before enqueuing (BFS) โ causes duplicates
- Cycle detection: in undirected graph pass parent to DFS to avoid false positives
- Topological sort only valid on DAG โ if cycle exists, output length < n
Practice Problemsโ
Related Topicsโ
- Trees โ trees are acyclic connected graphs
- Heap โ Dijkstra requires min-heap
- Dynamic Programming โ DP on DAGs
Graph Data Structure Referenceโ
Runnable implementations (with tests) live alongside this guide in this folder: Graph.js, GraphVertex.js, GraphEdge.js, plus algorithm folders such as dijkstra/, bellman-ford/, kruskal/, prim/, topological-sorting/, and more.
In computer science, a graph is an abstract data type that is meant to implement the undirected graph and directed graph concepts from mathematics, specifically the field of graph theory.
A graph data structure consists of a finite (and possibly mutable) set of vertices or nodes or points, together with a set of unordered pairs of these vertices for an undirected graph or a set of ordered pairs for a directed graph. These pairs are known as edges, arcs, or lines for an undirected graph and as arrows, directed edges, directed arcs, or directed lines for a directed graph. The vertices may be part of the graph structure, or may be external entities represented by integer indices or references.
Referencesโ
โ Back to Home ยท ยฉ sparshjaswal