Definitions – Topological Sort – Shortest-Path Algorithms – Unweighted Shortest Paths –

Dijkstra’s Algorithm – Minimum Spanning Tree – Prim’s Algorithm – Applications of Depth- First
Search – Undirected Graphs – Bi-connectivity – Introduction to NP​
​
​

Topological Sorting
​
Topological sorting for Directed Acyclic Graph (DAG) is a linear ordering of
vertices such that for every directed edge u-v, vertex u comes before v in the
ordering.
Note: Topological Sorting for a graph is not possible if the graph is not a
DAG.​
​
Input: V = 6, edges = [[2, 3], [3, 1], [4, 0], [4, 1], [5, 0], [5, 2]]​
Example:

​
​
Output: 5 4 2 3 1 0
Explanation: The first vertex in topological sorting is always a vertex with an
in-degree of 0 (a vertex with no incoming edges). A topological sorting of
the following graph is "5 4 2 3 1 0". There can be more than one topological
sorting for a graph. Another topological sorting of the following graph is "4 5
2 3 1 0". ​
​
​
2. Concept

●​ It represents a sequence in which tasks (or nodes) should be

performed.​

●​ It is mainly used in scenarios where certain tasks must be done before

others.​

3. Importance / Applications

Topological sorting is important in various fields like:

●​ Task Scheduling (e.g., job execution order)​

●​ Course Prerequisite Planning (do course A before B)​

●​ Build Systems (compiling code with dependencies)​

●​ Project Management (dependency resolution in tasks)​

4. Conditions for Topological Sorting

●​ The graph must be Directed.​

●​ The graph must be Acyclic (no cycles).​

●​ If a cycle exists, topological sorting is not possible.​

5. Algorithms Used

There are two main algorithms:

●​ Kahn’s Algorithm (BFS Based)​

●​ DFS-Based Algorithm​

Let’s describe Kahn’s Algorithm:

6. Kahn’s Algorithm (Step-by-Step)

1.​ Calculate in-degree of all vertices (number of incoming edges).​

2.​ Enqueue all vertices with in-degree = 0.​

3.​ While the queue is not empty:​

a. Remove a vertex u from the queue and add it to the topological
order.​
b. For each adjacent vertex v of u, decrease its in-degree by 1.​
 c. If the in-degree of v becomes 0, enqueue v.​

4.​ If topological order contains all vertices, sorting is successful.​

5.​ If not, the graph has a cycle.

8. Time and Space Complexity

●​ Time Complexity: O(V + E)​

●​ Space Complexity: O(V)​

9. DFS-Based Algorithm (Alternative)

●​ Perform DFS traversal​

●​ Push the vertex to a stack after visiting all its neighbors​

●​ Reverse the stack to get topological order​

10. When is Topological Sorting Not Possible?

●​ If the graph contains any cycle, then no valid ordering is possible.​

●​ Example: A → B → C → A (Cycle)​

11. Summary

●​ Topological sort is used to maintain a dependency order.​

 ●​ Only valid for DAGs.​

●​ Common in real-world scheduling and dependency management.​

What are the Shortest Path Algorithms?

The shortest path algorithms are the ones that focus on calculating the
minimum travelling cost from source node to destination node of a graph in
optimal time and space complexities.

Shortest path in an unweighted graph

Given an unweighted, undirected graph of V nodes and E edges, a source
node S, and a destination node D, we need to find the shortest path from
node S to node D in the graph​
​

​
​
nput: V = 8, E = 10, S = 0, D = 7, edges[][] = {{0, 1}, {1, 2}, {0, 3}, {3, 4}, {4, 7},
{3, 7}, {6, 7}, {4, 5}, {4, 6}, {5, 6}}​
Output: 0 3 7​
Explanation: The shortest path is 0 -> 3 -> 7.
Input: V = 8, E = 10, S = 2, D = 6, edges[][] = {{0, 1}, {1, 2}, {0, 3}, {3, 4}, {4, 7},
{3, 7}, {6, 7}, {4, 5}, {4, 6}, {5, 6}}​
Output: 2 1 0 3 4 6​
Explanation: The shortest path is 2 -> 1 -> 0 -> 3 - > 4 -> 6.

