Độ phức tạp thời gian sắp xếp cấu trúc liên kết trong Python là gì?

Mỗi đồ thị có nhiều hơn một trình tự sắp xếp tô pô bởi vì nó phụ thuộc vào độ của các cạnh của các nút. Nút bắt đầu đầu tiên mà chúng tôi chọn với số lượng nút theo độ là 0

Hãy hiểu thuật toán sắp xếp tô pô với một ví dụ

Bước 1. Chúng tôi chèn các nút có số cạnh đến bằng 0. Vậy các nút đó là nút 1 và nút 4

Bước 2

a. Chúng tôi bắt đầu với Nút 1. Chúng ta có thể chọn bất kỳ nút nào giữa Nút 1 và Nút 4

b. Chúng tôi giảm mỗi cạnh nút xuống 1, được kết nối với nút 1. Chúng tôi đang giảm cạnh của các nút (0, 2 và 3)

c. Chúng tôi di chuyển Nút 1 từ danh sách sang danh sách được sắp xếp theo cấu trúc liên kết, như hình dưới đây

Bước 3

a. Bây giờ chúng tôi tiếp tục từ danh sách, đó là Nút 4

b. Chúng tôi giảm tất cả các cạnh đi của các nút được kết nối với nút 4, đó là các nút (0 và 3)

c. Bây giờ, nút 3 không có cạnh đến, vì vậy chúng tôi đẩy nó vào danh sách và nút 4 chuyển sang danh sách được sắp xếp theo cấu trúc liên kết

Bước 4

a. Bây giờ chúng tôi tiếp tục từ danh sách, đó là Nút 3

b. Chúng tôi giảm tất cả các cạnh đi của các nút được kết nối với nút 3, đó là các nút (0 và 2)

c. Bây giờ, các nút 0 và Nút 2 không có cạnh đến, vì vậy chúng tôi đẩy nó vào danh sách và nút 3 chuyển sang danh sách được sắp xếp theo cấu trúc liên kết

Bước 5

a. Bây giờ chúng tôi tiến hành từ danh sách, đó là Nút 0

b. Vì không có cạnh đi ra từ Nút 0, vì vậy chúng tôi chỉ cần thêm chúng vào danh sách sắp xếp tô pô

Bước 6

a. Bây giờ chúng tôi tiếp tục từ danh sách, đó là Nút 2

b. Vì không có cạnh đi ra từ Nút 2, vì vậy chúng tôi chỉ cần thêm chúng vào danh sách sắp xếp tô pô

Bước 7

Cuối cùng, chúng tôi đã sắp xếp danh sách ở đây

Thuật toán sắp xếp tô pô

Dưới đây là các bước cho thuật toán sắp xếp tô pô mà chúng ta phải tuân theo

Bước 0. Tính độ trong của từng nút đồ thị

Bước 1. Trước tiên chúng ta phải tìm một nút có các cạnh tới bằng 0

Bước 2. Chúng tôi xóa nút đó khỏi biểu đồ và thêm nó vào danh sách các thứ tự sắp xếp tô pô

Bước 3. Loại bỏ các nút có các cạnh hướng ra ngoài

Bước 4. Giảm độ theo số cạnh liên quan đã bị xóa

Bước 5. Lặp lại các bước 1–4 cho đến khi không còn nút nào có độ bằng 0

Bước 6. Xác minh rằng tất cả các mục đều theo đúng trình tự

Bước 7. Bây giờ, chúng tôi đã sắp xếp thứ tự từ Bước 6

Bước 8. Đặt dấu chấm hết cho thuật toán

Mã Python. Dưới đây là một triển khai python của ví dụ trên

fromcollectionsimportdefaultdict

classbuildGraph

def__init__ (self, . int) .
bản thân . nút= nút

# Chúng tôi hiện đang lưu trữ biểu đồ ở định dạng danh sách liền kề
bản thân . adjListDetails= defaultdict (list)

# Nó sẽ lưu trữ thông tin về một nút cụ thể đang đến
# cạnh trong đồ thị
bản thân . count_numbers_of_incoming_edge_of_a_node= []

# Chúng tôi lưu trữ các nút được sắp xếp theo thứ tự cấu trúc liên kết
bản thân . thứ_tự_sắp_xếp= []

