Theres a good content suggestion right there, doing this for a range of different DS&A’s? A Nice clean, visual representation - just like these posts. @neetcodeIO
7 months ago (edited) | 0
Isn't time complexity of DFS and BFS both is O(V+E) cause topological sorting is based on DFS as well and it has O(V+E)
7 months ago | 0
NeetCodeIO
Graphs are common in coding interviews, but they are used in many other places too.
For example, the Six degrees of separation is the idea that all people (vertices) are six or fewer social connections (edges) away from each other.
Here's a list of 5 common graph algorithms that are common in coding interviews.
1. Depth First Search (DFS)
Prioritizes depth first. This search will go as deep as possible exploring each node before hitting the base case, after which it explores other nodes. A hash set is used to keep track of visited nodes.
2. Breadth First Search (BFS)
Prioritizes breadth first. It explores all possible neighbors of a vertex before moving on to the next level of neighbors, sometimes also called layers. This uses a queue and a hash set, and can be used to find the length of the shortest path from one vertex to the other.
3. Union-Find
Used to combine disjoint sets. It's useful for when we want to know the number of connected components in a graph. It's also used in Kruskal's algorithm for detecting cycles.
4. Topological Sort
Implemented on a directed acyclic graph, it's used to order vertices such that for every directed edge u -> v, vertex u appears before vertex v. This is useful if an interview problem talks about pre-requisites where one condition must be fulfilled before moving on to the next.
5. Dijkstra's Algorithm
A greedy algorithm that operates on weighted graphs, used to find the shortest path from one source to all other vertices in the graph. It uses a min heap to pick the shortest path at each step and a hash set to avoid cycles.
To download the full cheat sheet with code samples see: neetcode.io/courses/lessons/5-graph-algorithms
(it's free and I won't collect your email)
7 months ago | [YT] | 740