Diferencia entre BFS y DFS

Los artículos escritos en este blog fueron creados con el objetivo de enseñar. Además, la información del artículo puede ser incorrecta, así que tenga cuidado.

Los métodos representativos para explorar un gráfico incluyen BFS y DFS. Ambos siguen vértices no visitados, pero en diferente orden.

BFS

La búsqueda en amplitud busca ampliamente comenzando desde el vértice más cercano al punto de partida. Utilice cola.

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

Si todas las aristas tienen el mismo costo, BFS puede encontrar la ruta con la menor cantidad de aristas desde el punto de partida.

DFS

La búsqueda en profundidad primero recorre todo un camino y luego regresa. Utilice llamadas recursivas o Stack.

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

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

A menudo se utiliza en elementos de conexión, detección de ciclos y estructuras de seguimiento. Si el gráfico es muy profundo, la pila recursiva puede desbordarse, así que considere implementar una pila explícita.

BFS no es necesariamente mejor o DFS no es necesariamente más rápido. Su elección depende de si necesita una respuesta precisa, si necesita probar la ruta en profundidad y cuál es su memoria y profundidad de gráficos.