Breadth-first, Depth-first searches (BFS/DFS)

Breadth-first search (BFS)

BFS is a traversing algorithm that starts at the tree root and explores all nodes at the present depth prior to moving on to the nodes at the next depth level. Extra memory is needed to keep track of the child nodes that were encountered but not yet explored.

 

The traversing process is as follows:

Pseudocode

BFS(G, root) is
	let Q be a queue
    label root as explored
    Q.enqueue(root) // insert a tree root in queue until every neighbour vertices are marked
    while Q is not empty do:
    	v := Q.dequeue() // remove a to-be-visited vertex from queue
        if v is the goal then
        	return v
        for all edges from v to w in G.adjacentEdges(v) do:
        	if w is not labelled as explored then
            	label w as explored
                Q.enqueue(w) // store w in Q if it's not visited
        end for
    end while
end

 

Depth-first search (DFS)

DFS is a traversing algorithm that starts at the root node (selecting some arbitrary node as the root node in the case of a graph) and explores as far as possible along each branch before backtracking.

 

The traversing process is as follows:

Pseudocode

DFS(G,v) // v is the vertex where the search starts
	Stack S := {}; // start with an empty stack
    for each vertex u, set visited[u] := false
    	push S, v;
        while S is not empty do:
        	u := pop S;
            if u is not visited then
            	visited[u] := true;
                for each unvisited neighbout w of u
                	push S, w;
                end for
         end while
     end for
end

 

Example

The number of vertices: 4

The number of edges: 5

Start node: 1

#include <iostream>
#include <queue>

#define MAX_VAL 1001

int N, M, V;
int mat[MAX_VAL][MAX_VAL];
bool visited[MAX_VAL];

using namespace std;
void dfs(int v)
{
    printf("%d, ", v);
    visited[v] = true;
    for (int i = 1; i <= N; i++)
    {
        if (visited[i] || mat[v][i] == 0)
            continue;
        dfs(i);
    }
}

void bfs(int v)
{
    queue<int> q;
    q.push(v);
    visited[v] = true;
    while (!q.empty())
    {
        v = q.front();
        printf("%d, ", q.front());
        q.pop();
        for (int i = 1; i <= N; i++)
        {
            if (visited[i] || mat[v][i] == 0)
                continue;
            q.push(i);
            visited[i] = true;
        }
    }
}

int main()
{
    int x, y;
    cin >> N >> M >> V;
    for (int i = 0; i < M; i++)
    {
        cin >> x >> y;
        mat[x][y] = mat[y][x] = 1;
    }
    memset(visited, false, sizeof(visited));
    dfs(V);
    prinft("\n");
    memset(visited, false, sizeof(visited));
    bfs(V);
}

 

Complexity

	BFS	DFS
Time	O(|V| + |E|)	O(|V| + |E|)
Space	O(|V|)	O(|V|)

• |V| is the number of vertices
• |E| is the number of edges