Vor Beginn des Kurses "Algorithmen fĂŒr Entwickler" wurde eine Ăbersetzung des Artikels erstellt .
Die topologische Sortierung fĂŒr einen gerichteten azyklischen Graphen (gerichtete azyklische Graphen, im Folgenden als DAG bezeichnet) ist eine lineare Anordnung von Scheitelpunkten, fĂŒr die die folgende Bedingung gilt: FĂŒr jede gerichtete Kante uv steht der Scheitelpunkt u in der Reihenfolge vor dem Scheitelpunkt v. Wenn das Diagramm keine DAG ist, ist eine topologische Sortierung nicht möglich.Die topologische Sortierung des folgenden Diagramms lautet beispielsweise "5 4 2 3 1 0". Es gibt mehrere topologische Sortierungen fĂŒr ein Diagramm. Eine andere topologische Sortierung fĂŒr denselben Graphen lautet beispielsweise "4 5 2 3 1 0". Der erste Scheitelpunkt bei der topologischen Sortierung ist immer der Scheitelpunkt ohne eingehende Kanten.
Topologische Sortierung vs. Deep Walk:Wenn Sie tief gehen(Depth First Traversal, im Folgenden als DFS bezeichnet ) Wir geben den Scheitelpunkt aus und rufen dann rekursiv DFS fĂŒr benachbarte Scheitelpunkte auf. Bei der topologischen Sortierung mĂŒssen wir den Scheitelpunkt vor den benachbarten Scheitelpunkten anzeigen. In diesem Diagramm sollte beispielsweise der Scheitelpunkt â5â vor dem Scheitelpunkt â0â angezeigt werden, und im Gegensatz zu DFS sollte der Scheitelpunkt â4â auch vor dem Scheitelpunkt â0â angezeigt werden. Dies unterscheidet die topologische Sortierung von der DFS. Das DFS der obigen Spalte lautet beispielsweise "5 2 3 1 0 4", dies ist jedoch keine topologische Sortierung.Empfehlung: Bevor Sie mit der Implementierung des Algorithmus fortfahren, versuchen Sie zunĂ€chst, die Aufgabe in der Praxis zu verstehen .Suchalgorithmus fĂŒr topologische Sortierung.Wir empfehlen Ihnen, sich zunĂ€chst mit dieser DFS-Implementierung vertraut zu machen . Wir können DFS so modifizieren , dass eine topologische Sortierung des Graphen erhalten wird. In dfsWir beginnen mit einem geeigneten Scheitelpunkt, den wir zuerst ausgeben, und rufen dann rekursiv DFS fĂŒr seine benachbarten Scheitelpunkte auf. Bei der topologischen Sortierung verwenden wir einen temporĂ€ren Stapel. Ein Scheitelpunkt wird nicht sofort angezeigt. Zuerst wird die topologische Sortierung fĂŒr alle benachbarten Scheitelpunkte aufgerufen, dann wird der Scheitelpunkt auf den Stapel verschoben. Erst nach dem Durchlaufen aller Eckpunkte wird der Inhalt des Stapels angezeigt. Beachten Sie, dass ein Scheitelpunkt nur dann auf den Stapel verschoben wird, wenn sich alle benachbarten Scheitelpunkte (und ihre benachbarten Scheitelpunkte usw.) bereits auf dem Stapel befinden.Das Bild unten veranschaulicht den obigen Ansatz:
:
(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
Die Eckpunkte 0 und 1 sind bereits besucht. Keine rekursiven Aufrufe mehr.
Stapel 0 1 3 2 4
Schritt 5:
Topologische Sortierung (5), besucht [5] = wahr Die
Eckpunkte 2 und 0 sind bereits besucht. Keine rekursiven Aufrufe mehr.
Stapel 0 1 3 2 4 5
Schritt 6:
Ziehen Sie alle Stapelelemente von oben nach unten
Das Folgende sind topologische Sortierimplementierungen. ĂberprĂŒfen Sie die DFT- Implementierung auf ein nicht verbundenes Diagramm und beachten Sie die Unterschiede zwischen dem dort angegebenen zweiten Code und dem folgenden Code.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;
}
Java
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
Zeitliche Schwierigkeit: Der obige Algorithmus ist DFS mit einem zusĂ€tzlichen Stapel. Somit ist die zeitliche KomplexitĂ€t dieselbe wie die von DFS, die O (V + E) ist.Hinweis: Sie können auch einen Vektor anstelle eines Stapels verwenden. Wenn Sie einen Vektor verwenden, um eine topologische Sortierung zu erhalten, mĂŒssen Sie die Elemente in umgekehrter Reihenfolge ausgeben.Anwendung:Die topologische Sortierung wird hauptsĂ€chlich zum Planen von Arbeiten anhand bestimmter AbhĂ€ngigkeiten zwischen ihnen verwendet. In der Informatik wird es verwendet, um Befehle zu planen, Zellen fĂŒr die Berechnung von Formeln zu organisieren, wenn Formelwerte in Tabellenkalkulationen neu berechnet werden, logisch zu synthetisieren, die Reihenfolge der in Makefiles auszufĂŒhrenden Kompilierungsaufgaben zu bestimmen, Daten zu serialisieren und symbolische AbhĂ€ngigkeiten in Linkern aufzulösen [ 2 ].Zum Thema passende Artikel
Kahn-Algorithmus zur topologischen Sortierung : ein weiterer O (V + E) -Algorithmus.Alle topologischen Sortierungen eines orientierten azyklischen GraphenVerweise
http://www.personal.kent.edu/~rmuhamma/Algorithms/MyAlgorithms/GraphAlgor/topoSort.htmhttp://en.wikipedia.org/wiki/Topological_sortingBitte hinterlassen Sie einen Kommentar, wenn Sie einen Fehler finden oder teilen möchten zusÀtzliche Informationen zum diskutierten Thema.
Erfahren Sie mehr ĂŒber den Kurs.