Introduction to Graphs

A graph is a collection of vertices (nodes) connected by edges (links). It is used to model relationships between objects, such as social networks, road maps, and computer networks.

1. Types of Graphs

• Directed Graph (Digraph): Edges have direction (A → B).
• Undirected Graph: Edges have no direction (A ↔ B).
• Weighted Graph: Edges have weights (costs).
• Unweighted Graph: All edges have equal weight.
• Cyclic Graph: Contains at least one cycle.
• Acyclic Graph: No cycles (like trees).
• Connected Graph: All vertices are reachable.
• Disconnected Graph: Some vertices are isolated.
• Bipartite Graph: Nodes can be divided into two independent sets.

2. Graph Representations

2.1 Adjacency Matrix

• Uses a 2D array (adj[n][n]), where n is the number of vertices.
• adj[i][j] = 1 if an edge exists, else 0.
• Space Complexity: O(V²) (not efficient for sparse graphs).

2.2 Adjacency List

• Uses an array of lists (vector adj[n]).
• More memory-efficient than an adjacency matrix.
• Space Complexity: O(V + E).

3. Graph Traversal Algorithms

Graph traversal is used to explore all the vertices and edges.

3.1 Breadth-First Search (BFS)

• Explores all neighbors before going deeper.
• Uses a queue (FIFO).
• Time Complexity: O(V + E).

3.2 Depth-First Search (DFS)

• Explores deep paths first.
• Uses a stack (LIFO) or recursion.
• Time Complexity: O(V + E).

4. Shortest Path Algorithms

Used to find the shortest distance from a source vertex to all other vertices.

4.1 Dijkstra’s Algorithm (Greedy)

• Finds the shortest path in weighted graphs (non-negative weights).
• Uses a priority queue (min-heap).
• Time Complexity: O((V + E) log V).

4.2 Bellman-Ford Algorithm

• Finds the shortest path in graphs with negative weights.
• Uses relaxation technique (V-1 iterations).
• Time Complexity: O(VE).

4.3 Floyd-Warshall Algorithm

• Used for all-pairs shortest path.
• Time Complexity: O(V³) (not efficient for large graphs).

5. Minimum Spanning Tree (MST) Algorithms

Used to find the minimum cost tree that connects all vertices.

5.1 Kruskal’s Algorithm

• Greedy algorithm that picks the smallest edge first.
• Uses Disjoint Set Union (DSU).
• Time Complexity: O(E log E).

5.2 Prim’s Algorithm

• Greedy algorithm that grows MST from any vertex.
• Uses priority queue (min-heap).
• Time Complexity: O((V + E) log V).

6. Cycle Detection in Graphs

6.1 Cycle Detection in Undirected Graph

• Using DFS: If a visited node appears again (except its parent), there’s a cycle.

6.2 Cycle Detection in Directed Graph

• Using DFS and Recursion Stack: If a node appears in the recursion stack, a cycle exists.
• Using Kahn’s Algorithm (Topological Sorting).

7. Topological Sorting (for DAGs)

• Used for scheduling tasks, course prerequisites, etc.
• Only valid for Directed Acyclic Graphs (DAGs).
• Algorithms:
  • DFS-Based (Using Stack): O(V + E)
  • Kahn’s Algorithm (Using In-degree): O(V + E)

8. Strongly Connected Components (SCCs)

Used to find strongly connected subgraphs in directed graphs.

• Kosaraju’s Algorithm:
  1. Perform DFS to get finishing times.
  2. Reverse the graph.
  3. Perform DFS again on reversed graph.
• Time Complexity: O(V + E).

9. Other Important Graph Algorithms

9.1 Bipartite Graph Check

• Using BFS/DFS with 2-coloring technique.

9.2 Bridges in Graph (Tarjan’s Algorithm)

• Used in network reliability analysis.

9.3 Eulerian Path & Circuit

• Eulerian Path: Uses each edge exactly once.
• Eulerian Circuit: Starts and ends at the same vertex.

9.4 Hamiltonian Path & Circuit

• Visits each vertex exactly once.

10. Graph Problem List

10.1 Basics of Graph

1-1 Simple DFS/BFS

• Evaluate Division
• Keys and Rooms
• Find If Path Exists in Graph
• Detonate the Maximum Bombs

1-2 Count Degrees

• Find the Town Judge
• Find Center of Star Graph

1-3 Topological Sorting

• Course Schedule
• Course Schedule II

1-4 Connected Component/Union Find (Disjoint-set)

• Number of Provinces
• Redundant Connection

1-5 Bipartite

• Is Graph Bipartite
• Possible Bipartition

10.2 Medium Level Topics

2-1 BFS Variants

• Minimum Height Trees

2-2 Shortest Path - Dijkstra Algorithm

• Network Delay Time

2-3 Shortest Path - Bellman-Ford Algorithm

• Cheapest Flights Within K Stops

2-4 Shortest Path - Floyd-Warshall Algorithm

• Find the City with the Smallest Number of Neighbors

2-5 Cycle Detection

• Largest Color Value in a Directed Graph

2-6 Minimum Spanning Tree - Kruskal's Algorithm

• Find Critical and Pseudo-Critical Edges

10.3 Advanced Level Topics

• Euler Tour, De Bruijn Sequence, Game on Graph, Tarjan's Algorithm, DP Applications, etc.