グラフ理論

スポンサーリンク
アルゴリズム

【グラフ】DFS・BFS・UnionFindで連結性判定を実装する【Python】

グラフの連結性判定を行います。汎用的なアルゴリズムである深さ優先探索・幅優先探索と、UninFindというデータ構造を使った3つの判定方法と、Pythonでの実装例を解説します。
アルゴリズム

【UnionFind】クラスの実装とAtCoder典型問題まとめ【Python】

本記事では,競技プログラミング等で汎用的に扱うことのできるUnionFindクラスの実装を紹介します.そして,AtCoderの問題の解法と共に,その使い方を解説しています.
アルゴリズム

【UnionFind】グラフの連結成分毎に頂点と辺の数を数える【Python】

無向グラフにおける,連結成分毎に頂点や辺の数を数える問題について,Pythonでの実装例を解説しています。UnionFindクラスやオブジェクト指向プログラミングの理解に有用な問題です.
アルゴリズム

【DFS・BFS】グラフ(木構造)における2頂点間の経路を求める【Python】

木構造における、2頂点間の経路を求める問題についてPythonでの実装例を解説しています。幅優先探索や深さ優先探索を理解するのにも有用な問題です。
アルゴリズム

【幅優先探索】木構造(グラフ)における頂点間距離を求める【Python】

木構造を扱う際、頂点間の距離や根からの距離を求めたり、木の直径を求めたりする場面があります。本記事では幅優先探索(BFS)の考え方を図で直感的にイメージした後、グラフ(木構造)の頂点間の距離に関する具体的な問題を解説しています。
アルゴリズム

【深さ優先探索】グラフの連結判定(AtCoderABC259 D問題解説)

Pythonでグラフの連結判定問題を詳細に解説します。グラフ理論・連結性判定に関する良問、AtCoderABCコンテスト259D問題を例に解説します。隣接行列・深さ優先探索の実装など得るものが多い問題です。
スポンサーリンク