Matemáticas Discretas

Un árbol T es un árbol de expansión de un grafo G si T es un subgrafo que contiene a todos los vértices de G.

BFS DFS

Búsqueda a lo ancho Búsqueda en profundidad

Un árbol de expansión mínimo de G es un árbol de expansión con mínimo peso.

Peso: 20 Peso: 12

Determina un árbol de expansión mínimo en un grafo conectado ponderado.

Entrada: un grafo conectado ponderado. Salida: Conjunto de arcos en un árbol de

expansión mínimo.