# Chúng tôi lưu trữ thông tin của tất cả các nút không
# có bất kỳ cạnh đến nào trong biểu đồ
bản thân . nodes_have_zero_incoming_edges= []

# Bây giờ chúng tôi đang tạo một danh sách liền kề của tất cả các biểu đồ để sắp xếp
defAddGraphEdge (bản thân, nguồn. int, đích. int) .
bản thân . adjListChi tiết[ nguồn ] . chắp thêm( đích )
bản thân . count_numbers_of_incoming_edge_of_a_node[ điểm đến ] + =1

defTopologicalSortAlgorithm (self) .

cho phạm vi nút trong phạm vi (bản thân . nút) .
chính nó. count_numbers_of_incoming_edge_of_a_node[ node ] = . 0 :
bản thân . nodes_have_zero_incoming_edges . nối( nút )

trong khi đó. nodes_have_zero_incoming_edges .
bản thân . nodes_have_zero_incoming_edges . sắp xếp()
          nguồn =chính mình . nodes_have_zero_incoming_edges . bật(0)

# lặp lại danh sách liền kề
if chính nguồn. adjListDetails .
cho chính nút đó. adjListChi tiết[ nguồn ] .
bản thân . count_numbers_of_incoming_edge_of_a_node[ nút ] - =1
chính nó. count_numbers_of_incoming_edge_of_a_node[ node ] = . 0 :
bản thân . nodes_have_zero_incoming_edges . nối( nút )

bản thân . thứ_tự_sắp_xếp . chắp thêm( nguồn )

in("Thứ tự sắp xếp tô pô. " + str(bản thân . thứ_tự_sắp_xếp))

defmain () .

number_of_nodes =7
    biểu đồ = buildGraph ( số_nút )
đồ thị. count_numbers_of_incoming_edge_of_a_node= [0] *number_of_nodes

đồ thị. AddGraphEdge(0,2)
đồ thị. AddGraphEdge(0,5)
đồ thị. AddGraphEdge(1,3)
đồ thị. AddGraphEdge(1,6)
đồ thị. AddGraphEdge(2,4)
đồ thị. AddGraphEdge(3,5)
đồ thị. AddGraphEdge(5,2)
đồ thị. AddGraphEdge(5,4)
đồ thị. AddGraphEdge(6,2)

đồ thị. Thuật toán sắp xếp cấu trúc liên kết()

if __name__ =="__main__" .
chính ()

đầu ra

Thuật toán sắp xếp tô pô Độ phức tạp thời gian

Tổng thời gian để xử lý thuật toán là O(E + N), trong đó E là số cạnh và N là số nút trong đồ thị. Sau đó, trong bước tiếp theo, chúng ta phải tính toán độ của từng nút, thường mất O(E) lần, rồi đặt tất cả các nút đó vào một danh sách đã sắp xếp trong đó độ của chúng bằng 0, mất O(N) . Vậy tổng độ phức tạp thời gian của thuật toán sắp xếp tô pô là O(E+N)

Nhưng độ phức tạp không gian của thuật toán sắp xếp tô pô là O(N), là tổng số nút trong đồ thị

Ứng dụng

1. Sắp xếp tô pô rất hữu ích để tìm chu trình của đồ thị

2. Thuật toán sắp xếp tô pô được sử dụng để xác định các điều kiện bế tắc trong hệ điều hành

3. Thuật toán sắp xếp tô pô được sử dụng để tìm đường đi ngắn nhất trong đồ thị tuần hoàn có trọng số

Phần kết luận

Bài viết này đã tìm hiểu về một thuật toán quan trọng hơn, sắp xếp topo. Chúng tôi đã thấy rằng thuật toán này chỉ hoạt động với đồ thị tuần hoàn. Thuật toán sắp xếp topo cũng giúp xác định thứ tự biên dịch tác vụ. Thuật toán sắp xếp topo có nhiều ưu điểm thời gian thực, như tìm đường đi ngắn nhất. Vì thuật toán topo cực kỳ hữu ích nên mọi lập trình viên và sinh viên đều phải tìm hiểu kỹ thuật toán này

Độ phức tạp thời gian để sắp xếp tô pô là gì?

Sắp xếp tô pô là DFS hay BFS?

Độ phức tạp thời gian của sắp xếp tô pô Kahn là gì?

NP sắp xếp tô pô có đầy đủ không?