Breadth First Search and Depth First Search - Graph Algorithms - Algorithms Part 9
In this lecture, we we continue our discussion on graph algorithms by discussing the two most important algorithms for graph traversal: breadth first search (BFS) and depth first search (DFS). We then discuss the applications of these algorithms, including how BFS can be used to solve the single-source shortest paths problem for unweighted graphs, as well as how DFS can be used to perform undirected connected component (UCC) decomposition and strongly connected component (SCC) decomposition, where we finish by discussing Kosaraju's Algorithm.
Timestamps:
00:00 Introduction
00:32 Graph Representations
01:56 Breadth First Search (BFS)
05:05 Depth First Search (DFS)
07:01 Undirected Connected Components (UCC) Decomposition with DFS
07:57 DFS with Visit Times
10:55 Strongly Connected Component (SCC) Decomposition with DFS
13:06 Kosaraju's Algorithm
14:20 Conclusion
#bfs #dfs #graphtheory #breadthfirstsearch #depthfirstsearch #kosaraju #spanningtree #algorithms #timecomplexity #computerscience