Sind topologische Sortierung verschieden von DFS nur in dieser Verarbeitung von aktuellen Elementen nach rekursiven Aufruf erfolgt

Question

Ist topologische Sortierung verschieden von DFS nur dadurch, dass

• Bei Toplogical sortiert, wird die Verarbeitung (mit einem Ausgang Zugabe Stack) des aktuellen Elements erfolgt nach rekursivem Aufruf, während
• Im Fall von DFS wird das aktuelle Element vor dem rekursiven Aufruf verarbeitet (dh gedruckt oder hinzugefügt, um eine Ausgabewarteschlange)?

Dies ist mein Code für DFS

public void depthfirstsearchrecursive() 
    { 
     for(int i = 0;i<vertices.size();i++) 
     { 
      if(vertices.get(i).isVisited == false) 
      { 
       vertices.get(i).isVisited = true; 
       System.out.println(vertices.get(i).name + " "); 
       depthfirstsearchrecursiveUtil(vertices.get(i)); 
      } 
     } 
    } 
    public void depthfirstsearchrecursiveUtil(Vertex v) 
    { 
     for(int i = 0;i<v.neighbors.size();i++) 
     { 
      if(v.neighbors.get(i).isVisited == false) 
      { 
       v.neighbors.get(i).isVisited = true; 
       System.out.println(v.neighbors.get(i).name + " "); 
       depthfirstsearchrecursiveUtil(v.neighbors.get(i)); 
      } 
     } 
    } 

Wie Sie sehen können, habe ich das Element zuerst drucken, dann, den rekursiven Anruf.

Dies ist meine topologische Sortierung Umsetzung

/* topological sort recursive */ 
    public void topologicalsortrecursive() 
    { 
     Stack<Vertex> output = new Stack<Vertex>(); 
     for(int i = 0;i<vertices.size();i++) 
     { 
      if(vertices.get(i).isVisited == false) 
      { 
       vertices.get(i).isVisited = true; 
       topologicalsortrecursiveDriver(vertices.get(i), output); 

//    System.out.println(vertices.get(i).name + " "); 
       output.push(vertices.get(i)); 
      } 
     } 
    } 
    public void topologicalsortrecursiveDriver(Vertex v, Stack<Vertex> output) 
    { 
     for(int i = 0;i<v.neighbors.size();i++) 
     { 
      if(v.neighbors.get(i).isVisited == false) 
      { 
       v.neighbors.get(i).isVisited = true; 
       topologicalsortrecursiveDriver(v.neighbors.get(i), output); 

//    System.out.println(v.neighbors.get(i).name + " "); 
       output.push(v.neighbors.get(i)); 
      } 
     } 
    } 

Hier wird die Verarbeitung (in einen Stapel schieben, erfolgt nach der rekursive Aufruf gemacht wird)

Ist es wahr, dass zu sagen,

• DFS wie ein Vorordnungsdurchquerung sind, wo wir das Element verarbeiten, dann geht es Kinder, während
• Topologische Art ist wie ein umgekehrter Beitrag Order Traversal, wo wir an Kinder zuerst und dann das aktuelle Element verarbeiten, durch sie auf einen Stapel schieben, (das ist, warum ich sagte Reverse Postorder)

Answer 1

Nicht genau. DFS ist die generische Form. Sie können damit eine Vor- und/oder Nachbestellung durchführen.

Topologische Sortierung erfordert eine Post-Evaluation DFS.

Betrachten Sie den folgenden Code ein:

void DFS(Vertex v) { 
    if (v.hasVisited) 
    return; 
    v.hasVisited = true; 
    doBeforeDepth(v) 
    for (Vertex u : v.neighbours) 
    DFS(u); 
    doAfterDepth(v); 
} 

void DFS() 
{ 
    for (Vertex v : vertices) 
     DFS(v); 
} 

Sie können diese DFS-Code verwenden topologische Sortierung.