Graph Data Structure in C++ (Self Complete Revision Notes + Problems)
Ujjawal Pandey
932
Graph TheoryInterview

image

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.

🔹 Types of Graphs

  1. Directed Graph (Digraph): Edges have direction (A → B).
  2. Undirected Graph: Edges have no direction (A ↔ B).
  3. Weighted Graph: Edges have weights (costs).
  4. Unweighted Graph: All edges have equal weight.
  5. Cyclic Graph: Contains at least one cycle.
  6. Acyclic Graph: No cycles (like trees).
  7. Connected Graph: All vertices are reachable.
  8. Disconnected Graph: Some vertices are isolated.
  9. 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:
  • Perform DFS to get finishing times.
  • Reverse the graph.
  • Perform DFS again on reversed graph.
  • Time Complexity: O(V + E).

📌 9. Other Important Graph Algorithms:

  • Bipartite Graph Check:
  • Using BFS/DFS with 2-coloring technique.
  • Bridges in Graph (Tarjan’s Algorithm):
  • Used in network reliability analysis.
  • Eulerian Path & Circuit:
  • Eulerian Path: Uses each edge exactly once.
  • Eulerian Circuit: Starts and ends at the same vertex.
  • Hamiltonian Path & Circuit:
  • Visits each vertex exactly once.

📌 10. Summary Table:

image

Graph Problem List Part 1(Basics of Graph):

1-1 Simple DFS/BFS

  1. https://leetcode.com/problems/evaluate-division
  2. https://leetcode.com/problems/keys-and-rooms
  3. https://leetcode.com/problems/get-watched-videos-by-your-friends
  4. https://leetcode.com/problems/find-if-path-exists-in-graph
  5. https://leetcode.com/problems/detonate-the-maximum-bombs

1-2 Count Degrees

  1. https://leetcode.com/problems/find-the-town-judge
  2. https://leetcode.com/problems/minimum-number-of-vertices-to-reach-all-nodes
  3. https://leetcode.com/problems/maximal-network-rank
  4. https://leetcode.com/problems/minimum-degree-of-a-connected-trio-in-a-graph
  5. https://leetcode.com/problems/count-pairs-of-nodes
  6. https://leetcode.com/problems/find-center-of-star-graph
  7. https://leetcode.com/problems/maximum-total-importance-of-roads
  8. https://leetcode.com/problems/node-with-highest-edge-score
  9. https://leetcode.com/problems/maximum-star-sum-of-a-graph
  10. https://leetcode.com/problems/add-edges-to-make-degrees-of-all-nodes-even
  11. https://leetcode.com/problems/find-champion-ii

1-3 Topological Sorting

  1. https://leetcode.com/problems/course-schedule
  2. https://leetcode.com/problems/course-schedule-ii
  3. https://leetcode.com/problems/all-paths-from-source-to-target
  4. https://leetcode.com/problems/find-eventual-safe-states
  5. https://leetcode.com/problems/sort-items-by-groups-respecting-dependencies
  6. https://leetcode.com/problems/all-ancestors-of-a-node-in-a-directed-acyclic-graph
  7. https://leetcode.com/problems/course-schedule-iv
  8. https://leetcode.com/problems/strange-printer-ii
  9. https://leetcode.com/problems/parallel-courses-iii
  10. https://leetcode.com/problems/find-all-possible-recipes-from-given-supplies
  11. https://leetcode.com/problems/build-a-matrix-with-conditions

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

  1. https://leetcode.com/problems/number-of-provinces
  2. https://leetcode.com/problems/redundant-connection
  3. https://leetcode.com/problems/redundant-connection-ii
  4. https://leetcode.com/problems/most-stones-removed-with-same-row-or-column
  5. https://leetcode.com/problems/satisfiability-of-equality-equations
  6. https://leetcode.com/problems/rank-transform-of-a-matrix
  7. https://leetcode.com/problems/number-of-operations-to-make-network-connected
  8. https://leetcode.com/problems/remove-max-number-of-edges-to-keep-graph-fully-traversable
  9. https://leetcode.com/problems/checking-existence-of-edge-length-limited-paths
  10. https://leetcode.com/problems/process-restricted-friend-requests
  11. https://leetcode.com/problems/find-all-people-with-secret
  12. https://leetcode.com/problems/count-unreachable-pairs-of-nodes-in-an-undirected-graph
  13. https://leetcode.com/problems/minimum-score-of-a-path-between-two-cities
  14. https://leetcode.com/problems/count-the-number-of-complete-components

1-5 Bipartite

  1. https://leetcode.com/problems/is-graph-bipartite
  2. https://leetcode.com/problems/possible-bipartition

Graph Problem List Part 2(Medium level topics of Graph):

