Grafos 03 - Spanning tree

Un subgrafo $T=(V^{\prime},E^{\prime})$ de un grafo conexo $G=(V,E)$ es un spanning tree si:

1. $V^{\prime} = V$

2. $E^{\prime} \subseteq V$

3. $T$ es conexo y no tiene ciclos.

Existen varios algoritmos para determinar el minimum spanning tree de un grafo conexo ponderado.

KRUSKAL(G):
----------------------------
1. Sort all the edges of G in non-decreasing order of their weight.
2. T = empty graph
3. while T has less than V-1 edges:
4.   Pick the smallest edge from the sorted list. 
5.   Check if it would form a cycle T. 
6.   If cycle is not formed, include this edge in T.
7.   "Discard" edge from sorted list  

• Se puede lograr complejidad $O(|E| log|E| )$ al implementar el algoritmo de Kruskal:

  • El paso 1 se logra usando sort $O(|E| log|E| )$.
  • Para cada arista (en el peor de los casos |E|) debemos verificar si forma un ciclo con el resto de T. Esto se puede hacer de forma eficiente con una estructura union-find de forma que el total de pasos no excede complejidad $O(|E| log|E| )$.

• Idea general de union-find. Ver lab..

Ejercicios:

1. Accesa alguno de los grafos en https://visualgo.net/en/mst y determina su minimum spanning tree usando el algoritmo de Kruskal. Luego corre la simulación para validar tu respuesta.