Thuật toán sắp xếp tôpô: Python, C++ Ví dụ

Thuật toán sắp xếp tô pô là gì?

Sắp xếp tôpô còn được gọi là thuật toán Kahn và là một thuật toán sắp xếp phổ biến. Sử dụng biểu đồ có hướng làm đầu vào, Sắp xếp tôpô sẽ sắp xếp các nút sao cho mỗi nút xuất hiện trước nút mà nó trỏ tới.

Thuật toán này được áp dụng trên đồ thị có hướng không chu trình (DAG) sao cho mỗi nút xuất hiện trong mảng đã sắp xếp trước tất cả các nút khác mà nó trỏ đến. Thuật toán này tuân theo một số quy tắc lặp đi lặp lại cho đến khi quá trình sắp xếp hoàn tất.

Để đơn giản hơn, hãy xem ví dụ sau:

Đồ thị có hướng

Ở đây, ta thấy rằng “A” không có bậc vào. Bậc vào nghĩa là cạnh trỏ đến một nút. “B” và “C” có điều kiện tiên quyết là “A”, sau đó “E” có điều kiện tiên quyết là các nút “D” và “F”. Một số nút phụ thuộc vào các nút khác.

Dưới đây là một cách biểu diễn khác của đồ thị trên:

Sự phụ thuộc của mỗi nút (Sắp xếp tuyến tính)

Vì vậy, khi chúng ta chuyển DAG (Biểu đồ tuần hoàn có hướng) sang sắp xếp tôpô, nó sẽ cung cấp cho chúng ta một mảng có thứ tự tuyến tính, trong đó phần tử đầu tiên không có phần phụ thuộc.

Dưới đây là các bước để thực hiện việc này:

Bước 1) Tìm nút có các cạnh đến bằng 0, một nút có độ bằng 0.

Bước 2) Lưu trữ nút có bậc vào bằng 0 đó vào Hàng đợi hoặc Ngăn xếp và xóa nút đó khỏi Đồ thị.

Bước 3) Sau đó, xóa cạnh đi ra từ nút đó. Thao tác này sẽ làm giảm số bậc vào của nút tiếp theo.

Thứ tự tôpô yêu cầu cấu trúc dữ liệu đồ thị không được có bất kỳ chu trình nào. Một đồ thị sẽ được coi là đồ thị có hướng không chu trình (DAG) nếu nó đáp ứng các yêu cầu sau:

• Một hoặc nhiều nút có giá trị bậc bằng 0.
• Đồ thị không chứa bất kỳ chu trình nào.

Chừng nào đồ thị vẫn còn các nút và đồ thị vẫn là một đồ thị có hướng không chu trình (DAG), chúng ta sẽ thực hiện ba bước trên. Nếu không, thuật toán sẽ rơi vào vòng phụ thuộc và thuật toán Kahn sẽ không thể tìm được nút có bậc vào bằng không.

Cách sắp xếp cấu trúc liên kết hoạt động

Ở đây, chúng ta sẽ sử dụng "Thuật toán Kahn" để sắp xếp topo. Giả sử ta có đồ thị sau:

Dưới đây là các bước thực hiện thuật toán Kahn:

Bước 1) Tính toán cạnh không độ hoặc cạnh tới của tất cả các nút trong Biểu đồ.

Lưu ý:

• Indegree có nghĩa là các cạnh được định hướng trỏ đến nút.
• Mức độ ngoài có nghĩa là các cạnh được định hướng đến từ một nút.

Đây là bậc vào và bậc ra của đồ thị trên:

Bước 2) Tìm nút có bậc vào bằng 0 hoặc không có cạnh đi vào. Nút có bậc vào bằng 0 nghĩa là không có cạnh nào đi về phía nút đó. Nút “A” có bậc vào bằng 0, nghĩa là không có cạnh nào trỏ đến nút “A”. Vì vậy, chúng ta sẽ thực hiện các bước sau:

