How can we use Depth First Search to check whether 2 vertices are connected or not?

Question

I am unable to understand how dfs can be used to check whether two vertices in a graph are connected or not( not only directly connected but can also be indirectly connected).

Answer 1

Let the two vertices be source and destination. Without loss of generality, any of them could be source, and the other being destination. So the basic idea is, you do a dfs starting from the source node, and you keep an array to track the status of each node (i.e if they have been visited already or not). When no new node can be visited, the dfs will terminate. If the source and destination are indeed connected, then after running dfs from the source, the status of destination node in the visited array will either be visited (visited status can be represented by 1 or true) or not visited (0 or false). It will be 1 or true if they are connected and 0 otherwise. Not only does this work for the destination, but also all of the other nodes.

visited[n] --> n nodes, 0 to n - 1,  initialize with 0 or false values

dfs(source){
    visited[source] = true;
    for(node : adjacencyList[source]){
        if(!visited[node]){
            dfs(node);
        }
    }
}

connected(source){
    dfs(source);
    for(i = 0 ; i < n ; ++i){
        if(!visited[i]){
            // source and i are not connected
        }
    }
}