Sắp xếp tô pô Python lặp đi lặp lại

DFS đã được sửa đổi để tạo ra một sắp xếp topo. Trong hướng dẫn này, chúng tôi sẽ thực hiện sắp xếp tô pô trên biểu đồ bằng ngôn ngữ python

Sắp xếp tô pô - Giới thiệu cơ bản

Sắp xếp tô pô là thứ tự của các đỉnh theo cách mà nút hoặc đỉnh a phải truy cập trước nút hoặc đỉnh b cho mọi cạnh có hướng ab. Thực hiện truyền tải DFS bắt đầu tại một số nút trong biểu đồ và kết thúc với DFS trên một trong các nút chưa được truy cập nếu còn bất kỳ nút nào. Thao tác này được lặp lại cho đến khi không còn nút nào chưa được truy cập. Thứ tự cấu trúc liên kết của DAG sau đó được xác định bằng cách sắp xếp thời gian hoàn thành tương ứng với từng nút theo thứ tự giảm dần

Chúng ta hãy nhìn vào sơ đồ dưới đây

Thứ tự topo hoặc sắp xếp của đồ thị là A, B, C, D, E, F. Nghĩa là muốn thăm đỉnh B thì phải thăm đỉnh A trước. Để thăm đỉnh C, đỉnh A, B phải được thăm, v.v.

Hai điều kiện sau sẽ được sử dụng để sắp xếp một mảng bằng phương pháp tô pô

• Đồ thị phải tuần hoàn và có hướng
• Trong đồ thị tô pô, đỉnh phải là đỉnh không có cạnh tới

thuật toán

Đến bây giờ, chúng ta đã hiểu sơ bộ về cách sắp xếp tô pô được thực hiện. Để hiểu rõ hơn, hãy đi sâu vào thuật toán, sau đó là mã

1. Nhập defaultdict
2. Tạo biểu đồ lớp
3. Tạo một hàm edge()
4. Tạo một hàm visit()
5. tạo một hàm topological_sort()
6. Xác định các đỉnh không có cạnh tới
7. Chọn đỉnh đó làm đỉnh xuất phát của đồ thị
8. Xóa đỉnh xuất phát hoặc đỉnh không có cạnh tới và xóa tất cả các cạnh đi của nó khỏi đồ thị
9. Đặt đỉnh đã xóa vào danh sách đầu ra
10. Lặp lại cho đến khi biểu đồ trống
11. Biểu đồ hiện đã được sắp xếp
12. In kết quả

Chương trình sắp xếp vỏ

Như đã thảo luận ở trên về thuật toán, bây giờ chúng ta hãy đi sâu vào phần lập trình của thao tác sắp xếp tô pô chịu ảnh hưởng của thuật toán

from collections import defaultdict
class Graph:
    def __init__(self, directed=False):
        self.graph = defaultdict(list)
        self.directed = directed

    def Edge(self, frm, to):
        self.graph[frm].append(to)

        if self.directed is False:
            self.graph[to].append(frm)
        else:
            self.graph[to] = self.graph[to]

    def visit(self, s, visited, sortlist):
        visited[s] = True

        for i in self.graph[s]:
            if not visited[i]:
                self.visit(i, visited, sortlist)

        sortlist.insert(0, s)

    def topological_Sort(self):
        visited = {i: False for i in self.graph}

        sortlist = []
       
        for v in self.graph:
            if not visited[v]:
                self.visit(v, visited, sortlist)

        print(sortlist)

#driver code
if __name__ == '__main__':
 
    g = Graph(directed=True)

    g.Edge(1, 2)
    g.Edge(2, 3)
    g.Edge(3, 4)
    g.Edge(4, 5)
    g.Edge(5, 6)
    g.Edge(6, 7)
    g.Edge(7, 8)
    
    print("The Result after Topological Sort:")
    g.topological_Sort()

Kết quả sau khi sắp xếp tô pô
[1, 2, 3, 4, 5, 6, 7, 8]

Phần kết luận

Trong hướng dẫn này, chúng tôi đã thực hiện thao tác sắp xếp tô pô trong python để sắp xếp biểu đồ. Thuật toán sắp xếp tô pô không ổn định. Độ phức tạp thời gian của thuật toán sắp xếp tô pô là O(n+k) và độ phức tạp không gian là O(max). Chúng ta có thể sử dụng radic

Sắp xếp tô pô của DAG là thứ tự tuyến tính từng phần của các nút của nó sao cho nếu đồ thị đó có cạnh hướng từ u đến v, thì u phải được đặt theo thứ tự trước v. Đặt hàng một phần rất hữu ích trong nhiều tình huống. Vấn đề lập lịch trình, giải pháp phụ thuộc

Một số thuật ngữ hữu ích cho đồ thị

