Graphs · グラフ
Graphs
- A graph is a set of nodes (also called vertices) joined by edges (connections).
- Graphs model networks: friends, roads between cities, links between web pages.
- A tree is really a special graph; a general graph can have cycles and many links per node.
グラフ
- グラフとは、エッジ（接続）によって結びついたノード（頂点とも呼ばれる）の集合です。
- グラフはネットワークをモデル化します：友人関係、都市間の道路、ウェブページ間のリンクなど。
- ツリーは実際には特殊なグラフです。一般的なグラフはサイクルを持ち、ノードあたりのリンクが複数あることがあります。
Representing a graph: adjacency list
- One common way is an adjacency list: a dictionary mapping each node to its list of neighbours.
graph["A"]is the list of nodes directly connected toA.- This is compact when each node has only a few connections.
グラフの表現：隣接リスト
- 一般的な方法の一つに隣接リストがあります。各ノードを隣接するノードのリストにマッピングする辞書です。
graph["A"]はAと直接接続されているノードのリストです。- 各ノードが few の接続しか持たない場合、これはコンパクトです。
# 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']
Adding an edge
- In an undirected graph, an edge
A—Bgoes both ways. - So adding it means appending
BtoA's list andAtoB's list. - If a node is new, start it with an empty list first.
エッジの追加
- 無向グラフにおいて、エッジ
A—Bは双方向に機能します。 - したがって、追加するには、
BをAのリストに追加すると同時に、AをBのリストにも追加する必要があります。 - 新ノードがある場合は、最初に空のリストとして初期化します。
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']}
Walking the neighbours
- To explore from a node, you read its neighbour list and visit each one.
- A node that is not in the graph has no neighbours — return an empty list, not an error.
- This neighbour lookup is the first step of bigger jobs like searching the whole graph.
隣接ノードの探索
- ノードから探索するには、隣接リストを読み取って各ノードを visiting します。
- グラフに含まれないノードには隣接ノードが一切ありません。エラーではなく、空のリストを返してください。
- この隣接ノードの照会は、グラフ全体の検索などの大きなタスクの最初のステップです。
Directed vs undirected
- In an undirected graph an edge works both ways (a friendship).
- In a directed graph an edge points one way only (a one-way street, a "follows" link).
- For directed edges you would append in one direction only.
有向 vs 無向
- 無向グラフでは、エッジは両方向に機能します（友情のような関係）。
- 有向グラフでは、エッジは一方の方向のみを指します（片道、"follows" リンクなど）。
- 有向エッジの場合、追加は一方の方向のみに行います。
Common mistakes
- A graph is nodes joined by edges; an edge can be one-way or two-way.
- A tree is a graph with no cycles — do not confuse the two.
よくあるミス
- グラフはエッジで結ばれたノードの集合であり、エッジは片道でも両道でも構いません。
- ツリーはサイクルを持たないグラフです。これら2つを混同しないでください。
Now you try
- Build the adjacency-list operations:
add_edge,neighbours, andcount_edges. - Each task checks your function on a small graph.
- Press Check answer to test it.
あなたも試してみよう
- 隣接リストの操作を構築します：
add_edge、neighbours、およびcount_edges。 - 各タスクは、小さなグラフ上であなたの関数をチェックします。
- Check answer を押して確認する。
Write add_edge(graph, a, b) for an undirected graph stored as a dict of neighbour lists. Append b to graph[a] and a to graph[b]. If a node is not in the graph yet, give it an empty list [] first. Change the dict in place. · 隣接リスト辞書として格納された無向グラフ用のadd_edge(graph, a, b)を記述する。bをgraph[a]に、aをgraph[b]に追加する。もしノードがまだグラフにない場合、最初に空のリスト[]を与える。辞書は**原地（in place）**で変更する。
Click Run to see the output here. · 実行ボタンをクリックして出力を確認してください。
Write neighbours(graph, node) that returns the list of nodes directly connected to node. If node is not in the graph, return an empty list [] (do not raise an error). · neighbours(graph, node) を書きなさい。これは node に直接接続されているノードのリストを返します。node がグラフに含まれない場合は、エラーを発生させずに空のリスト [] を返します。
Click Run to see the output here. · 実行ボタンをクリックして出力を確認してください。
Write count_edges(graph) for an undirected graph: count how many edges it has. Add up the lengths of every neighbour list, then divide by 2 (each edge is stored in both nodes' lists). Example: a triangle A–B–C has 3 edges. · 無向グラフのcount_edges(graph)を記述し、辺の数を数える。すべての隣接リストの長さを足し合わせ、2で割る（各辺は両方のノードのリストに格納されているため）。例：三角形A–B–Cは3の辺を持つ。
Click Run to see the output here. · 実行ボタンをクリックして出力を確認してください。