Ändern der Tiefensuche zuerst

Question

(Quelle, Ziel) und es ist Typ (Baum, zurück, vorwärts, Kreuz)?

Answer 1

Schöne Frage.

Dies ist die Lösung basierend auf the source you posted as comment. wichtig: Es ist ein Fehler auf dem Start/Ende-Tabelle sollte dritte Reihe dritte Spalte sein "end [u] < Ende [V]" anstelle von "end [u]> Ende [V]"

void main(G, s){ 
     for each node v in G{ 
      explored[v]=false 
      parent[v]=null 
      start[v]=end[v]=null 
     } 
     Global clock = 0 
     DFS(G, s, s) 
    } 

    void DFS(G, s, parent){ 
     explored[s] = true; 
     parent[s] = parent 

     start[s]=clock 
     clock++ 

     for each u=(s,v){ 
      if(explored[v] == false){ 
       DFS(G, v) 
      } 
      print (s + "-->" + v +"type: " + getType(s,v)) 
     } 

     end[s]=clock 
     clock++ 
    } 

    String getType(s, v){ 
     if(start[s]<start[v]){ 
      if(end[s]>end[v]) return "Tree edge" 
      else return "Forward edge" 
     else{ 
      if(end[s]<end[v]) return "Back edge" 
      else return "Cross edge" 
     } 
    } 

Answer 2

Hier gehts. Code in Java

import java.util.ArrayList; 
import java.util.List; 

class Node { 
    public String name; 
    public List<Node> connections = new ArrayList<>(); 
    boolean visited = false; 

    Node(String name) { 
     this.name = name; 
    } 
} 

class DFS { 
    // Main part. 
    public static void search(Node root) { 
     if (root == null) { 
      return; 
     } 
     root.visited = true; 
     for (Node node : root.connections) { 
      if (!node.visited) { 
       // Print result. 
       System.out.println(root.name + "->" + node.name); 
       search(node); 
      } 
     } 
    } 
} 

public class App { 

    public static void main(String[] args) { 
     Node a = new Node("a"); 
     Node b = new Node("b"); 
     Node c = new Node("c"); 
     Node d = new Node("d"); 
     Node e = new Node("e"); 

     a.connections.add(b); 

     b.connections.add(a); 
     b.connections.add(c); 
     b.connections.add(d); 

     c.connections.add(b); 
     c.connections.add(d); 

     d.connections.add(b); 
     d.connections.add(c); 
     d.connections.add(e); 

     DFS.search(d); 
    } 
}