Pengurutan Topologi: Python, C++ Contoh Algoritma
Sarah Chen
Apa itu Algoritma Pengurutan Topologi?
Penyortiran Topologi juga dikenal sebagai algoritma Kahn dan merupakan Algoritma Penyortiran yang populer. Dengan menggunakan grafik berarah sebagai masukan, Pengurutan Topologi mengurutkan node sehingga setiap node muncul sebelum node yang dituju.
Algoritma ini diterapkan pada DAG (Directed Acyclic Graph) sehingga setiap node muncul dalam array yang terurut sebelum semua node lainnya diarahkan ke sana. Algoritme ini mengikuti beberapa aturan berulang kali hingga pengurutan selesai.
Untuk menyederhanakannya, lihat contoh berikut:
Di sini, kita dapat melihat bahwa “A” tidak memiliki derajat masuk. Artinya tepi yang menunjuk ke sebuah node. “B” dan “C” mempunyai prasyarat “A”, kemudian “E” mempunyai prasyarat “D” dan “F”. Beberapa node bergantung pada node lainnya.
Berikut representasi lain dari Grafik di atas:
Jadi, ketika kita meneruskan DAG (Directed Acyclic Graph) ke pengurutan topologi, ini akan memberi kita array dengan urutan linier, di mana elemen pertama tidak memiliki ketergantungan.
Contoh ini menunjukkan grafik dengan siklus:
Berikut langkah-langkah untuk melakukannya:
Langkah 1) Temukan simpul dengan nol sisi masuk, simpul dengan nol derajat.
Langkah 2) Simpan simpul dalam derajat nol itu dalam Antrean atau Tumpukan dan hapus simpul tersebut dari Grafik.
Langkah 3) Kemudian hapus tepi keluar dari node tersebut.
Ini akan mengurangi jumlah derajat untuk node berikutnya.
Pengurutan topologi mengharuskan struktur data grafik tidak memiliki siklus apa pun.
Sebuah grafik akan dianggap DAG jika memenuhi persyaratan berikut:
- Satu atau lebih node dengan nilai derajat masuk nol.
- Grafik tidak mengandung siklus apa pun
Selama masih ada node dalam Grafik dan Grafik masih DAG, kita akan menjalankan tiga langkah di atas. Jika tidak, algoritma akan jatuh ke dalam ketergantungan siklik, dan Algoritma Kahn tidak akan dapat menemukan node dengan derajat masuk nol.
Cara Kerja Penyortiran Topologi
Di sini, kita akan menggunakan “Algoritma Kahn” untuk pengurutan topologi. Katakanlah kita memiliki Grafik berikut:
Berikut langkah-langkah Algoritma Kahn:
Langkah 1) Hitung derajat masuk atau tepi masuk dari semua node dalam Grafik.
Catatan:
- Indegree berarti tepi berarah yang menunjuk ke node.
- Derajat keluar berarti tepi terarah yang berasal dari sebuah simpul.
Berikut derajat masuk dan derajat keluar dari Grafik di atas:
Langkah 2) Temukan simpul dengan nol derajat masuk atau nol sisi masuk.
Node dengan derajat masuk nol berarti tidak ada sisi yang menuju ke node tersebut. Node “A” mempunyai derajat masuk nol, artinya tidak ada sisi yang menunjuk ke node “A”.
Jadi, kita akan melakukan tindakan berikut:
- Hapus node ini dan tepi keluarnya (tepi keluar)
- Tempatkan node di Antrian untuk pemesanan.
- Perbarui hitungan derajat dari simpul tetangga “A”.
Langkah 3) Kita perlu mencari simpul dengan nilai derajat masuk nol. Dalam contoh ini, “B” dan “C” mempunyai derajat masuk nol.
Di sini, kita dapat mengambil salah satu dari keduanya. Mari kita ambil “B” dan menghapusnya dari Grafik.
Kemudian perbarui nilai derajat masuk dari node lainnya.
Setelah melakukan operasi ini, Grafik dan Antrean kita akan terlihat seperti berikut:
Langkah 4) Node “C” tidak memiliki tepi masuk. Jadi, kita akan menghapus node “C” dari Grafik dan memasukkannya ke dalam Antrean.
Kita juga dapat menghapus tepi yang keluar dari “C”.
Sekarang, Grafik kita akan terlihat seperti ini:
Langkah 5) Kita dapat melihat bahwa node “D” dan “F” mempunyai derajat masuk sebesar nol. Kami akan mengambil sebuah node dan memasukkannya ke dalam Antrian.
Mari kita keluarkan “D” terlebih dahulu. Maka hitungan derajat masuk untuk simpul “E” adalah 1. Sekarang, tidak akan ada simpul dari D ke E.
Kita perlu melakukan hal yang sama untuk node “F”, hasil kita akan seperti berikut:
Langkah 6) Derajat masuk (tepi masuk) dan derajat keluar (tepi keluar) dari simpul “E” menjadi nol. Jadi, kita telah memenuhi semua prasyarat untuk node “E”.
Di sini, kami menempatkan “E” di akhir Antrian. Jadi, kita tidak punya node lagi, jadi algoritmanya berakhir di sini.
Kode Pseudo untuk Penyortiran Topologi
Berikut pseudo-code untuk pengurutan topologi saat menggunakan Algoritma 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
Pengurutan topologi juga dapat diimplementasikan menggunakan DFS (Penelusuran Pertama Kedalaman) metode. Namun pendekatan tersebut merupakan metode rekursif. Algoritma Kahn lebih efisien dibandingkan pendekatan DFS.
C++ Implementasi Penyortiran Topologi
#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();
}
Keluaran
0 1 2 3 5 4
Python Implementasi Penyortiran Topologi
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()
Keluaran
[0, 1, 2, 3, 5, 4]
Grafik Siklik Algoritma Pengurutan Topologi
Grafik yang berisi siklus tidak dapat diurutkan secara topologi. Karena Grafik siklik memiliki ketergantungan secara siklik.
Misalnya, periksa Grafik ini:
Graf ini bukan DAG (Grafik Asiklik Terarah) karena A, B, dan C membentuk siklus. Jika Anda perhatikan, tidak ada simpul dengan nilai derajat nol.
Menurut Algoritma Kahn, jika kita menganalisis Grafik di atas:
- Temukan simpul dengan nol derajat masuk (tidak ada sisi masuk).
- Hapus simpul itu dari Grafik dan dorong ke Antrian.
Namun, pada Grafik di atas, tidak ada node dengan derajat nol. Setiap node memiliki nilai derajat lebih besar dari 0. - Mengembalikan antrian kosong, karena tidak dapat menemukan node dengan derajat nol.
Kita dapat mendeteksi siklus menggunakan urutan topologi dengan langkah-langkah berikut:
Langkah 1) Lakukan Penyortiran topologi.
Langkah 2) Hitung jumlah total elemen dalam daftar yang diurutkan secara topologi.
Langkah 3) Jika jumlah elemen sama dengan jumlah titik, maka tidak ada siklus.
Langkah 4) Jika tidak sama dengan jumlah simpul, maka paling sedikit terdapat satu siklus dalam struktur data graf yang diberikan.
Analisis Kompleksitas Sortiran Topologi
Ada dua jenis kompleksitas dalam algoritma. Yaitu:
- Kompleksitas Waktu
- Kompleksitas Ruang
Kompleksitas ini direpresentasikan dengan fungsi yang memberikan kompleksitas umum.
Kompleksitas Waktu: Semua kompleksitas waktu sama untuk Topological Sorting. Ada skenario terburuk, rata-rata, dan terbaik untuk kompleksitas waktu.
Kompleksitas waktu untuk Penyortiran topologi adalah O(E + V), di sini, E berarti jumlah Tepi dalam Grafik, dan V berarti jumlah titik dalam Grafik.
Mari kita uraikan kerumitan ini:
Langkah 1) Pada awalnya, kami akan menghitung semua derajat masuk. Untuk melakukan itu, kita perlu melewati semua sisi, dan awalnya, kita akan menetapkan semua V titik dalam derajat ke nol. Jadi, langkah tambahan yang kami selesaikan adalah HAI(V+E).
Langkah 2) Kita akan menemukan node dengan nilai derajat masuk nol. Kita perlu mencari dari nomor V dari titik tersebut. Jadi, langkah-langkahnya akan selesai O (V).
Langkah 3) Untuk setiap simpul dengan derajat masuk nol, kita akan menghapus simpul tersebut dan mengurangi derajat masuknya. Melakukan operasi ini untuk semua node akan memakan waktu HAI(E).
Langkah 4) Terakhir, kami akan memeriksa apakah ada siklus atau tidak. Kami akan memeriksa apakah jumlah total elemen dalam array yang diurutkan sama dengan jumlah total node. Itu akan memakan waktu O (1).
Jadi, ini adalah kompleksitas waktu individual untuk setiap langkah Penyortiran topologi atau pengurutan topologi. Kita dapat mengatakan bahwa kompleksitas waktu dari perhitungan di atas adalah O( V + E ); di sini, O berarti fungsi kompleksitas.
Kompleksitas Ruang: Kami membutuhkan ruang O(V) untuk menjalankan algoritma pengurutan topologi.
Berikut adalah langkah-langkah di mana kami membutuhkan ruang untuk program ini:
- Kami harus menghitung semua derajat ke dalam node yang ada di Grafik. Karena Grafik memiliki total V node, kita perlu membuat array berukuran V. Jadi, ruang yang dibutuhkan adalah O (V).
- Struktur data Antrian digunakan untuk menyimpan node dengan derajat masuk nol. Kami menghapus node dengan derajat masuk nol dari Grafik asli dan menempatkannya di Antrean. Untuk ini, ruang yang dibutuhkan adalah O (V).
- Array tersebut diberi nama “urutan”. Itu menyimpan node dalam urutan topologi. Itu juga diperlukan O (V) spasi.
Ini adalah kompleksitas ruang individual. Jadi, kita perlu memaksimalkan ruang-ruang ini dalam waktu proses.
Kompleksitas ruang adalah singkatan dari O(V), di mana V berarti jumlah titik sudut dalam Grafik.
Penerapan Pengurutan Topologi
Ada kegunaan besar untuk Penyortiran Topologi. Berikut beberapa di antaranya:
- Ini digunakan ketika Operasistem ting perlu melakukan alokasi sumber daya.
- Menemukan siklus dalam Grafik. Kita dapat memvalidasi apakah Grafik tersebut DAG atau tidak dengan pengurutan topologi.
- Urutan kalimat di aplikasi pelengkapan otomatis.
- Ini digunakan untuk mendeteksi kebuntuan.
- Berbagai jenis Penjadwalan atau penjadwalan kursus menggunakan pengurutan topologi.
- Menyelesaikan ketergantungan. Misalnya, jika Anda mencoba menginstal suatu paket, paket tersebut mungkin juga memerlukan paket lain. Pemesanan topologi menemukan semua paket yang diperlukan untuk menginstal paket saat ini.
- Linux menggunakan pengurutan topologi di "apt" untuk memeriksa ketergantungan paket.
