This page needs a recent browser (with SharedArrayBuffer support). Please update Chrome, Edge, Firefox or Safari to the latest version. · 이 페이지는 최신 브라우저(SharedArrayBuffer 지원)가 필요합니다. Chrome, Edge, Firefox 또는 Safari를 최신 버전으로 업데이트해 주세요.
English
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.
한국어
그래프
- 그래프는 노드(또는 꼭짓점라고도 함)들이 간선(연결고리)에 의해 연결된 집합입니다.
- 그래프는 네트워크를 모델링합니다: 친구 관계, 도시 간 도로, 웹 페이지 간 링크 등.
- 트리는 사실 특수한 형태의 그래프이며, 일반 그래프는 사이클을 가질 수 있고 각 노드에 여러 개의 연결고리가 있을 수 있습니다.
English
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.
한국어
그래프 표현: 인접 목록
- 일반적인 방법 중 하나는 인접 목록(adjacency list) 입니다. 이는 각 노드를 인접한 노드의 목록에 매핑하는 사전(dictionary)입니다.
graph["A"]은A과 직접 연결된 노드들의 목록입니다.- 각 노드에 연결고리가 적을 때 이 방법은 압축적입니다.
# 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']
English
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']}
English
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.
한국어
인접 노드 순회하기
- 한 노드에서 탐색하려면 해당 노드의 인접 목록을 읽고 각 노드를 방문해야 합니다.
- 그래프에 없는 노드는 인접 노드가 없습니다 — 오류 대신 빈 목록을 반환해야 합니다.
- 이러한 인접 노드 조회는 전체 그래프를 검색하는 등의 더 큰 작업의 첫 단계입니다.
English
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 무향성
- 무향 그래프에서는 간선이 양방향으로 기능합니다(우정 관계).
- 유향 그래프에서는 간선이 한方向만 향합니다(일방통행도로, "팔로우" 링크).
- 유향 간선의 경우 한 방향으로만 추가해야 합니다.
English
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.
한국어
흔한 실수
- 그래프는 간선에 의해 연결된 노드들의 집합이며, 간선은 일방통행이나 쌍방통행일 수 있습니다.
- 트리는 사이클이 없는 그래프이므로 두 개념을 혼동하지 마십시오.
English
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. - 각 과제는 작은 그래프에서 함수를 테스트합니다.
- 답안 확인을 눌러 테스트해 보십시오.
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.
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).
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.
Click Run to see the output here. · 출력을 보려면 '실행'을 클릭하세요.