Estimating Percolation in a Matrix Network
Dynamic connectivity algorithms provide an efficient way to model and analyze percolation in a grid of sites.
Tag: Graph
Travelling Salesman Problem using Held-Karp Algorithm | Dynamic Programming
The Held-Karp algorithm is an efficient dynamic programming approach for solving the Travelling Salesman Problem (TSP). The algorithm builds up a table to store the optimal cost of visiting subsets of cities.
Travelling Salesman Problem using Nearest Neighbour Algorithm
Given a list of cities and the distances between each pair of cities, find the shortest possible route that visits each city exactly once and returns to the origin city.
BFS (Breadth-First Search) in Binary Trees and Graphs
BFS (Breadth-First Search) is one of the simplest algorithms for traversing a graph. Prim’s min-spanning-tree and Djikstra’s algorithm use similar ideas as BFS. BFS is also known as Level-order traversal because the algorithm discover all nodes at distance k from root before discovering any nodes at distance k+1.