Terjemahan artikel disiapkan sebelum dimulainya kursus "Algoritma untuk Pengembang" .
Penyortiran topologis untuk grafik asiklik terarah (Grafik Asiklik Terarah, yang selanjutnya disebut DAG) adalah pengurutan linear dari simpul-simpul yang dipegang oleh kondisi berikut: untuk setiap tepi terarah uv, simpul u mendahului simpul v dalam pengurutan. Jika grafik bukan DAG, maka penyortiran topologi tidak mungkin dilakukan.Misalnya, pengurutan topologis dari grafik di bawah ini adalah "5 4 2 3 1 0". Ada beberapa penyortiran topologi untuk suatu grafik. Misalnya, pengurutan topologi lain untuk grafik yang sama adalah "4 5 2 3 1 0". Verteks pertama dalam penyortiran topologi selalu merupakan titik tanpa tepi yang masuk.
Penyortiran topologis vs deep walk:Ketika berjalan dalam(Depth First Traversal, yang selanjutnya disebut sebagai DFS ) kami output vertex dan kemudian secara rekursif memanggil DFS untuk vertex yang berdekatan. Dalam penyortiran topologis, kita perlu menampilkan titik di depan simpul yang berdekatan. Misalnya, dalam grafik ini, titik "5" harus ditampilkan sebelum titik "0", dan, tidak seperti DFS , titik "4" juga harus ditampilkan sebelum titik "0". Ini membedakan penyortiran topologis dari DFS. Sebagai contoh, DFS dari kolom di atas adalah "5 2 3 1 0 4", tetapi ini bukan jenis topologi.Rekomendasi: sebelum beralih ke implementasi algoritma, pertama-tama cobalah untuk memahami tugas dalam praktik .Algoritma pencarian penyortiran topologis.Untuk memulai, kami sarankan Anda membiasakan diri dengan implementasi DFS ini . Kami dapat memodifikasi DFS sehingga penyortiran topologi grafik diperoleh. Dalam dfskita mulai dengan vertex yang cocok, yang pertama kali kita hasilkan, dan kemudian secara rekursif memanggil DFS untuk simpul-simpul yang berdekatan. Dalam penyortiran topologi, kami menggunakan tumpukan sementara. Vertex tidak segera ditampilkan - pertama, penyortiran topologi dipanggil untuk semua simpul yang berdekatan, kemudian verteks didorong ke stack. Hanya setelah melintasi semua simpul adalah isi tumpukan ditampilkan. Perhatikan bahwa sebuah vertex didorong ke stack hanya ketika semua simpul yang berdekatan (dan simpul yang berdekatan, dll.) Sudah ada di stack.Gambar di bawah ini adalah ilustrasi dari pendekatan di atas:
:
(G)
0 ā
1ā
2 ā 3
3 ā 1
4 ā 0, 1
5 ā 2, 0
1:
(0), visited[0] = true
. .
0
2:
(1), visited[1] = true
. .
0 1
3:
(2),, visited[2] = true
(3),, visited[3] = true
1 .
0 1 3 2
4:
(4),, visited[4] = true
Verteks 0 dan 1 sudah dikunjungi. Tidak ada lagi panggilan rekursif.
Tumpukan 0 1 3 2 4
Langkah 5:
Penyortiran topologis (5), dikunjungi [5] = true,
Verteks 2 dan 0 sudah dikunjungi. Tidak ada lagi panggilan rekursif
Stack 0 1 3 2 4 5
Langkah 6:
Tarik semua item tumpukan dari atas ke bawah
Berikut ini adalah implementasi semacam topologi. Silakan periksa implementasi DFT untuk grafik yang terputus dan perhatikan perbedaan antara kode kedua yang diberikan di sana dan kode di bawah ini.C ++
#include<iostream>
#include <list>
#include <stack>
using namespace std;
class Graph
{
int V;
list<int> *adj;
void topologicalSortUtil(int v, bool visited[], stack<int> &Stack);
public:
Graph(int V);
void addEdge(int v, int w);
void topologicalSort();
};
Graph::Graph(int V)
{
this->V = V;
adj = new list<int>[V];
}
void Graph::addEdge(int v, int w)
{
adj[v].push_back(w);
}
void Graph::topologicalSortUtil(int v, bool visited[],
stack<int> &Stack)
{
visited[v] = true;
list<int>::iterator i;
for (i = adj[v].begin(); i != adj[v].end(); ++i)
if (!visited[*i])
topologicalSortUtil(*i, visited, Stack);
Stack.push(v);
}
void Graph::topologicalSort()
{
stack<int> Stack;
bool *visited = new bool[V];
for (int i = 0; i < V; i++)
visited[i] = false;
for (int i = 0; i < V; i++)
if (visited[i] == false)
topologicalSortUtil(i, visited, Stack);
while (Stack.empty() == false)
{
cout << Stack.top() << " ";
Stack.pop();
}
}
int main()
{
Graph g(6);
g.addEdge(5, 2);
g.addEdge(5, 0);
g.addEdge(4, 0);
g.addEdge(4, 1);
g.addEdge(2, 3);
g.addEdge(3, 1);
cout << "Following is a Topological Sort of the given graph \n";
g.topologicalSort();
return 0;
}
Jawa
import java.io.*;
import java.util.*;
class Graph
{
private int V;
private LinkedList<Integer> adj[];
Graph(int v)
{
V = v;
adj = new LinkedList[v];
for (int i=0; i<v; ++i)
adj[i] = new LinkedList();
}
void addEdge(int v,int w) { adj[v].add(w); }
void topologicalSortUtil(int v, boolean visited[],
Stack stack)
{
visited[v] = true;
Integer i;
Iterator<Integer> it = adj[v].iterator();
while (it.hasNext())
{
i = it.next();
if (!visited[i])
topologicalSortUtil(i, visited, stack);
}
stack.push(new Integer(v));
}
void topologicalSort()
{
Stack stack = new Stack();
boolean visited[] = new boolean[V];
for (int i = 0; i < V; i++)
visited[i] = false;
for (int i = 0; i < V; i++)
if (visited[i] == false)
topologicalSortUtil(i, visited, stack);
while (stack.empty()==false)
System.out.print(stack.pop() + " ");
}
public static void main(String args[])
{
Graph g = new Graph(6);
g.addEdge(5, 2);
g.addEdge(5, 0);
g.addEdge(4, 0);
g.addEdge(4, 1);
g.addEdge(2, 3);
g.addEdge(3, 1);
System.out.println("Following is a Topological " +
"sort of the given graph");
g.topologicalSort();
}
}
Python
class Graph:
def __init__(self,vertices):
self.graph = defaultdict(list)
self.V = vertices
def addEdge(self,u,v):
self.graph[u].append(v)
def topologicalSortUtil(self,v,visited,stack):
visited[v] = True
for i in self.graph[v]:
if visited[i] == False:
self.topologicalSortUtil(i,visited,stack)
stack.insert(0,v)
def topologicalSort(self):
visited = [False]*self.V
stack =[]
for i in range(self.V):
if visited[i] == False:
self.topologicalSortUtil(i,visited,stack)
print stack
g= Graph(6)
g.addEdge(5, 2);
g.addEdge(5, 0);
g.addEdge(4, 0);
g.addEdge(4, 1);
g.addEdge(2, 3);
g.addEdge(3, 1);
print "Following is a Topological Sort of the given graph"
g.topologicalSort()
<b>:</b>
Following is a Topological Sort of the given graph
5 4 2 3 1 0
Kesulitan waktu: algoritma di atas adalah DFS dengan tumpukan tambahan. Dengan demikian, kompleksitas waktu sama dengan DFS, yaitu O (V + E).Catatan: Anda juga dapat menggunakan vektor, bukan tumpukan. Jika Anda menggunakan vektor untuk mendapatkan penyortiran topologis, Anda perlu menampilkan elemen dalam urutan terbalik.Aplikasi:Penyortiran topologis terutama digunakan untuk pekerjaan penjadwalan dari ketergantungan yang diberikan di antara mereka. Dalam ilmu komputer, ini digunakan untuk merencanakan perintah, mengatur sel untuk menghitung formula ketika menghitung ulang nilai formula dalam spreadsheet, sintesis logis, menentukan urutan tugas kompilasi yang akan dilakukan dalam makefile, serialisasi data, dan menyelesaikan dependensi simbolik dalam linker [ 2 ].Artikel terkait
Algoritma Kahn untuk pengurutan topologi : algoritma O (V + E) lainnya.Semua penyortiran topologi dari grafik asiklik yang berorientasiReferensi
http://www.personal.kent.edu/~rmuhamma/Algorithms/MyAlgorithms/GraphAlgor/topoSort.htmhttp://en.wikipedia.org/wiki/Topological_sortingSilakan tinggalkan komentar jika Anda menemukan kesalahan, atau jika Anda ingin berbagi informasi tambahan tentang topik yang dibahas.
Pelajari lebih lanjut tentang kursus.