Đồ thị
Đồ 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.
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']
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']}
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ị.
Đị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.
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.
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.
Độ khó 5/5 · 400 xu + phần thưởng nhỏ khi hoàn thành lần đầu tiên hôm nay
Write add_edge(graph, a, b) for an undirected graph stored as a dict of neighbour lists. Append b đến graph[a] và a đến graph[b]. If a node is not in the graph yet, give it an empty list [] first. Change the dict in place.
Nhấn Chạy để xem kết quả ở đây.
Độ khó 5/5 · 400 xu + phần thưởng nhỏ khi hoàn thành lần đầu tiên hôm nay
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).
Nhấn Chạy để xem kết quả ở đây.
Độ khó 5/5 · 400 xu + phần thưởng nhỏ khi hoàn thành lần đầu tiên hôm nay
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.
Nhấn Chạy để xem kết quả ở đây.