Minimum spanning trees (MST) & Floodfill

Algoritmo de Kruskal para Minimum spanning trees (MST)

En el algoritmo de Kruskal, el spanning tree inicial solo contiene los nodos del grafo y no contiene ninguna arista (vertices). Luego, el algoritmo recorre las aristas ordenadas por sus pesos y siempre agrega una arista al árbol si no crea un ciclo. El algoritmo mantiene los componentes del árbol. Inicialmente, cada nodo del grafo pertenece a un componente separado. Siempre que se agrega una arista al árbol, se unen dos componentes. Finalmente, todos los nodos pertenecen al mismo componente y se ha encontrado un árbol de expansión mínimo (Minimum spanning tree).

Ahora apliquemos el algoritmo a este grafo:

El grafo contiene 9 vértices y 14 aristas. Por lo tanto, el árbol de expansión mínima formado tendrá (9 - 1) = 8 aristas. Después de ordenar queda como:

Ahora selecciona todas las aristas una por una de la lista ordenada de aristas.

Implementacion

Floodfill

es un algoritmo que identifica y etiqueta el componente conectado al que pertenece una celda en particular, en una matriz multidimensional. Básicamente, es DFS o BFS, pero en una cuadrícula, y queremos encontrar el componente conectado de todas las celdas conectadas con el mismo número.

Implementacion con BFS

Problemas

• 472D Design Tutorial: Inverse the Problem
• 1365D Solve The Maze

Referencias

• Choudhary, A. (2024). Flood Fill Algorithm. Recuperado de https://www.geeksforgeeks.org/flood-fill-algorithm/
• GeeksforGeeks. Kruskal’s Minimum Spanning Tree (MST) Algorithm. Recuperado de https://www.geeksforgeeks.org/kruskals-minimum-spanning-tree-algorithm-greedy-algo-2/
• Inside Code.(2021). This is how Paint's bucket fill works (Flood fill algorithm) [video]. Recuperado de https://youtu.be/VuiXOc81UDM?si=cWO6C1N8-eVAbNxt
• Laaksonen, A. (2018). Competitive Programmer’s Handbook. Recuperado de https://cses.fi/book/book.pdf
• Michael Sambol. (2012). Kruskal's Algorithm in 2 minuts [video]. Recuperado de https://youtu.be/71UQH7Pr9kU?si=xjBdbCXTxw-fMO6A
• Qi,B. et al. (s.f.). Minimum Spanning Trees. Recuperado de https://usaco.guide/gold/mst?lang=cpp
• Yao, D. (2020). AN INTRODUCTION TO THE USA COMPUTING OLYMPIAD. Recuperado de https://darrenyao.com/usacobook/cpp.pdf
• Yao, D. (s.f.) Flood Fill. Recuperado de https://usaco.guide/silver/flood-fill?lang=cpp