• Xóa nút này và các cạnh đi ra của nó.
• Đặt nút vào Hàng đợi để đặt hàng.
• Cập nhật số lượng liên kết vào của nút lân cận của “A”.

Bước 3) Chúng ta cần tìm một nút có giá trị bậc vào bằng không. Trong ví dụ này, “B” và “C” có bậc vào bằng không. Ở đây, chúng ta có thể chọn một trong hai. Hãy chọn “B” và xóa nó khỏi đồ thị. Sau đó cập nhật giá trị bậc vào của các nút khác. Sau khi thực hiện các thao tác này, đồ thị và hàng đợi của chúng ta sẽ trông như sau:

Bước 4) Nút “C” không có cạnh đi vào. Vì vậy, chúng ta sẽ xóa nút “C” khỏi đồ thị và đẩy nó vào hàng đợi. Chúng ta cũng có thể xóa cạnh đi ra từ “C”. Bây giờ, đồ thị của chúng ta sẽ trông như thế này:

Bước 5) Ta thấy rằng các nút “D” và “F” có bậc vào bằng 0. Ta sẽ lấy một nút và đưa nó vào hàng đợi. Trước tiên, hãy lấy “D” ra. Khi đó, bậc vào của nút “E” sẽ là 1. Lúc này, sẽ không còn nút nào nối từ D đến E nữa. Ta cần làm tương tự với nút “F”, và kết quả sẽ như sau:

Bước 6) Độ vào (cạnh đi vào) và độ ra (cạnh đi ra) của nút “E” đã trở thành 0. Như vậy, chúng ta đã đáp ứng tất cả các điều kiện tiên quyết cho nút “E”. Tại đây, chúng ta sẽ đặt “E” vào cuối hàng đợi. Vì vậy, chúng ta không còn nút nào nữa và thuật toán kết thúc tại đây.

Biệt danh Code để sắp xếp tôpô

Đây là mã giả cho thuật toán sắp xếp tôpô sử dụng thuật toán Kahn.

function TopologicalSort( Graph G ):
  for each node in G:
    calculate the indegree
  start = Node with 0 indegree
  G.remove(start)
  topological_list = [start]
  while node with 0 indegree present:
    topological_list.append(node)
    G.remove(node)
    // Update indegree of present nodes
  return topological_list

Sắp xếp cấu trúc liên kết cũng có thể được thực hiện bằng cách sử dụng DFS (Tìm kiếm sâu đầu tiên) phương pháp. Tuy nhiên, cách tiếp cận đó là phương pháp đệ quy. Thuật toán của Kahn hiệu quả hơn phương pháp DFS.

C++ Thực hiện sắp xếp tôpô

#include<bits/stdc++.h>
using namespace std;
class graph{
  int vertices;
  list<int> *adjecentList;
public:
  graph(int vertices){
    this->vertices = vertices;
    adjecentList = new list<int>[vertices];
  }
  void createEdge(int u, int v){
    adjecentList[u].push_back(v);
  }
  void TopologicalSort(){
    // filling the vector with zero initially
    vector<int> indegree_count(vertices,0);

    for(int i=0;i<vertices;i++){
      list<int>::iterator itr;
      for(itr=adjecentList[i].begin(); itr!=adjecentList[i].end();itr++){
        indegree_count[*itr]++;
      }
    }
    queue<int> Q;
    for(int i=0; i<vertices;i++){
      if(indegree_count[i]==0){
        Q.push(i);
      }
    }
    int visited_node = 0;
    vector<int> order;
    while(!Q.empty()){
      int u = Q.front();
      Q.pop();
      order.push_back(u);

      list<int>::iterator itr;
      for(itr=adjecentList[u].begin(); itr!=adjecentList[u].end();itr++){
        if(--indegree_count[*itr]==0){
          Q.push(*itr);
        }
      }
      visited_node++;
    }
    if(visited_node!=vertices){
      cout<<"There's a cycle present in the Graph.\nGiven graph is not DAG"<<endl;
      return;
    }
    for(int i=0; i<order.size();i++){
      cout<<order[i]<<"\t";
    }
  }
};
int main(){
  graph G(6);
  G.createEdge(0,1);
  G.createEdge(0,2);
  G.createEdge(1,3);
  G.createEdge(1,5);
  G.createEdge(2,3);
  G.createEdge(2,5);
  G.createEdge(3,4);
  G.createEdge(5,4);
  G.TopologicalSort();
}

