Sắp xếp tô pô trong đồ thị là gì?
Sắp xếp tô pô trong đồ thị là gì?
Sắp xếp topo (topological sort): thứ tự tuyến tính các đỉnh của DAG sao cho mọi cạnh u → v có u đứng trước v. Chỉ tồn tại khi không có chu trình.
Kahn (BFS):
from collections import deque
def topo(n, edges):
adj = [[] for _ in range(n)]; indeg = [0] * n
for u, v in edges: adj[u].append(v); indeg[v] += 1
q = deque(i for i in range(n) if indeg[i] == 0); order = []
Đăng nhập để tham gia thảo luận cùng mọi người.
Chưa có bình luận nào
Hãy là người đầu tiên chia sẻ suy nghĩ của bạn.