グラフ2 件の記事

グラフ の記事

Union-Find（素集合データ構造）入門 - 経路圧縮とunion by sizeで連結性を高速に管理する

Union-Find（素集合データ構造）入門 - 経路圧縮とunion by sizeで連結性を高速に管理する

約32分

要素のグループ分けを管理するUnion-Find（素集合データ構造 / DSU）を解説します。find・union・sameという3つの基本操作、森による表現、素朴な実装がO(n)に劣化する理由、経路圧縮とunion by sizeという2つの最適化、Tarjanが示したならしO(α(n))という計算量、クラスカル法・連結成分の数え上げ・グリッドの島の数・サイクル検出・重み付きUnion-Findといった応用、各言語の標準ライブラリ事情まで、実際に動くPythonコードで整理します。

アルゴリズムデータ構造Union-Findグラフ計算量
グラフ探索アルゴリズム入門 - BFS・DFS・ダイクストラと最短経路

グラフ探索アルゴリズム入門 - BFS・DFS・ダイクストラと最短経路

約19分

グラフの基礎用語と表現（隣接リスト/隣接行列）から、幅優先探索(BFS)・深さ優先探索(DFS)、トポロジカルソート、重み付き最短経路（ダイクストラ・ベルマン–フォード・A*）までを、それぞれの計算量と実務での使い所を添えてPythonコード例で丁寧に解説します。

アルゴリズムグラフデータ構造最短経路ダイクストラ