典型タグ

推移閉包

各始点探索またはWarshallの段階不変条件により全頂点対の到達関係を計算する。

この典型を扱う単元: 推移閉包

検索別名: Warshall法、transitive closure、推移閉包

未知問からこの典型を見つける手掛かり

扱う対象
  • 到達関係
  • 有向graph
使う手掛かり
  • 全頂点対
  • 到達可能性
保つ不変量
  • closure
  • 中継許可集合
求めるもの
  • 到達行列
適用しない条件
個別の除外条件の記載はありません。扱う対象と使う手掛かりから適用を判断してください。
分類・前提・学習成果

分類と直接の前提

概念上の親: グラフモデルと構造

    関連する典型

      学習成果と学習単位

      • 各始点探索または中継許可集合の段階不変条件を保つWarshall更新で推移閉包を求め、必要なら初回到達段階も記録できる。

        推移閉包で学ぶ

      代表問題

      この典型の考え方を具体的な問題で確かめるための入口です。

      関連問題

      この典型が主タグまたは補助タグとして付いている問題です。