修改深度优先搜索

Question

（源，目标）和它的类型（树，后，前进，交叉）？

Answer 1

你去吧。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);
    }
}

Answer 2

好问题。

这是基于您作为评论发布的来源的解决方案。重要提示：开始/结束表上有一个错误，第三行第三列应该是"end[u] <end[v]"而不是"end[u]> end[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"
        }
    }