java - 图中两个节点之间的深度优先搜索和广度优先搜索

Question

我有一个无向连通图。我使用邻接矩阵来实现它，它是一个二维数组。

据我了解，DFS 在访问兄弟节点之前访问子节点。 BFS 在 child 之前拜访 sibling 。

我这样实现了这两个:

    public void DFT(int firstVertex) {
    connectedVertices = 0;
    int v;
    Stack<Integer> stack = new Stack<Integer>();
    for (int i = 0; i < numVertices; i++) {
        if(vertex[i] != null){
            vertex[i].setPushed(false);
        }
    }
    stack.push(firstVertex);
    connectedVertices++;
    vertex[firstVertex].setPushed(true);

    while(!stack.isEmpty()){
        v = stack.pop();
        vertex[v].visit();
        for (int i = 0; i < numVertices; i++) {
            if(adj[v][i] != 0 && !vertex[i].getPushed()){
                stack.push(i);
                connectedVertices++;
                vertex[i].setPushed(true);
            }   
        }
    }

}

public void BFT(int firstVertex) {
    connectedVertices = 0;
    int v;
    Queue<Integer> queue = new LinkedList<Integer>();
    for (int i = 0; i < numVertices; i++) {
        if(vertex[i] != null){
            vertex[i].setPushed(false);
        }
    }
    queue.add(firstVertex);
    connectedVertices++;
    vertex[firstVertex].setPushed(true);

    while(!queue.isEmpty()){
        v = queue.remove();
        vertex[v].visit();
        for (int i = 0; i < numVertices; i++) {
            if(adj[v][i] != 0 && !vertex[i].getPushed()){
                queue.add(i);
                connectedVertices++;
                vertex[i].setPushed(true);
            }   
        }
    }

}

因为这些方法只采用一个参数，即起始顶点。如果我被要求将 DFS 和 BFS 从一个节点提供给另一节点怎么办？这是一个连接无向图的简单示例。

如果要求我执行从 D 到 E 的 DFS，会是 D,C,A,E 还是 D,E。我认为DFS和BFS必须访问每个节点，这样的话B就无法访问。我不知道应该如何改变当前的方法来满足这些要求。

Answer 1

我不确定您先访问 C 还是 E 是否真的重要。他们都是D的 child 吧？这是特定于实现的行为，DFS 不定义您首先访问哪个 child 。

在 DFS 中，如果您先选择子 C，那么您应该在访问 E 之前访问 A。

在 BFS 中，您应该在访问 A 或 B 之前访问过 E 和 C。