There are two methods for visiting every node in a graph. If an undirected graph is connected, then a traversal that starts at any node can reach every node. If a directed graph is strongly connected, then a traversal that starts at any node can reach every node. Otherwise the traversal might reach every node (in a weakly connected digraph) or won't reach every node (in an unconnected undirected graph).
DFS follows a path as far as possible. When it is not possible to go forward, either because there is no successor or all successors have already been visited, the search backtracks. After backtracking the search tries to go forward on another path. Each time the search cannot go forward it backtracks and tries to go forward on a different path. To keep track of which nodes have been visited, a node is marked when it is visited. Once a node is marked it will not be visited again. DFS is similar to the preorder traversal in trees.
There are two ways to backtrack, and thus two ways to implement DFS, with recursion or with a stack.
Recursive:
DFS(v) {
mark v as visited
for each unvisited vertex w adjacent to v {
DFS(v)
}
}
Iterative:
DFS(v) {
st.push(v)
mark v as visited
while (!st.isEmpty()) {
x = st.top()
if no unvisited vertices are adjacent to x {
st.pop()
else {
choose unvisited w adjacent to x
st.push(w)
mark w as visited
}
}
}
As stated above, DFS may not be able to visit every node. Therefore a driver program is necessary to restart the search if it stops before reaching every node.
DFSDriver {
for each vertex v {
if v is not visited
DFS(v)
}
}
The DFS driver pseudocode says "for each vertex v". Which vertex is chosen first? That depends on how the DFS is being used. If there is no reason to choose a particular vertex, then the DFS will start at the first vertex in the array of vertices (adjacency matrix) or the first vertex in the list of vertices (adjacency list).
The DFS pseudocode says "choose an unvisited vertex w adjacent to v". This means follow an edge from the current vertex v to the vertex w at the other end of the edge. Which edge is chosen? There is no predetermined order for choosing the next edge; every edge will eventually be chosen. Therefore, the easiest choice is taken. In the adjacency matrix this means choose the next edge in the row of edges for vertex v. In the adjacency list this means choose the next edge in the list of edges for vertex v.
Often when we practice DFS and BFS from a picture, where we don't have the actual data structure, we visit the nodes in alphabetical or numeric order. So whenever we have a choice, we choose the vertex whose element is "least". That's how we proceeded in the following examples.
Starting the DFS at A, visit A -> B -> C, backtrack to B, visit E -> F, backtrack to A, visit D -> G -> H.
Starting the DFS at A, visit A -> B -> F ->G -> C, backtrack to F, visit I -> H, backtrack to A, visit D, backtrack to A, visit E.
BFS fans out by visiting all neighbors, then visiting their neighbors, and continuing in that manner. Similar to DFS, a node is marked when it is visited. Once a node is marked it will not be visited again.
BFS is implemented with a queue to hold the nodes whose neighbors still need to be visited.
BFS(v) {
q.insert(v)
mark v as visited
while (!q.isEmpty()) {
w = q.dequeue()
for each unvisited vertex u adjacent to w {
mark u as visited
q.enqeue(u)
}
}
}
As stated above, BFS may not be able to visit every node. Therefore a driver program is necessary to restart the search if it stops before reaching every node.
BFSDriver {
for each vertex v {
if v is not visited
BFS(v)
}
}
The BFS driver pseudocode says "for each vertex v". Which vertex is chosen first? Just as in the DFS, that depends on how the BFS is being used. If there is no reason to choose a particular vertex, then the BFS will start at the first vertex in the array of vertices (adjacency matrix) or the first vertex in the list of vertices (adjacency list).
The BFS pseudocode says "for each unvisited vertex u adjacent to w". This means we have a loop, and each time through the loop we follow an edge from the current vertex w to the vertex u at the other end of the edge. There is no predetermined order for choosing the edges. Therefore, the easiest choice is taken. In the adjacency matrix this means choose the next edge in the row of edges for vertex v. In the adjacency list this means choose the next edge in the list of edges for vertex v.
Starting the BFS at A, visit A -> B -> D -> C -> E -> G -> H -> F.
Starting the BFS at A, visit A -> B -> D -> E -> F -> C -> H -> G -> I.
Show the order in which the vertices will be visited in a DFS and a BFS of the following graph. When you have a choice, visit the vertices in alphabetical order.
Both DFS and BFS scan all vertices and edges, but they scan them in different order. We need to count each time we go to a vertex: either to visit the vertex or to check whether it has been visited. We visit each vertex once. We check whether the vertex has been visited once for each edge into the vertex: we must follow each edge to see if the vertex has been visited yet. The first time it hasn't been visited, the rest of the times it has been visited. This is the degree of the vertex - the number of edges incident to the vertex. So the total number of times we check nodes (for the whole graph) is the total degree of all nodes. For an undirected graph each edge is incident to two nodes; for a directed graph each edge is incident to one node. Thus for a graph with n nodes and e edges we have:
undirected: n visits + 2e checks = O(n + e)
directed: n visits + e checks = O(n + e)
Email Me |
Office Hours |
My Home Page |
Department Home |
MCC Home Page
© Copyright Emmi Schatz 2017