このページには最新のブラウザ(SharedArrayBuffer対応)が必要です。Chrome、Edge、Firefox、Safariを最新バージョンに更新してください。
グラフ
- グラフとは、エッジ(接続)によって結びついたノード(頂点とも呼ばれる)の集合です。
- グラフはネットワークをモデル化します:友人関係、都市間の道路、ウェブページ間のリンクなど。
- ツリーは実際には特殊なグラフです。一般的なグラフはサイクルを持ち、ノードあたりのリンクが複数あることがあります。
グラフの表現:隣接リスト
- 一般的な方法の一つに隣接リストがあります。各ノードを隣接するノードのリストにマッピングする辞書です。
graph["A"]はAと直接接続されているノードのリストです。- 各ノードが few の接続しか持たない場合、これはコンパクトです。
English
# A graph as a dict: each node maps to its list of neighbours
graph = {
"A": ["B", "C"],
"B": ["A"],
"C": ["A"],
}
print(graph["A"]) # ['B', 'C'] -- A connects to B and C
print(graph["B"]) # ['A']
エッジの追加
- 無向グラフにおいて、エッジ
A—Bは双方向に機能します。 - したがって、追加するには、
BをAのリストに追加すると同時に、AをBのリストにも追加する必要があります。 - 新ノードがある場合は、最初に空のリストとして初期化します。
English
def add_edge(graph, a, b):
if a not in graph:
graph[a] = []
if b not in graph:
graph[b] = []
graph[a].append(b)
graph[b].append(a)
graph = {}
add_edge(graph, "A", "B")
add_edge(graph, "A", "C")
print(graph) # {'A': ['B', 'C'], 'B': ['A'], 'C': ['A']}
隣接ノードの探索
- ノードから探索するには、隣接リストを読み取って各ノードを visiting します。
- グラフに含まれないノードには隣接ノードが一切ありません。エラーではなく、空のリストを返してください。
- この隣接ノードの照会は、グラフ全体の検索などの大きなタスクの最初のステップです。
有向 vs 無向
- 無向グラフでは、エッジは両方向に機能します(友情のような関係)。
- 有向グラフでは、エッジは一方の方向のみを指します(片道、"follows" リンクなど)。
- 有向エッジの場合、追加は一方の方向のみに行います。
よくあるミス
- グラフはエッジで結ばれたノードの集合であり、エッジは片道でも両道でも構いません。
- ツリーはサイクルを持たないグラフです。これら2つを混同しないでください。
あなたも試してみよう
- 隣接リストの操作を構築します:
add_edge、neighbours、およびcount_edges。 - 各タスクは、小さなグラフ上であなたの関数をチェックします。
- Check answer を押して確認する。
難易度 5/5 · 400 コイン + 今日初回達成時の小ボーナス
隣接リスト辞書として格納された無向グラフ用のadd_edge(graph, a, b)を記述する。bをgraph[a]に、aをgraph[b]に追加する。もしノードがまだグラフにない場合、最初に空のリスト[]を与える。辞書は**原地(in place)**で変更する。
実行ボタンをクリックして出力を確認してください。
難易度 5/5 · 400 コイン + 今日初回達成時の小ボーナス
neighbours(graph, node) を書きなさい。これは node に直接接続されているノードのリストを返します。node がグラフに含まれない場合は、エラーを発生させずに空のリスト [] を返します。
実行ボタンをクリックして出力を確認してください。
難易度 5/5 · 400 コイン + 今日初回達成時の小ボーナス
無向グラフのcount_edges(graph)を記述し、辺の数を数える。すべての隣接リストの長さを足し合わせ、2で割る(各辺は両方のノードのリストに格納されているため)。例:三角形A–B–Cは3の辺を持つ。
実行ボタンをクリックして出力を確認してください。