Đầu ra

0       1       2       3       5       4

Python Thực hiện sắp xếp tôpô

from collections import defaultdict
class graph:
    def __init__(self, vertices):
        self.adjacencyList = defaultdict(list)
        self.Vertices = vertices  # No. of vertices
    # function to add an edge to adjacencyList
    def createEdge(self, u, v):
        self.adjacencyList[u].append(v)
    # The function to do Topological Sort.
    def topologicalSort(self):
        total_indegree = [0]*(self.Vertices)
        for i in self.adjacencyList:
            for j in self.adjacencyList[i]:
                total_indegree[j] += 1
        queue = []
        for i in range(self.Vertices):
            if total_indegree[i] == 0:
                queue.append(i)
        visited_node = 0
        order = []
        while queue:
            u = queue.pop(0)
            order.append(u)
            for i in self.adjacencyList[u]:
                total_indegree[i] -= 1

                if total_indegree[i] == 0:
                    queue.append(i)
            visited_node += 1
        if visited_node != self.Vertices:
            print("There's a cycle present in the Graph.\nGiven graph is not DAG")
        else:
            print(order)
G = graph(6)
G.createEdge(0,1)
G.createEdge(0,2)
G.createEdge(1,3)
G.createEdge(1,5)
G.createEdge(2,3)
G.createEdge(2,5)
G.createEdge(3,4)
G.createEdge(5,4)
G.topologicalSort()

Đầu ra

[0, 1, 2, 3, 5, 4]

Đồ thị tuần hoàn của thuật toán sắp xếp tôpô

Đồ thị chứa chu trình không thể được sắp thứ tự về mặt tôpô, vì đồ thị có chu trình thể hiện sự phụ thuộc theo kiểu chu trình. Ví dụ, hãy xem đồ thị này:

Đồ thị này không phải là đồ thị có hướng không chu trình (DAG) vì A, B và C tạo thành một chu trình. Nếu để ý, bạn sẽ thấy không có nút nào có bậc vào bằng 0. Theo thuật toán Kahn, nếu phân tích đồ thị trên:

• Tìm một nút có độ bằng 0 (không có cạnh nào đến).
• Hãy xóa nút đó khỏi đồ thị và đẩy nó vào hàng đợi. Tuy nhiên, trong đồ thị trên, không có nút nào có bậc vào bằng 0. Mỗi nút đều có giá trị bậc vào lớn hơn 0.
• Trả về hàng đợi rỗng vì không tìm thấy nút nào có bậc vào bằng không.

Chúng ta có thể phát hiện chu kỳ bằng cách sử dụng thứ tự tôpô theo các bước sau:

Bước 1) Thực hiện sắp xếp topo.

Bước 2) Tính tổng số phần tử trong danh sách được sắp xếp theo cấu trúc liên kết.

Bước 3) Nếu số lượng phần tử bằng tổng số đỉnh thì không có chu trình.

Bước 4) Nếu nó không bằng số đỉnh, thì cấu trúc dữ liệu đồ thị đã cho có ít nhất một chu trình.

Phân tích độ phức tạp của sắp xếp theo topo

Có hai loại độ phức tạp trong thuật toán. Đó là:

1. Thời gian phức tạp
2. Không gian phức tạp

Những độ phức tạp này được biểu diễn bằng một hàm cung cấp độ phức tạp chung.

Độ phức tạp về thời gian: Độ phức tạp thời gian của thuật toán Sắp xếp tôpô là như nhau. Có các trường hợp xấu nhất, trung bình và tốt nhất về độ phức tạp thời gian. Độ phức tạp thời gian của thuật toán Sắp xếp tôpô là O(E + V), trong đó E là số cạnh trong đồ thị và V là số đỉnh trong đồ thị.

