Sắp xếp tôpô: Python, C++ Ví dụ về thuật toán
Sarah Chen
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 DAG (Biểu đồ tuần hoàn có hướng) để mỗi nút xuất hiện trong mảng có thứ tự trước khi tất cả các nút khác được trỏ đến 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 việc sắp xếp hoàn tất.
Để đơn giản hơn, hãy xem ví dụ sau:
Ở đây, chúng ta có thể thấy rằng “A” không có bằng cấp. Nó có 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à nút “D” và “F”. Một số nút phụ thuộc vào các nút khác.
Đây là một cách trình bày khác của Biểu đồ trên:
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.
Ví dụ này hiển thị một biểu đồ có chu trình:
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 bậc 0 đó trong Hàng đợi hoặc Ngăn xếp và xóa nút đó khỏi Biểu đồ.
Bước 3) Sau đó xóa cạnh đi khỏi nút đó.
Điều này sẽ giảm số lượng theo độ cho nút tiếp theo.
Thứ tự tôpô yêu cầu cấu trúc dữ liệu đồ thị sẽ không có bất kỳ chu trình nào.
Biểu đồ sẽ được coi là DAG nếu nó tuân theo 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
Miễn là có các nút trong Đồ thị và Đồ thị vẫn là DAG, chúng ta sẽ chạy ba bước trên. Nếu không, thuật toán sẽ rơi vào phụ thuộc tuần hoàn và Thuật toán Kahn sẽ không thể tìm thấy 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 theo topo. Giả sử chúng ta có Đồ thị sau:
Sau đâ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à mức độ và mức độ của biểu đồ trên:
Bước 2) Tìm nút có độ bằng 0 hoặc cạnh tới bằng 0.
Nút có độ bằng 0 có nghĩa là không có cạnh nào tiến về phía nút đó. Nút “A” có độ 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 hành động sau:
- Loại bỏ nút này và các cạnh ngoài của nó (các cạnh đi)
- Đặt nút vào Hàng đợi để đặt hàng.
- Cập nhật số lượng theo độ 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 bằng 0. Trong ví dụ này, “B” và “C” không có bậc nào.
Ở đây, chúng ta có thể lấy một trong hai cái này. Hãy lấy “B” và xóa nó khỏi Biểu đồ.
Sau đó cập nhật các giá trị độ của các nút khác.
Sau khi thực hiện các thao tác này, Biểu đồ 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 đến. Vì vậy, chúng tôi sẽ xóa nút “C” khỏi Biểu đồ 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ờ, Biểu đồ của chúng ta sẽ trông như thế này:
Bước 5) Chúng ta có thể thấy rằng các nút “D” và “F” có bậc bằng 0. Chúng tôi sẽ lấy một nút và đặt nó vào Hàng đợi.
Trước tiên hãy loại bỏ chữ “D”. Khi đó số bậc của nút “E” sẽ là 1. Bây giờ, sẽ không có nút nào từ D đến E.
Chúng ta cần làm tương tự cho nút “F”, kết quả sẽ như sau:
Bước 6) Mức độ trong (cạnh vào) và mức độ ngoài (cạnh ra) của nút “E” trở thành 0. Vì vậy, chúng tôi đã đáp ứng tất cả các điều kiện tiên quyết cho nút “E”.
Ở đây, chúng tôi đặt chữ “E” ở cuối Hàng đợi. Vì vậy, chúng ta không còn nút nào nên thuật toán kết thúc ở đây.
Mã giả để sắp xếp cấu trúc liên kết
Đây là mã giả để sắp xếp cấu trúc liên kết trong khi 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 O 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ô
Một đồ thị chứa một chu trình không thể được sắp xếp theo thứ tự tôpô. Vì Biểu đồ tuần hoàn có sự phụ thuộc theo cách tuần hoàn.
Ví dụ: kiểm tra Biểu đồ này:
Biểu đồ này không phải là DAG (Biểu đồ tuần hoàn có hướng) vì A, B và C tạo ra một chu trình. Nếu bạn để ý, không có nút nào có giá trị bằng 0.
Theo Thuật toán Kahn, nếu chúng ta phân tích Biểu đồ trên:
- Tìm một nút có độ bằng 0 (không có cạnh nào đến).
- Xóa nút đó khỏi Biểu đồ và đẩy nó vào Hàng đợi.
Tuy nhiên, trong Biểu đồ trên, không có nút nào có số 0 độ. Mỗi nút có giá trị mức độ lớn hơn XNUMX. - Trả về một hàng đợi trống vì nó không thể tìm thấy bất kỳ nút nào có độ bằng 0.
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ố 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ó ít nhất một chu trình trong cấu trúc dữ liệu đồ thị đã cho.
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. Chúng là
- Thời gian phức tạp
- 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 về thời gian là như nhau đối với Topological Sorting. Có các trường hợp xấu nhất, trung bình và tốt nhất cho độ phức tạp về thời gian.
Độ phức tạp thời gian cho 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 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).
Vì vậy, đây là độ phức tạp thời gian riêng lẻ cho từng bước của Sắp xếp theo topo hoặc sắp xếp theo topo. Chúng 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 có nghĩa là hàm độ phức tạp.
Không gian phức tạp: Chúng tôi cần khoảng trống 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à “thứ tự”. Điều đó lưu trữ các nút theo thứ tự tôpô. Điều đó cũng bắt buộc O(V) khoảng trống.
Đây là độ phức tạp của 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 của không gian là O(V), trong đó V là số đỉnh trong Đồ thị.
Ứng dụng sắp xếp tôpô
Có một công dụng rất lớn đối với Sắp xếp cấu trúc liên kết. Dưới đây là một số trong số họ:
- Nó được sử dụng khi Operahệ thống ting cần thực hiện việc phân bổ nguồn lực.
- Tìm một chu trình trong đồ thị. Chúng tôi có thể xác thực xem Biểu đồ có phải là DAG hay không bằng cách sắp xếp cấu trúc liên kết.
- Thứ tự câu trong các ứng dụng tự động hoàn thành.
- Nó được sử dụng để phát hiện bế tắc.
- Loại Lập kế hoạch hoặc lập kế hoạch khóa học khác nhau sử dụng sắp xếp cấu trúc liên kết.
- 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.
