Câu hỏi:
13/07/2024 612Kiểm tra tính liên thông của đơn đồ thị có hướng
Trong đơn đồ thị có hướng, người ta thường quan tâm đến tính liên thông mạnh của đồ thị. Một đồ thị có hướng được gọi là liên thông mạnh nếu từ một đỉnh bất kì của đồ thị có thể đến được tất cả các đỉnh còn lại.
Các bài toán liên quan đến tính liên thông của đơn đồ thị có hướng cũng có nhiều ứng dụng như tính liên thông của đơn đồ thị vô hướng.
Sách mới 2k7: Tổng ôn Toán, Lí, Hóa, Văn, Sử, Địa…. kỳ thi tốt nghiệp THPT Quốc gia 2025, đánh giá năng lực (chỉ từ 110k).
Quảng cáo
Trả lời:
Trong đơn đồ thị có hướng, người ta thường quan tâm đến tính liên thông mạnh của đồ thị. Một đồ thị có hướng được gọi là liên thông mạnh nếu từ một đỉnh bất kì của đồ thị có thể đến được tất cả các đỉnh còn lại.
Các bài toán liên quan đến tính liên thông của đơn đồ thị có hướng cũng có nhiều ứng dụng như tính liên thông của đơn đồ thị vô hướng.
Muốn kiểm tra tính liên thông mạnh của một đồ thị có hướng, chúng ta cần đảm bảo rằng từ bất kỳ đỉnh nào cũng có thể đi đến tất cả các đỉnh khác. Điều này yêu cầu mỗi đỉnh có thể đạt tới tất cả các đỉnh khác thông qua các cung của đồ thị có một thuật toán hiệu quả để kiểm tra tính liên thông mạnh của đồ thị có hướng, đó là thuật toán Kosaraju. Các bước của thuật toán như sau:
* Thuật toán Kosaraju
- Chạy DFS từ tất cả các đỉnh và lưu thứ tự hoàn thành của các đỉnh: Duyệt đồ thị và sử dụng DFS để lưu trữ thứ tự hoàn thành của các đỉnh trong một stack.
- Đảo ngược đồ thị: Tạo một đồ thị mới với tất cả các cạnh đảo ngược so với đồ thị gốc.
- Chạy DFS trên đồ thị đảo ngược theo thứ tự hoàn thành: Sử dụng stack từ bước 1 để chạy DFS trên đồ thị đảo ngược, bắt đầu từ đỉnh cuối cùng trong stack. Mỗi lần chạy DFS, các đỉnh được duyệt sẽ tạo thành một thành phần liên thông mạnh. Nếu sau bước 3, chỉ có một thành phần liên thông mạnh duy nhất chứa tất cả các đỉnh, thì đồ thị gốc là liên thông mạnh.
* Chương trình Python:
def kosaraju(n, edges):
# Bước 1: Xây dựng đồ thị và chạy DFS để có thứ tự hoàn thành
def dfs(v, graph, visited, stack):
visited[v] = True
for neighbor in graph[v]:
if not visited[neighbor]:
dfs(neighbor, graph, visited, stack)
stack.append(v)
# Bước 2: Đảo ngược đồ thị
def reverse_graph(n, edges):
reversed_graph = [[] for _ in range(n)]
for u, v in edges:
reversed_graph[v].append(u)
return reversed_graph
# Bước 3: Chạy DFS trên đồ thị đảo ngược theo thứ tự hoàn thành
def fill_order(n, graph):
visited = [False] * n
stack = []
for i in range(n):
if not visited[i]:
dfs(i, graph, visited, stack)
return stack
def get_sccs(n, reversed_graph, stack):
visited = [False] * n
sccs = []
while stack:
v = stack.pop()
if not visited[v]:
scc_stack = []
dfs(v, reversed_graph, visited, scc_stack)
sccs.append(scc_stack)
return sccs
# Xây dựng đồ thị
graph = [[] for _ in range(n)]
for u, v in edges:
graph[u].append(v)
# Bước 1: Chạy DFS và lấy thứ tự hoàn thành
stack = fill_order(n, graph)
# Bước 2: Đảo ngược đồ thị
reversed_graph = reverse_graph(n, edges)
# Bước 3: Chạy DFS trên đồ thị đảo ngược theo thứ tự hoàn thành
sccs = get_sccs(n, reversed_graph, stack)
# Kiểm tra số lượng thành phần liên thông mạnh
return len(sccs) == 1
# Ví dụ sử dụng
n = 5
edges = [(0, 1), (1, 2), (2, 0), (1, 3), (3, 4), (4, 1)]
print(kosaraju(n, edges)) # Kết quả: True, đồ thị liên thông mạnh
CÂU HỎI HOT CÙNG CHỦ ĐỀ
Câu 1:
Kiểm tra tính liên thông của đơn đồ thị vô hướng
Một đơn đồ thị vô hướng được gọi là liên thông nếu hai đinh bất kì của đồ thị đều có đường đi tới nhau.
Bài toán kiểm tra tính liên thông của đơn đồ thị vô hướng xuất hiện nhiều trong nghiên cứu lí thuyết cũng như ứng dụng trong cuộc sống, sau đây là một ví dụ cụ thể:
Có địa điểm được đánh số từ 0 đến n - 1, có m tuyến xe buýt hai chiều giữa các địa điểm, tuyển thứ k sẽ di chuyển giữa hai địa điểm ik, và jk, Em hãy kiểm tra xem từ một địa điểm bất kì có thể tới được các địa điểm còn lại bằng cách chỉ sử dụng m tuyển xe buýt hay không.
Câu 2:
Tìm đường đi ngắn nhất trên đơn đồ thị có hướng
Một dãy đỉnh a = i0, i1,..., is = b (a ≠ b) được gọi là đường đi từ đinh a tới đỉnh b nếu hai đỉnh liên tiếp trên đường đi có cạnh nối.
Trong cuộc sống chúng ta gặp rất nhiều bài toán liên quan đến tìm đường đi, dưới đây là một ví dụ cụ thể.
Có n sân bay được đánh số từ 0 đến n - 1, có m tuyến bay giữa các sân bay, tuyến thứ k sẽ bay từ sân bay i, sang sân bay j .Em hãy tìm cách di chuyển từ sân bay a tới sân bay b với số tuyến bay là ít nhất.
263 câu Trắc nghiệm tổng hợp ôn thi tốt nghiệp THPT môn Tin học Chủ đề F. Giải quyết vấn đề với sự trợ giúp của máy tính có đáp án
15 câu Trắc nghiệm Tin học 12 KNTT Bài 7: HTML và cấu trúc trang web
15 câu Trắc nghiệm Tin học 12 KNTT Bài 10: Tạo liên kết
15 câu Trắc nghiệm Tin học 12 KNTT Bài 8: Định dạng văn bản
15 câu Trắc nghiệm Tin học 12 KNTT Bài 11: Chèn tệp tin đa phương tiện và khung nội tuyến vào trang web
15 câu Trắc nghiệm Tin học 12 KNTT Bài 9: Tạo danh sách, bảng
15 câu Trắc nghiệm Tin học 12 Cánh diều Bài 1: Làm quen với ngôn ngữ đánh dấu siêu văn bản
Đề thi Học kì 1 Tin học 12 có đáp án (Đề 1)
về câu hỏi!