Algoritma Pengurutan Topologi: Python, C++ Example

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 lain yang ditunjuk olehnya. Algoritma ini mengikuti beberapa aturan secara berulang hingga pengurutan selesai.

Untuk menyederhanakannya, lihat contoh berikut:

Grafik Sutradara

Di sini, kita dapat melihat bahwa “A” tidak memiliki indegree. Indegree berarti sisi yang mengarah ke sebuah node. “B” dan “C” memiliki prasyarat “A”, kemudian “E” memiliki prasyarat “D” dan “F”. Beberapa node bergantung pada node lain.

Berikut adalah representasi lain dari grafik di atas:

Ketergantungan setiap node (Pengurutan Linier)

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.

Berikut adalah langkah-langkah untuk melakukannya:

Langkah 1) Temukan simpul dengan nol sisi masuk, simpul dengan nol derajat.

Langkah 2) Simpan node dengan derajat masuk nol tersebut ke dalam Antrian atau Tumpukan dan hapus node tersebut dari Graf.

Langkah 3) Kemudian hapus tepi keluar dari simpul tersebut. Ini akan mengurangi jumlah derajat masuk untuk simpul berikutnya.

Pengurutan topologi mensyaratkan bahwa struktur data graf tidak akan memiliki siklus. Sebuah graf akan dianggap sebagai DAG jika memenuhi persyaratan berikut:

• Satu atau lebih node dengan nilai derajat masuk nol.
• Grafik tersebut tidak mengandung siklus apa pun.

Selama masih ada node dalam Graph dan Graph tersebut masih berupa DAG, kita akan menjalankan tiga langkah di atas. Jika tidak, algoritma akan mengalami 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. Misalkan kita memiliki Graf berikut:

Berikut adalah langkah-langkah untuk 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 adalah indegree dan outdegree dari grafik di atas:

Langkah 2) Temukan simpul dengan derajat masuk nol atau nol sisi yang masuk. Simpul dengan derajat masuk nol berarti tidak ada sisi yang menuju ke simpul tersebut. Simpul “A” memiliki derajat masuk nol, artinya tidak ada sisi yang mengarah ke simpul “A”. Jadi, kita akan melakukan tindakan berikut:

• Hapus node ini dan sisi-sisi keluarnya (sisi keluar).
• Tempatkan node di Antrian untuk pemesanan.
• Perbarui jumlah derajat masuk (in-degree) dari node tetangga “A”.

Langkah 3) Kita perlu menemukan node dengan nilai indegree nol. Dalam contoh ini, “B” dan “C” memiliki indegree nol. Di sini, kita dapat mengambil salah satu dari keduanya. Mari kita ambil “B” dan hapus dari Graph. Kemudian perbarui nilai indegree node lainnya. Setelah melakukan operasi ini, Graph dan Queue kita akan terlihat seperti berikut:

Langkah 4) Node “C” tidak memiliki tepi masuk. Jadi, kita akan menghapus node “C” dari Graph dan memasukkannya ke dalam Queue. Kita juga dapat menghapus tepi yang keluar dari “C”. Sekarang, Graph kita akan terlihat seperti ini:

Langkah 5) Kita dapat melihat bahwa node “D” dan “F” memiliki indegree nol. Kita akan mengambil sebuah node dan memasukkannya ke dalam Antrian. Mari kita keluarkan “D” terlebih dahulu. Maka jumlah indegree untuk node “E” akan menjadi 1. Sekarang, tidak akan ada node dari D ke E. Kita perlu melakukan hal yang sama untuk node “F”, dan hasilnya akan seperti berikut:

Langkah 6) Derajat masuk (tepi masuk) dan derajat keluar (tepi keluar) dari node “E” menjadi nol. Jadi, kita telah memenuhi semua prasyarat untuk node “E”. Di sini, kita akan menempatkan “E” di akhir Antrian. Jadi, kita tidak memiliki node yang tersisa, dan algoritma berakhir di sini.

Pseudo Code untuk Pengurutan Topologi

Berikut adalah pseudokode untuk pengurutan topologi 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 0 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

Graf yang mengandung siklus tidak dapat diurutkan secara topologis, karena graf siklik memiliki ketergantungan secara siklik. Misalnya, perhatikan graf ini:

Graf ini bukan DAG (Directed Acyclic Graph) karena A, B, dan C membentuk siklus. Jika Anda perhatikan, tidak ada simpul dengan nilai derajat masuk nol. Menurut Algoritma Kahn, jika kita menganalisis Graf di atas:

• Temukan simpul dengan nol derajat masuk (tidak ada sisi masuk).
• Hapus node tersebut dari Graph dan masukkan ke dalam Queue. Namun, pada Graph di atas, tidak ada node dengan in-degree nol. Setiap node memiliki nilai in-degree lebih besar dari 0.
• Kembalikan antrian kosong, karena tidak dapat menemukan simpul dengan derajat masuk 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 total simpul, maka tidak ada siklus.

Langkah 4) Jika jumlah siklus tidak sama dengan jumlah simpul, maka setidaknya ada satu siklus dalam struktur data graf yang diberikan.

Analisis Kompleksitas Sortiran Topologi

Terdapat dua jenis kompleksitas dalam algoritma. Yaitu:

1. Kompleksitas Waktu
2. Kompleksitas Ruang

Kompleksitas ini direpresentasikan dengan fungsi yang memberikan kompleksitas umum.

Kompleksitas Waktu: Kompleksitas waktu untuk pengurutan topologi adalah sama. Terdapat skenario terburuk, rata-rata, dan terbaik untuk kompleksitas waktu. Kompleksitas waktu untuk pengurutan topologi adalah O(E + V), di mana E adalah jumlah sisi dalam graf, dan V adalah jumlah simpul dalam graf.

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 pengurutan topologi atau penataan topologi. Dapat dikatakan 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 tersebut:

• 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 “order”, yang menyimpan node dalam urutan topologi. Itu juga membutuhkan O (V) spasi.

Ini adalah kompleksitas ruang individual. Jadi, kita perlu memaksimalkan ruang-ruang ini dalam waktu eksekusi. Kompleksitas ruang dilambangkan dengan O(V), di mana V berarti jumlah simpul dalam Graf.

Penerapan Pengurutan Topologi

Pengurutan Topologi memiliki banyak sekali kegunaan. Berikut beberapa di antaranya:

• Ini digunakan ketika sebuah Operasistem ting perlu melakukan alokasi sumber daya.
• Menemukan siklus dalam Graf. Kita dapat memvalidasi apakah Graf tersebut merupakan DAG atau bukan 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.

Pertanyaan Umum Demo Slot