Approach:

The idea is to use a modified version of Breadth-First Search in which we

keep storing the parent of a given vertex while doing the breadth-first search.
We first initialize an array dist[0, 1, ...., v-1] such that dist[i] stores the
distance of vertex i from the source vertex and array par[0, 1, ....., v-1] such
that par[i] represents the parent of the vertex i in the breadth-first search
starting from the source.

Dijkstra's Algorithm
Now we get the length of the path from source to any other vertex from
array dist[], and for printing the path from source to any vertex we can use
array par[].

Given a weighted undirected graph represented as an edge list and a source

vertex src, find the shortest path distances from the source vertex to all
other vertices in the graph. The graph contains V vertices, numbered from 0 to
V - 1.

Note: The given graph does not contain any negative edge.​
​
Input: src = 0, V = 5, edges[][] = [[0, 1, 4], [0, 2, 8], [1, 4, 6], [2, 3, 2], [3, 4,
10]] ​
​

Output: 0 4 8 10 10​
Explanation: Shortest Paths: ​
0 to 1 = 4. 0 → 1​
0 to 2 = 8. 0 → 2​
0 to 3 = 10. 0 → 2 → 3​
0 to 4 = 10. 0 → 1 → 4
🔍 Depth-First Search (DFS)
Depth-First Search (DFS) is a graph traversal algorithm that starts from a
selected node (called the source or root) and explores as far as possible
along each branch before backtracking.

●​ DFS can be implemented recursively or using an explicit stack.​

●​ It works on both directed and undirected graphs.​

🧠 How DFS Works (Step-by-Step)

Let’s take an example of an undirected graph:

🎯 Graph Example:

​
🔁 DFS Traversal (Starting from A):
1.​ Visit A → Mark A visited​

2.​ Go to B (neighbor of A) → Mark B visited​

3.​ Go to D (neighbor of B) → Mark D visited​

4.​ D has no unvisited neighbors → Backtrack​

5.​ Back to B → B is done → Backtrack to A​

6.​ From A → Go to C (unvisited neighbor)​

7.​ C → E → F (visit and mark each)​

8.​ Done!

✅ DFS Order:
A→B→D→C→E→F

📊 Diagram of DFS Traversal

Here's a visual representation of DFS:

🌐 Applications of DFS
DFS is a powerful algorithm used in many important graph-based problems.

1. 🔄 Cycle Detection in Graphs

●​ DFS can help detect cycles in both directed and undirected graphs.​

●​ If we visit an already visited node not through the parent, it indicates a

cycle.

2. 🔁 Topological Sorting
●​ Applicable only in Directed Acyclic Graphs (DAGs).​
 ●​ DFS is used to sort nodes such that for every directed edge u → v, u
comes before v.

3. 🌐 Connected Components in Undirected Graphs

●​ DFS can be used to find connected components (subgraphs where any
two vertices are connected).​

●​ Run DFS from an unvisited node to discover all nodes in that

component.

🌳 What is a Spanning Tree?

A Spanning Tree of a connected, undirected graph is a subgraph that:

●​ Includes all the vertices of the graph.​

●​ Has no cycles.​

●​ Is a tree (i.e., connected and acyclic).​

●​ Has exactly (V - 1) edges, where V is the number of vertices.​

🧮 What is a Minimum Spanning Tree (MST)?

A Minimum Spanning Tree (MST) is a spanning tree with the minimum
possible total edge weight.

🎯 Goal: Connect all nodes with minimum cost and no cycles.

✅ Properties of MST:
 ●​ MST has V-1 edges for V vertices.​

●​ MST is not unique if multiple edges have the same weight.​

●​ MST doesn’t contain any cycles.

💡 MST Using Kruskal’s Algorithm (Step-by-Step)

✨ Kruskal’s Algorithm:
1.​ Sort all edges by weight (ascending).​

2.​ Pick the smallest edge. If it doesn’t form a cycle, include it.​

3.​ Repeat until you have V-1 edges in the MST.

🪜 Steps:
Sorted edges:

●​ B–C (1)​

●​ A–B (2)​

●​ A–D (3)​

●​ C–E (4)​

●​ B–E (5)​