2-1 BFS Variants (0-1 BFS, multi-source BFS)

  1. https://leetcode.com/problems/minimum-height-trees
  2. https://leetcode.com/problems/minimize-malware-spread
  3. https://leetcode.com/problems/minimize-malware-spread-ii
  4. https://leetcode.com/problems/maximum-candies-you-can-get-from-boxes

2-2 Shortest Path - Dijkstra Algorithm

  1. https://leetcode.com/problems/network-delay-time
  2. https://leetcode.com/problems/reachable-nodes-in-subdivided-graph
  3. https://leetcode.com/problems/path-with-maximum-probability
  4. https://leetcode.com/problems/minimum-cost-to-make-at-least-one-valid-path-in-a-grid
  5. https://leetcode.com/problems/number-of-restricted-paths-from-first-to-last-node
  6. https://leetcode.com/problems/minimum-cost-to-reach-destination-in-time
  7. https://leetcode.com/problems/number-of-ways-to-arrive-at-destination
  8. https://leetcode.com/problems/the-time-when-the-network-becomes-idle
  9. https://leetcode.com/problems/second-minimum-time-to-reach-destination
  10. https://leetcode.com/problems/minimum-weighted-subgraph-with-the-required-paths
  11. https://leetcode.com/problems/minimum-obstacle-removal-to-reach-corner
  12. https://leetcode.com/problems/minimum-cost-of-a-path-with-special-roads
  13. https://leetcode.com/problems/minimum-time-to-visit-a-cell-in-a-grid
  14. https://leetcode.com/problems/modify-graph-edge-weights

2-3 Shortest Path - Bellman–Ford Algorithm

  1. https://leetcode.com/problems/shortest-path-with-alternating-colors
  2. https://leetcode.com/problems/cheapest-flights-within-k-stops

2-4 Shortest Path - Floyd–Warshall Algorithm

  1. https://leetcode.com/problems/find-the-city-with-the-smallest-number-of-neighbors-at-a-threshold-distance
  2. https://leetcode.com/problems/design-graph-with-shortest-path-calculator
  3. https://leetcode.com/problems/number-of-possible-sets-of-closing-branches
  4. https://leetcode.com/problems/minimum-cost-to-convert-string-i
  5. https://leetcode.com/problems/minimum-cost-to-convert-string-ii
  6. https://leetcode.com/problems/count-the-number-of-houses-at-a-certain-distance-i

2-5 Cycle Detection

  1. https://leetcode.com/problems/largest-color-value-in-a-directed-graph
  2. https://leetcode.com/problems/maximum-employees-to-be-invited-to-a-meeting
  3. https://leetcode.com/problems/find-closest-node-to-given-two-nodes
  4. https://leetcode.com/problems/longest-cycle-in-a-graph
  5. https://leetcode.com/problems/shortest-cycle-in-a-graph
  6. https://leetcode.com/problems/count-visited-nodes-in-a-directed-graph

2-6 Minimum Spanning Tree - Kruskal's Algorithm

  1. https://leetcode.com/problems/find-critical-and-pseudo-critical-edges-in-minimum-spanning-tree
  2. https://leetcode.com/problems/min-cost-to-connect-all-points

Graph Problem List Part 3(Advanced Level topics of Graph):

3-1 Euler Tour

  1. https://leetcode.com/problems/reconstruct-itinerary
  2. https://leetcode.com/problems/valid-arrangement-of-pairs

3-2 De Bruijn Sequence

  1. https://leetcode.com/problems/cracking-the-safe

3-3 Game on Graph

  1. https://leetcode.com/problems/cat-and-mouse
  2. https://leetcode.com/problems/cat-and-mouse-ii

3-4 Graph Cloning

  1. https://leetcode.com/problems/clone-graph

3-5 Construction

  1. https://leetcode.com/problems/maximum-score-of-a-node-sequence
  2. https://leetcode.com/problems/couples-holding-hands

3-6 Hamilton Cycle/Travelling Sellsman

  1. https://leetcode.com/problems/shortest-path-visiting-all-nodes

3-7 Tarjan's Algorithm

  1. https://leetcode.com/problems/critical-connections-in-a-network

3-8 DP applications

  1. https://leetcode.com/problems/maximum-path-quality-of-a-graph
  2. https://leetcode.com/problems/parallel-courses-ii
  3. https://leetcode.com/problems/flower-planting-with-no-adjacent
  4. https://leetcode.com/problems/loud-and-rich
  5. https://leetcode.com/problems/longest-increasing-path-in-a-matrix
  6. https://leetcode.com/problems/number-of-increasing-paths-in-a-grid

3-9 Ad-Hoc

  1. https://leetcode.com/problems/number-of-ways-to-reconstruct-a-tree
  2. https://leetcode.com/problems/divide-nodes-into-the-maximum-number-of-groups
  3. https://leetcode.com/problems/count-the-number-of-houses-at-a-certain-distance-ii
Comments (0)