Estructuras de datos y algoritmos · Grafos

Árboles de expansión mínima

El conjunto de aristas más barato que conecta todos los vértices sin ciclos.

Empezar una lección sobre Árboles de expansión mínima

Aprende antes

• Union-find: Una estructura que rastrea qué elementos pertenecen al mismo grupo y fusiona grupos rápidamente.
• Montículos y colas de prioridad: Una estructura en forma de árbol que siempre mantiene fácil de encontrar el elemento más pequeño, o el más grande.

Lleva a

• Algoritmos voraces: Tomar la mejor decisión local en cada paso confiando en que lleva a la mejor respuesta global.

Temas relacionados

• Algoritmo de Dijkstra: Encontrar el camino más barato desde un vértice hacia todos los demás cuando ningún peso de arista es negativo.
• Algoritmos voraces: Tomar la mejor decisión local en cada paso confiando en que lleva a la mejor respuesta global.