Graphs · Đồ thị
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.
Đồ thị
- Một đồ thị là tập hợp các nút (cũng gọi là đỉnh) được nối bởi các cạnh (kết nối).
- Đồ thị mô hình hóa mạng lưới: bạn bè, đường phố giữa các thành phố, liên kết giữa các trang web.
- Cây thực chất là một đồ thị đặc biệt; đồ thị tổng quát có thể có chu trình và nhiều liên kết cho mỗi nút.
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.
Biểu diễn đồ thị: danh sách kề
- Một cách phổ biến là danh sách kề: một từ điển ánh xạ mỗi nút với danh sách các lân cận của nó.
graph["A"]là danh sách các nút được kết nối trực tiếp vớiA.- Điều này tiết kiệm bộ nhớ khi mỗi nút chỉ có vài kết nối.
# 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.
Thêm một cạnh
- Trong đồ thị không định hướng, cạnh
A—Bđi theo cả hai chiều. - Vì vậy, thêm nó có nghĩa là appended
Bvào danh sáchAvàAvào danh sáchB. - Nếu một nút mới, hãy bắt đầu nó bằng một danh sách rỗng trước tiên.
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.
Duyệt qua các lân cận
- Để khám phá từ một nút, bạn đọc danh sách lân cận của nó và truy cập từng cái.
- Một nút không nằm trong đồ thị có không có lân cận — trả về danh sách rỗng, không phải lỗi.
- Tra cứu lân cận này là bước đầu tiên của những công việc lớn hơn như tìm kiếm toàn bộ đồ thị.
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.
Định hướng so với không định hướng
- Trong đồ thị không định hướng, một cạnh hoạt động hai chiều (một mối quan hệ bạn bè).
- Trong đồ thị định hướng, một cạnh chỉ trỏ theo một chiều (một con đường một chiều, một liên kết "theo dõi").
- Đối với các cạnh định hướng, bạn sẽ appended theo một chiều duy nhất.
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.
Lỗi thường gặp
- Một đồ thị là các nút được nối bởi các cạnh; một cạnh có thể một chiều hoặc hai chiều.
- Cây là một đồ thị không có chu trình — đừng nhầm lẫn hai thứ này.
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.
Bây giờ bạn thử
- Xây dựng các thao tác danh sách kề:
add_edge,neighbours, vàcount_edges. - Mỗi nhiệm vụ kiểm tra hàm của bạn trên một đồ thị nhỏ.
- Nhấn Kiểm tra đáp án để thử nghiệm.
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. · Viết ⟨add_edge(graph, a, b)⟩ cho đồ thị không định hướng được lưu dưới dạng dict chứa các danh sách lân cận. Thêm ⟨b⟩ vào ⟨graph[a]⟩ và ⟨a⟩ vào ⟨graph[b]⟩. Nếu một node chưa có trong đồ thị, hãy gán cho nó một danh sách rỗng ⟨[]⟩ trước. Thay đổi dict ngay tại chỗ.
Click Run to see the output here. · Nhấn Chạy để xem kết quả ở đây.
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). · Viết ⟨neighbours(graph, node)⟩ trả về danh sách các node được nối trực tiếp với ⟨node⟩. Nếu ⟨node⟩ không có trong đồ thị, trả về danh sách rỗng ⟨[]⟩ (không gây lỗi).
Click Run to see the output here. · Nhấn Chạy để xem kết quả ở đây.
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. · Viết ⟨count_edges(graph)⟩ cho đồ thị không định hướng: đếm số cạnh của nó. Cộng độ dài của mọi danh sách lân cận, sau đó chia cho 2 (mỗi cạnh được lưu trong danh sách của cả hai node). Ví dụ: tam giác A–B–C có ⟨3⟩ cạnh.
Click Run to see the output here. · Nhấn Chạy để xem kết quả ở đây.