←Back to Tutorials
Graph Theory: Fundamentals & Algorithms
Master graph data structures and essential algorithms: BFS, DFS, shortest paths, MST, and topological sort—with code, complexity, and interview patterns.
80 minutes
6Detailed Sections
Senior Level
A graph is a collection of vertices (nodes) connected by edges. Unlike trees, graphs can have cycles and multiple paths between any two nodes.
- Key types:
- Undirected vs. Directed (Digraph): Edges have no direction vs. edges that point from one node to another.
- Weighted vs. Unweighted: Edges have values (cost, distance) vs. all edges being equal.
- Cyclic vs. Acyclic: Contains at least one cycle vs. no cycles (e.g., trees).
- Connected vs. Disconnected: A path exists between every pair of nodes vs. isolated subgraphs.
- Terminology: Degree is the number of edges connected to a node. In directed graphs, we have In-degree and Out-degree. A Path is a sequence of edges; a Cycle is a path that starts and ends at the same node.
Key Takeaways
1
Graph: Vertices + Edges; can have cycles and multiple paths2
Directed: Edges have direction (u → v); Undirected: (u, v) is bi-directional3
Weighted: Edges have costs; Unweighted: All edges equal4
Degree: Number of neighbors; In-degree/Out-degree for digraphs5
Use cases: Social networks, maps, dependency resolution, recommendation engines6
Senior takeaway: Graphs are the most generic model of relationshipsVisual Diagram
┌─────────────────────────────────────────────────────────┐
│ Graph Structures │
├─────────────────────────────────────────────────────────┤
│ Undirected Directed (Weighted) │
│ │
│ (A)---(B) (A) ─5─▶ (B) │
│ | | ▲ | │
│ | | 2 10 │
│ (C)---(D) | ▼ │
│ (C) ◀──── (D) │
│ │
│ Vertices: {A,B,C,D} Edges: {(A,B,5), (B,D,10),│
│ (D,C,?), (C,A,2)} │
└─────────────────────────────────────────────────────────┘