Depth first search and Breadth first search between two nodes in graph

Question

I have an undirected connected graph. I have implemented it using an adjacency matrix which is a 2 dimensional array.

As I understand, a DFS visits children nodes before siblings. BFS visits siblings before children.

I implemented these two like this:

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

}

As it is these methods take only one parameter, the start vertex. What if I am asked to give the DFS and BFS from one node to a different node? Here is a simple example of a connected undirected graph. enter image description here

If I am asked to perform a DFS from D to E, would it be D,C,A,E or D,E. I thought DFS and BFS must visit every node, in this case B cannot be visited. I dont know how I should change my current methods to satisfy these requirements.

Justin Justin · Accepted Answer · 2013-11-25T02:17:21

I'm not sure it really matters if you visit C or E first. They are both children of D, right? It's implementation specific behavior, DFS doesn't define which child you visit first.

In DFS, if you pick child C first then you should visit A before you visit E.

In BFS, you should have visited both E and C before you visit A or B.

Depth first search and Breadth first search between two nodes in graph

1 Answers