Difference between BFS and DFS

The articles written on this blog were created with the goal of teaching. Also, the information in the article may be incorrect, so please be careful.

Representative methods for exploring a graph include BFS and DFS. Both follow unvisited vertices, but in different order.

BFS

Breadth-First Search searches widely starting from the vertex closest to the starting point. Use Queue.

std::queue<int> Open;
std::vector<bool> Visited(NodeCount, false);

Open.push(Start);
Visited[Start] = true;

while (!Open.empty())
{
    const int Current = Open.front();
    Open.pop();

    for (int Next : Graph[Current])
    {
        if (!Visited[Next])
        {
            Visited[Next] = true;
            Open.push(Next);
        }
    }
}

If all edges have the same cost, BFS can find the path with the fewest edges from the starting point.

DFS

Depth-First Search goes all the way down a path and then returns. Use recursive calls or Stack.

void DFS(int Current)
{
    Visited[Current] = true;

    for (int Next : Graph[Current])
    {
        if (!Visited[Next])
        {
            DFS(Next);
        }
    }
}

It is often used in connection elements, cycle detection, and backtracking structures. If the graph is very deep, the recursive Stack may overflow, so consider implementing an explicit Stack.

BFS is not necessarily better or DFS is not necessarily faster. Your choice depends on whether you need a close answer, whether you need to test the path deeply, and what your memory and graph depth is.