グラフアルゴリズム

グラフをレベルごとに探索し、より深く進む前に現在の深さのすべての頂点を訪問します。キューを使用し、重み付けされていないグラフでの最短経路を見つけるのに理想的です。迷路の解決、ソーシャルネットワーク分析、ノード間の接続の検索などの応用があります。

各経路に沿って可能な限り深く進んでから後戻りするグラフ探索方法です。スタックまたは再帰を使用して実装され、再帰的な問題に自然です。経路探索、サイクル検出、トポロジカルソート、迷路生成に使用されます。

重み付きグラフで単一始点から他のすべての頂点への最短経路を見つけます。GPSナビゲーションシステムやネットワークルーティングプロトコルを支えています。優先度付きキューを使用した貪欲法により、非負の辺の重みで効率的に機能します。

A best-first search algorithm that finds the shortest path using heuristics. Combines Dijkstra's algorithm and greedy best-first search using f(n) = g(n) + h(n). Widely used in games, robotics, and GPS navigation for efficient pathfinding.

Finds the Minimum Spanning Tree (MST) of a weighted undirected graph. Uses a greedy approach by sorting edges by weight and adding them if they don't create a cycle. Employs Union-Find for efficient cycle detection. Essential for network design and clustering.

Finds the Minimum Spanning Tree (MST) by growing a tree from a starting vertex. Always adds the minimum weight edge connecting a vertex in the tree to one outside. Uses a priority queue for efficient edge selection. Ideal for dense graphs.

Orders vertices of a Directed Acyclic Graph (DAG) such that for every edge u→v, u comes before v. Uses DFS-based approach. Essential for dependency resolution, build systems, and course scheduling.

Google's algorithm for ranking web pages by link structure. Computes importance scores iteratively.

Also known as the 'tortoise and hare' algorithm, this elegant technique detects cycles in linked lists or sequences using O(1) space. Uses two pointers moving at different speeds—if there's a cycle, they will eventually meet. Essential for detecting infinite loops, analyzing graph structures, and validating data integrity.

Single-source shortest path algorithm that handles negative weights and detects negative cycles. Relaxes all edges V-1 times to guarantee correct distances even with negative weights. Essential for currency arbitrage detection, network routing with varied costs, and situations where Dijkstra's algorithm fails. Trades speed for flexibility.

All-pairs shortest path algorithm that computes distances between every pair of vertices in O(V³) time. Uses dynamic programming with elegant three-line core logic. Handles negative weights and provides transitive closure. Ideal for dense graphs, network analysis, and when all pairwise distances are needed.

Greedy algorithm that builds a minimum spanning tree by adding edges in order of increasing weight, using union-find to avoid cycles. Efficient for sparse graphs with time complexity O(E log E). Applications include network design, clustering, approximation algorithms, and understanding greedy correctness proofs.

Greedy algorithm that grows a minimum spanning tree by repeatedly adding the cheapest edge connecting the tree to a new vertex. Uses a priority queue for efficiency with O(E log V) time. Preferred for dense graphs and real-time applications like network broadcasting and circuit design.