Concepts106
MST Properties and Applications
An MST minimizes total edge weight over all spanning trees and has powerful properties such as the cut and cycle properties that guide correct, greedy construction.
Minimum Spanning Tree - Prim
Prim's algorithm builds a Minimum Spanning Tree (MST) by growing a tree from an arbitrary start vertex, always adding the lightest edge that connects the tree to a new vertex.
Bellman-Ford Algorithm
Bellman–Ford finds single-source shortest paths even when some edge weights are negative.
Dijkstra - Variations and Applications
Dijkstra’s algorithm can be adapted to track the second shortest path by keeping the best and second-best distances per vertex.
Topological Sort - DP on DAG
Topological sort orders vertices of a directed acyclic graph (DAG) so every edge goes from earlier to later, which is perfect for dynamic programming (DP).
Breadth-First Search (BFS)
Breadth-First Search (BFS) explores a graph level by level, visiting all vertices at distance d from the source before any at distance d+1.
Multi-Source BFS
Multi-source BFS explores an unweighted graph starting from several sources at once to compute the minimum distance to any source for every vertex.
0-1 BFS
0-1 BFS is a shortest path algorithm specialized for graphs whose edge weights are only 0 or 1.
Depth-First Search (DFS)
Depth-First Search (DFS) explores a graph by going as deep as possible along each path before backtracking.
2D Prefix Sum
A 2D prefix sum (also called an integral image) lets you compute the sum of any axis-aligned sub-rectangle in constant time after O(nm) preprocessing.
Prefix Sum and Difference Array
Prefix sums precompute running totals so any range sum [l, r] can be answered in O(1) time as prefix[r] - prefix[l-1].
Sorting Algorithms
Sorting arranges items into a chosen order so that searching, grouping, and further algorithms become faster and simpler.