Topological Sort | Kahn vs DFS | Graphs | Data Structure
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.
In this video, I have discussed following two algorithms for Topological sort:
1. Kahn's algorithm
2. Modified DFS algorithm
I have explained both the algorithms using an example and have implemented in C++ as well.
Source Code: https://github.com/fit-coder/fitcoder...
00:00 Introduction
00:25 Topological sort
02:44 Kahn's algorithm
08:21 Modified DFS algorithm
13:12 Applications
15:30 C++ Implementation
-------------------------------------------------------------
I live in New Delhi and love explaining programming concepts. I have done M.Tech(BITS Pilani) + B.Tech(PEC, Chandigarh) in Computer Science and am currently working as a software engineer in a MNC.
If you like my content, please like, share my videos and subscribe to the channel.
-------------------------------------------------------------
For in-depth Graph theory and implementation details, please refer to the below videos:
Graphs Introduction: • Introduction to Graphs Data Structure
Graph representation:
Adjacency Matrix: • Graph representation I - Adjacency Matrix ...
Adjacency List: • Graph representation II - Adjacency List E...
Incidence Matrix: • Graph representation III - Incidence Matri...
Traversal techniques:
BFS, Breadth First Search: • BFS Breadth First Search | Graph Traversal...
DFS, Depth First Search: • DFS Depth First Search | Graph Traversal |...
Shortest Path algorithms:
Dijkstra algorithm: • Dijkstra Algorithm | Single Source Shortes...
Bellman Ford algorithm: • Bellman Ford Algorithm | Single Source Sho...
Floyd Warshall algorithm: • Floyd Warshall Algorithm | All Pairs Short...
Minimum Spanning Tree:
Kruskal algorithm: • Kruskal Algorithm | Minimum Spanning Tree ...
Prim algorithm: • Prim Algorithm | Minimum Spanning Tree | G...
Topological sort (Kahn algorithm): • Topological Sort | Kahn vs DFS | Graphs | ...
Articulation points / Cut vertices:
Tarjan algorithm: • Articulation Points | Cut Vertices | Tarja...
Disjoint Set / Union Find: • Disjoint Set | Union Find | Cycle Detectio...
Maximum Flow Problem:
Ford Fulkerson algorithm: • Ford Fulkerson Algorithm | Maximum Flow Pr...
Graph coloring / Chromatic number: • Graph Coloring | Chromatic Number | BackTr...
Hamiltonian cycle: • Hamiltonian Cycle (Circuit) | Hamiltonian ...
Euler cycle (Fleury algorithm): • Euler Cycle (Circuit) | Euler Path | Circu...
#DataStructure,#Graphs,#FitCoder,#Algorithm,#competitiveprogramming