The most common topics in graphs are Breadth First Traversal, and Depth First Traversal.
Think of graphs as trees with cycles. Thus, unlike a tree traversal, you need to make sure you are not moving around in cycles. Other differences are that most graph based questions often involve structures with more than two child nodes per node, and disconnected structures.
- Usually implemented using a queue
- In practice, may take more memory than DFS.
- The go-to algorithm for questions involving shortest distances (or nodes less than 2 hops away etc).
- Usually implemented using recursion
- In practice, takes less memory than BFS
- The go-to algorithm for questions involving paths
Find if there is a path between two given nodes in a graph.
A Knight is at location (0,0) on a 8 X8 chessboard. Find the minimum number of steps needed to reach square (0,3).
A Knight is at location (0,0) on a chessboard. Enumerate its path (points in needs to visit in order) to (3, 3), if such a path exists.
Example: The path to (4,2) is (0,0), (2,1), (4,2).
Your are given a set of processes and a dependency graph. (Each process has a depends on node which points to another process in the set, if the former depends on the latter).
Motivation To approximate the shortest path in real-life situations, like- in maps, games where there can be many…www.geeksforgeeks.org