Graphs: Matrix, List, BFS, DFS, and Dijkstra

Structural Foundations

The Language of Graphs: Vertices and Edges

A graph G = (V, E) models arbitrary relationships without fixed hierarchy. V are vertices; E are edges or connections.

Undirected Graph: Connections are bidirectional. (u, v) is identical to (v, u). Friendship networks or two-way roads.

Memory Structures

Representation depends on density. Dense graphs (|E| ≈ |V|²) fit matrices; sparse graphs (|E| ≪ |V|²) save memory with lists.

4-Node Graph Click edges to toggle

	A (0)	B (1)	C (2)	D (3)

Space: O(V²). Adjacency lookup: O(1).

Breadth Traversals

BFS expands layer by layer from root using a FIFO Queue. Finds the shortest path in number of hops.

FIFO Queue

[A]

Processing Visited Unvisited

Visit Order

A

Depth Traversals

DFS plunges deep into one path until reaching a dead end and then backtracks. Uses a LIFO Stack or the recursion call stack.

Call Stack / LIFO Stack

dfs(A)

Current Action

Starting at root node A

Weighted Shortest Paths

Computes single-source shortest paths on non-negative weighted graphs. Greedy paradigm with edge relaxation.

PriorityQueue<NodeDist>: (A, 0)

Vertex	Tentative Dist	Previous	Settled

Source node A starts with dist 0. All others at infinity (∞).

Dynamic Programming on Graphs

Computes all-pairs shortest paths in O(V³). Gradually checks if routing through pivot k yields a shorter path between i and j.

Relaxation rule with pivot k: D[i][j] = Math.min(D[i][j], D[i][k] + D[k][j])

D^(k)	A	B	C

k = 0: Direct adjacency matrix without intermediate vertices.