πΈοΈ Graph - Networks & Connections
π΄ Advanced Advanced 90 min read
π― What is a Graph?
A Graph is a collection of vertices (nodes) connected by edges. Graphs model relationships - social networks, maps, web pages, dependencies, and countless real-world systems. G = (V, E) where V = vertices, E = edges.
π Graph Terminology & Types
Directed vs Undirected
Undirected: A---B (bidirectional)
Directed: AβB (one-way)Weighted vs Unweighted
Weighted: A--5--B (edges have cost)
Unweighted: A---B (all edges equal)π Graph Representations
1. Adjacency Matrix (O(VΒ²) space)
// Good for dense graphs, O(1) edge check
$adjMatrix = [
// 0 1 2 3
[0, 1, 0, 1], // 0 connected to 1,3
[1, 0, 1, 0], // 1 connected to 0,2
[0, 1, 0, 1], // 2 connected to 1,3
[1, 0, 1, 0], // 3 connected to 0,2
];2. Adjacency List (O(V+E) space) - Preferred
$adjList = [
0 => [1, 3],
1 => [0, 2],
2 => [1, 3],
3 => [0, 2],
];π BFS & DFS - Core Graph Traversals
// BFS - Queue-based, finds shortest path in unweighted graphs
function bfs(array $graph, int $start): array {
$visited = [$start => true];
$queue = [$start];
$result = [];
while (!empty($queue)) {
$node = array_shift($queue);
$result[] = $node;
foreach ($graph[$node] as $neighbor) {
if (!isset($visited[$neighbor])) {
$visited[$neighbor] = true;
$queue[] = $neighbor;
}
}
}
return $result;
}
// DFS - Stack/Recursion-based, explores depth first
function dfs(array $graph, int $node, array &$visited = []): array {
$visited[$node] = true;
$result = [$node];
foreach ($graph[$node] as $neighbor) {
if (!isset($visited[$neighbor])) {
$result = array_merge($result, dfs($graph, $neighbor, $visited));
}
}
return $result;
}π Representation Comparison
| Operation | Adjacency Matrix | Adjacency List |
|---|---|---|
| Space | O(VΒ²) | O(V+E) |
| Add Edge | O(1) | O(1) |
| Remove Edge | O(1) | O(degree) |
| Check Edge | O(1) | O(degree) |
| Find All Neighbors | O(V) | O(degree) |
πΊοΈ Graph Algorithms Overview
| BFS | Level-order traversal | O(V+E) | Shortest path (unweighted) |
| DFS | Depth-first traversal | O(V+E) | Cycle detection, topological sort |
| Dijkstra | Shortest path (non-negative) | O((V+E)log V) | GPS navigation |
| Bellman-Ford | Shortest path (negative OK) | O(VE) | Detect negative cycles |
| Floyd-Warshall | All-pairs shortest path | O(VΒ³) | Small dense graphs |
| Prim/Kruskal | Minimum Spanning Tree | O(E log V) | Network design |
| Topological Sort | Linear ordering of DAG | O(V+E) | Task scheduling |
| Union-Find | Connected components | O(Ξ±(V)) | Kruskal's, dynamic connectivity |
π Detailed implementations of each graph algorithm are in the Graph Algorithms section.
πΌ Interview Questions
BFS: shortest path, level-order, closer nodes. Uses Queue. DFS: path existence, topological sort, cycle detection, maze solving. Uses Stack/recursion. BFS uses more memory for wide graphs.
Matrix: O(1) edge check, O(VΒ²) space. Good for dense graphs. List: O(degree) edge check, O(V+E) space. Good for sparse graphs (most real-world graphs are sparse).