est une sorte topologiques différent de DFS uniquement dans ce que le traitement de l'élément en cours est effectué après appel récursif

Question

est un peu topologiques différent de DFS seulement que,

• En cas de tri Toplogical, le traitement (Ajoutant à une sortie pile) de l'élément courant est effectué après appel récursif, alors que
• Dans le cas de DFS, l'élément en cours est traité (c'est-à-dire, imprimé ou ajouté à une file d'attente de sortie) avant l'appel récursif?

Ceci est mon code pour 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)); 
      } 
     } 
    } 

Comme vous pouvez le voir, imprimer l'élément premier, puis, faire l'appel récursif.

Ceci est ma mise en œuvre de tri topologiques

/* 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)); 
      } 
     } 
    } 

Ici, le traitement (en poussant dans une pile, se fait après l'appel récursif est fait)

Est-il vrai de dire que,

• DFS est comme un parcours de l'où nous traitons l'élément, puis aller à c'est des enfants, alors que,
• tri topologique est comme un ordre inverse après traversal, où nous allons aux enfants d'abord, et traiter ensuite l'élément courant, en poussant les à une pile, (ce qui est la raison pour laquelle je l'ai dit inverse Postorder)

Answer 1

Pas exactement. DFS est la forme générique. Vous pouvez l'utiliser pour implémenter une évaluation pré et/ou post-commande.

Le tri topologique nécessite une évaluation DFS post-évaluation.

Consultez le code suivant:

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); 
} 

Vous pouvez utiliser ce code pour effectuer DFS tri topologique.