0Pricing
Coding Interview Prep · レッスン

橋と関節点

グラフを分断する辺とノードを見つけます

「橋と関節点」はCoddyKit上の無料Coding Interview Prepレッスンです。 これはレッスン4/4です。 下記で完全なレッスンを無料で読むことができます。その後、ブラウザ内の組み込みコードエディタと24時間対応のAIチューターでハンズオン演習できます。 これはCoding Interview Prep学習パスの一部であり、ウェブとCoddyKitアプリ全体で進捗が同期されます。 Coding Interview Prepコースには全4レッスンが含まれています。

グラフの脆い箇所

無向グラフには重要な部分があります。それらを取り除くとグラフが分断されます。そこを見つけることで、弱い接続部分が明らかになります。

橋とは

橋とは、取り除くと連結成分の数が増える辺です。2つの領域を結ぶ唯一の経路になっています。

関節点とは

関節点とは、取り除くとグラフが非連結になるノードです。ネットワークにとって、単一障害点にあたります。

DFS木をもう一度見る

どちらも1回のDFSで動作し、発見時刻と low 値を管理します。Tarjanのアルゴリズムとよく似ていますが、無向グラフを対象にします。

disc = [-1] * n
low = [-1] * n

lowは最も早く到達できる発見番号

ノードのlowは、そのDFS部分木から到達できる最小の発見番号です。場合によっては、1本の後退辺を上へたどって到達します。

入った時点で初期化する

DFSでノードに入ったら、現在のタイマーの値をdisc と lowに記録し、隣接ノードへ進みます。

disc[u] = low[u] = timer
timer += 1

橋の条件

子 v へ再帰した後、low[v] > disc[u] なら、u より先へ抜ける後退辺はありません。したがって辺 u-v は橋です。

if low[v] > disc[u]:
    bridges.append((u, v))

関節点の条件

根でない u は、子 v が low[v] >= disc[u] を満たすとき関節点です。v の部分木は u を迂回できません。

if parent[u] != -1 and low[v] >= disc[u]:
    art.add(u)

根の場合の特別扱い

DFSの根が関節点になるのは、DFS木で2つ以上の子を持つ場合だけです。そのため、子の数を数えます。

if parent[u] == -1 and children > 1:
    art.add(u)

親への辺をスキップする

後退辺から low を更新するときは、親へ向かう辺を逆にたどらないでください。そうしないと橋を誤判定します。

if v != parent[u]:
    low[u] = min(low[u], disc[v])

1回の探索で両方を求める

1回のDFSで、すべての橋と関節点を同時にO(V + E)で見つけられます。追加の探索は必要ありません。

理解度チェック

u から子 v へ再帰した後、low[v] > disc[u] でした。何を見つけましたか？

まとめ: 重要な辺とノード

disc と low を使った1回のDFSですべてを見つけられます。low[v] > disc[u] は橋を、low[v] >= disc[u] は関節点を示します。🌉

よくある質問

「橋と関節点」レッスンは無料ですか？

はい。「橋と関節点」の完全なテキストはこのウェブで無料で読めます。インタラクティブに演習し（組み込みコードエディタと24時間対応のAIチューター）、Coding Interview Prepコースの残りをアンロックするには、CoddyKit PROにアップグレードしてください。 Coding Interview Prepコースには全4レッスンが含まれています。

「橋と関節点」で何を学びますか？

グラフを分断する辺とノードを見つけます ブラウザで直接実行するハンズオンコードでCoding Interview Prepを演習し、24時間対応のAIチューターがレッスンを進める中での質問に答えます。

Coding Interview Prepを始めるのに経験は必要ですか？

事前経験は必要ありません。CoddyKitのCoding Interview Prepは初級者から上級者向けに構成されているため、ここから始めるか最初から始めて、自分のペースで進むことができます。 これはレッスン4/4です。

「橋と関節点」レッスンにはどのくらい時間がかかりますか？

ほとんどのCoddyKitレッスンは約5～10分かかります。各レッスンはコンパクトでインタラクティブなので、着実に進歩し、ウェブとアプリ全体で正確に前回の場所から再開できます。

このCoding Interview Prepレッスンでコードを書いて実行できますか？

はい。すべてのCoding Interview Prepレッスンに組み込みコードエディタが含まれているため、ブラウザでリアルコードを書いて実行し、即座のAIフィードバックを取得できます。ローカル設定は不要です。

このコースのすべてのレッスン

  1. Kahn のアルゴリズムによるトポロジカルソート
  2. 有向グラフのサイクル検出
  3. 強連結成分
  4. 橋と関節点
← Coding Interview Prepに戻る