●​ A–C (6)​
 ●​ D–E (7)​

1.​ Include B–C (1)​

2.​ Include A–B (2)​

3.​ Include A–D (3)​

4.​ Include C–E (4)​

✔️ We now have 4 edges (for 5 nodes)​
✅ Final MST:
Edges: B–C, A–B, A–D, C–E​
Total weight = 1 + 2 + 3 + 4 = 10

🔁 MST Using Prim’s Algorithm

✨ Prim’s Algorithm:
1.​ Start from any node.​

2.​ At each step, pick the smallest edge that connects a visited node to an
unvisited node.​

3.​ Repeat until all nodes are included.​

✅ Result will be same MST if all weights are unique.

🧠 Real-Life Applications of MST
Application Description

Network Cable TV, Internet wiring, or telephone

Design networks

Road Minimum cost roads connecting cities

Construction

Electrical Grids Connecting substations at minimal

wiring cost

Cluster Grouping data points in machine

Analysis learning

Civil Laying out pipes or wires efficiently

Engineering

🌟 What is Prim’s Algorithm?

Prim's Algorithm builds the Minimum Spanning Tree by:

●​ Starting from any vertex.​

●​ At each step, adding the cheapest edge from the visited set to an
unvisited vertex.​

●​ Repeating until all vertices are connected.​

✅ Key Features of Prim’s Algorithm

 Feature Description

Approach Greedy

Graph Type Connected, undirected, weighted

Cycle Ensures no cycles while expanding the MST

Avoidance

Edge Always pick the minimum weight edge from

Selection the visited set

🔁 Step-by-Step Procedure
1.​ Initialize an empty MST.​

2.​ Choose any vertex as the starting point.​

3.​ Add it to the visited set.​

4.​ From all edges connecting visited ↔ unvisited, pick the

minimum-weight edge.​

5.​ Add the selected edge and vertex to MST.​

6.​ Repeat until all vertices are included.

📘 1. Undirected Graphs
An undirected graph is a graph where edges have no direction. That means
if there is an edge between nodes u and v, you can travel from u to v and
also from v to u.

📌 Key Terminology:
●​ Vertex (Node): A point in the graph.​

●​ Edge: A connection between two vertices.​

●​ Adjacent vertices: Two vertices connected directly by an edge.​

●​ Degree of a vertex: Number of edges connected to it.

✅ Properties:
●​ Undirected: Edge (A–B) is same as (B–A)​

●​ Connected: There’s a path between any two vertices​

●​ May contain cycles

🔁 2. Bi-Connectivity in Undirected Graphs

🎯 What is Bi-connectivity?
A graph is bi-connected (or 2-vertex-connected) if:

●​ It is connected​
 ●​ There are no articulation points (i.e., no single vertex whose removal
disconnects the graph)​

🔍 Articulation Point (Cut Vertex):

A vertex in an undirected graph whose removal increases the number of
connected components.

🧠 How to check Bi-connectivity?

Use Depth-First Search (DFS) to find:

●​ Articulation points​

●​ Low values (earliest reachable ancestor)​

✅ Algorithm (DFS-based):
1.​ Do a DFS traversal.​

2.​ Keep track of:​

○​ Discovery time​

○​ Lowest discovery time reachable​

3.​ A node is an articulation point if:​

○​ It is the root with two or more children in DFS tree.​

 ○​ It has a child v such that no back-edge connects v or its
descendants to the ancestors of u.

💡 3. Introduction to NP-Completeness
⚙️ What is NP-Completeness?
●​ P = Class of problems that can be solved in polynomial time​

●​ NP = Problems whose solutions can be verified in polynomial time​

●​ NP-Complete = Problems that are:​

○​ In NP​

○​ As hard as any problem in NP​

○​ If one NP-Complete problem is solved in P-time → All NP

problems become solvable in P-time​

🧩 Examples of NP-Complete Problems:

Problem Description

Traveling Shortest route visiting all cities

Salesman
3-SAT Satisfiability of Boolean
expression

Vertex Cover Smallest set of vertices covering

all edges

Clique Problem Largest fully connected

subgraph

Hamiltonian Cycle visiting each vertex exactly

Cycle once