13 Algoritmos básicos

Algoritmo:

Exploración en profundidad (otros dicen recorrido en profundidad, o depth first search, DFS)

Con el algoritmo DFS se obtiene un árbol con raíz $T$ y aristas de retroceso no pertenecientes a $T$. El algoritmo sirve entre otras cosas:

• determinar componentes conexas
• detectar puentes
• detectar vértices de corte
• detectar bloques
• ordenación topológica

Teorema:

Sea $T$ un árbol DFS de un grafo $G$ conexo y $v$ su raíz

$v$ es vértice de corte $\qquad\Longleftrightarrow\qquad$ $v$ tiene más de un hijo en $T$

Teorema:

Sea $T$ un árbol DFS de un grafo $G$ conexo y $v$ no sea la raíz

$v$ es vértice de corte $\qquad\Longleftrightarrow\qquad$ no existe una arista de retroceso desde el subárbol debajo de $v$ hacia un antecesor de $v$ en $T$

DFS tiene complejidad $\Theta(n+m)$ (asumiendo listas de adyacencias, ¿y con los demás?)

Algoritmo:

Exploración en anchura (otros dicen recorrido en anchura, o breadth first search, BFS)

Con el algoritmo de BFS se obtiene un árbol con raíz $T$, aristas de retroceso no pertenecientes a $T$, y aristas de cruce. El algoritmo sirve entre otras cosas:

• determinar caminos lo más cortos entre vertices
• ordenación topológica

BFS tiene complejidad $\Theta(n+m)$ (asumiendo listas de adyacencias, ¿y con los demás?)