Graphs
Graph Traversals
Graph traversal, also called graph search, refers to the process of visiting each vertex in a graph.
There are two main algorithms for graph traversal where each vertex of the graph is visited: Depth First Search (DFS) and Breadth First Search (BFS).
DFS is typically implemented using a stack or recursion, and it is highly efficient when combined with backtracking.
BFS is primarily implemented using a queue and is used for problems like finding the shortest path in a graph. Note that BFS does not work recursively and can only be implemented iteratively using a queue.
There are two main ways to represent a graph: adjacency matrix and adjacency list. In the case of an adjacency list, this can be represented using Python's dictionary data type. The starting node can be represented as the key, and the destination nodes as the values. Since there can be multiple destination nodes, they are represented in a list format.
Backtracking
Backtracking is a general algorithm for finding solutions by exploring candidates progressively and abandoning a candidate ("backtracking") as soon as it is determined that the candidate cannot possibly be extended to a valid solution. It is particularly useful for constraint satisfaction problems.
Backtracking involves searching until a dead-end is reached, then retracting steps and searching in a different direction. Therefore, backtracking is primarily implemented using recursion and fundamentally falls under the DFS category.
In the context of trees, backtracking relates to tree pruning and is associated with tree search optimization problems.
Constraint Satisfaction Problems
Backtracking is also an essential algorithm for solving constraint satisfaction problems, which refer to mathematical problems that seek states satisfying numerous constraints. Therefore, to solve problems within a reasonable timeframe, concepts like heuristics and combinatorial search are combined with backtracking.
Last updated