Hãy cùng nhau vượt qua sự phức tạp này:

Bước 1) Lúc đầu, chúng tôi sẽ tính toán tất cả các mức độ. Để làm điều đó, chúng ta cần đi qua tất cả các cạnh và ban đầu, chúng ta sẽ gán tất cả độ góc của đỉnh V bằng 0. Vì vậy, các bước tăng dần mà chúng tôi hoàn thành sẽ là O(V+E).

Bước 2) Chúng ta sẽ tìm thấy nút có giá trị độ bằng 0. Chúng ta cần tìm kiếm từ số V của đỉnh. Vì vậy, các bước hoàn thành sẽ là O(V).

Bước 3) Đối với mỗi nút có độ bằng 0, chúng tôi sẽ loại bỏ nút đó và giảm độ. Việc thực hiện thao tác này cho tất cả các nút sẽ mất O(E).

Bước 4) Cuối cùng, chúng ta sẽ kiểm tra xem có chu kỳ nào hay không. Chúng ta sẽ kiểm tra xem tổng số phần tử trong mảng đã sắp xếp có bằng tổng số nút hay không. Nó sẽ mất O (1).

Như vậy, đây là độ phức tạp thời gian riêng lẻ cho mỗi bước của quá trình sắp xếp topo hoặc thứ tự topo. Ta có thể nói rằng độ phức tạp thời gian từ phép tính trên sẽ là O(V + E); ở đây, O là hàm độ phức tạp.

Không gian phức tạp: Chúng tôi cần không gian O(V) để chạy thuật toán sắp xếp tôpô. Dưới đây là các bước mà chúng tôi cần không gian cho chương trình:

• Chúng tôi phải tính toán tất cả mức độ của các nút có trong Biểu đồ. Vì Biểu đồ có tổng số nút V nên chúng ta cần tạo một mảng có kích thước V. Vì vậy, không gian cần thiết là O(V).
• Cấu trúc dữ liệu Hàng đợi được sử dụng để lưu trữ nút có mức độ bằng 0. Chúng tôi đã xóa các nút có độ bằng 0 khỏi Biểu đồ ban đầu và đặt chúng vào Hàng đợi. Đối với điều này, không gian cần thiết là O(V).
• Mảng được đặt tên là “order”, lưu trữ các nút theo thứ tự tôpô. Điều đó cũng đòi hỏi O(V) khoảng trống.

Đây là độ phức tạp không gian riêng lẻ. Vì vậy, chúng ta cần tối đa hóa các không gian này trong thời gian chạy. Độ phức tạp không gian được ký hiệu là O(V), trong đó V là số lượng đỉnh trong đồ thị.

Ứng dụng sắp xếp tôpô

Thuật toán sắp xếp tôpô có rất nhiều ứng dụng. Dưới đây là một số ví dụ:

• Nó được sử dụng khi một Operahệ thống ting cần thực hiện việc phân bổ nguồn lực.
• Tìm chu trình trong đồ thị. Chúng ta có thể kiểm tra xem đồ thị có phải là đồ thị có hướng không chu trình (DAG) hay không bằng cách sử dụng thuật toán sắp xếp tôpô.
• Thứ tự câu trong các ứng dụng tự động hoàn thành.
• Nó được dùng để phát hiện bế tắc.
• Các loại lập lịch trình hoặc lập lịch khóa học khác nhau sử dụng thuật toán sắp xếp topo.
• Giải quyết sự phụ thuộc. Ví dụ: nếu bạn cố gắng cài đặt một gói, gói đó cũng có thể cần các gói khác. Thứ tự cấu trúc liên kết tìm ra tất cả các gói cần thiết để cài đặt gói hiện tại.
• Linux sử dụng sắp xếp cấu trúc liên kết trong “apt” để kiểm tra sự phụ thuộc của các gói.

Câu Hỏi Thường Gặp