• Độ không - Số cạnh hướng về phía nó
• Outgrade —Số cạnh đi ra ngoài từ đỉnh
• Đỉnh nguồn — Một đỉnh không có cạnh nào hướng về phía nó. Nó có các cạnh chỉ hướng ra ngoài
• Sink Vertex — Một đỉnh không có cạnh hướng ra ngoài. Nó có các cạnh chỉ hướng về phía nó

bước

1. Lưu trữ độ của tất cả các nút trong biểu đồ
2. Xác định các nút có độ bằng 0. Thêm từng nút vào một hàng đợi sẽ được lặp lại
3. Trong khi tập chứa các nút có bậc bằng 0 không trống, hãy loại bỏ một nút. Lưu trữ nút trong danh sách kết quả. Đối với mỗi nút bị xóa, hãy lặp lại các cạnh của nó, giảm dần độ của từng nút đích trên cạnh. Nếu một nút hiện có bậc bằng 0, hãy thêm nút đó vào hàng đợi và liệt kê theo bước 2
4. Cuối cùng, trả về danh sách mỗi nút được thêm vào. Điều này sẽ chứa một thứ tự cấu trúc liên kết của các nút

Triển khai mã

from collections import defaultdict
 
class Graph:
    def __init__(self, vertices):
        self.graph = defaultdict(list)
        self.V = vertices    def add_edge(self, u, v):
        self.graph[u-1].append(v-1)    def topological_sort(self):
        in_degree = [0]*(self.V)
        visited = [0]*(self.V)
        for i in self.graph:
            for j in self.graph[i]:
                in_degree[j] += 1
        top_order = []
        queue = []
        from heapq import heappush, heappop
        for i in range(self.V):
            if in_degree[i] == 0:
                heappush(queue, i)        while queue:
            u = heappop(queue)
            if not visited[u]:
                top_order.append(u+1)
                for i in self.graph[u]:
                    in_degree[i] -= 1
                    if in_degree[i] == 0:
                        heappush(queue, i)
                visited[u] = 1
        
        return top_order## Driver code  
A = 6
B = [[6, 3], [6, 1], [5, 1], [5, 2], [3, 4], [4, 2]]graph = Graph(A)
for u, v in B:
    graph.add_edge(u, v)
        
res = graph.topological_sort()
print(res) # [5, 6, 1, 3, 4, 2]

Trong cách triển khai ở trên, tôi đã sử dụng heapq vì tôi muốn đảm bảo kết quả là nhỏ nhất về mặt từ điển trong trường hợp chúng tôi có nhiều đơn đặt hàng. Ngoài ra, tôi đã sử dụng (u-1 và v-1) vì tôi đang sử dụng lập chỉ mục dựa trên 1 cho các nút

bước

1. Bắt đầu với bất kỳ đỉnh nào và gọi hàm DFS trên đó
2. Tiếp tục đi xuống con đường đó cho đến khi bạn tìm thấy một nút không có cạnh đi ra nữa
3. Thêm nó vào thứ tự cấu trúc liên kết (chúng tôi chèn nó vào ngăn xếp ở chỉ số thứ 0 nếu không chúng tôi sẽ bị đảo ngược thứ tự)
4. Quay lại nút trước đó với các hậu duệ chưa được truy cập tiếp theo
5. Tiếp tục cho đến khi bạn đã truy cập tất cả các nút

Triển khai mã

from collections import defaultdict
 
class Graph:
    def __init__(self, vertices):
        self.graph = defaultdict(list)
        self.V = vertices
    
    def add_edge(self, u, v):
        self.graph[u-1].append(v-1)    def helper(self,u,visited, res):
        visited[u] = True
        for i in self.graph[u]:
            if visited[i] == False:
                self.helper(i, visited, res)
        res.insert(0, u+1)    def topological_sort(self):
        visited = [False]*self.V
        res =[]
        for i in reversed(range(self.V)):
            if visited[i] == False:
                self.helper(i, visited, res)
                
        return res## Driver code
A = 6
B = [[6, 3], [6, 1], [5, 1], [5, 2], [3, 4], [4, 2]]
graph = Graph(A)
for u, v in B:
    graph.add_edge(u, v)
        
res = graph.topological_sort()
print(res) # [5, 6, 1, 3, 4, 2]

Trong phần triển khai ở trên, tôi đã sử dụng Reverse(range(self. V)) vì tôi muốn đảm bảo kết quả là nhỏ nhất về mặt từ điển trong trường hợp chúng tôi có nhiều đơn đặt hàng

mã hóa hạnh phúc

Thêm nội dung tại PlainEnglish. io. Đăng ký nhận bản tin hàng tuần miễn phí của chúng tôi. Theo dõi chúng tôi trên Twitter và LinkedIn. Kiểm tra Sự bất hòa trong cộng đồng của chúng tôi và tham gia Tập thể tài năng của chúng tôi

Sắp xếp tô pô có thể hoạt động với các chu kỳ không?

Sắp xếp tô pô có đệ quy không?

Sắp xếp tô pô có sử dụng BFS hoặc DFS không?

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