Algoritmo Quick Find

El curso de coursera “Algorithms, Part I” me vino excelente ya que este año quería mejorar mis conocimientos en algoritmos. El curso es totalmente gratuito y los vídeos son de altísimo nivel, muy recomendado.

La primera semana introduce un par de algoritmos de conectividad dinámica, son Quick Find y Quick Union. Estos algoritmos permiten conectar y verificar la conexión que existe entre nodos de una estructura de tipo Árbol, representada en un Array. Primero escribiré sobre Quick Find y en otro post sobre Quick Union, para no hacer los posts tan largos.

Quick Find

El algoritmo se basa en 2 funciones principales, Union y Find, Union permite conectar 2 nodos y Find permite verificar si dos nodos están conectados, directa o indirectamente, es decir a través de otros nodos.

Union

La unión permite conectar 2 nodos, la lógica es simple (complejidad O(n)), se basa en recorrer todo el arreglo dentro de un ciclo y establecer como raíz al nodo2 en todos los nodos que tengan como raíz al nodo1, para ello basta con verificar en cada paso si arreglo[i] == arreglo[nodo1], de ser verdadero, sustituir arreglo[i] con el valor del arreglo[nodo2]. De manera tal que todos tengan el mismo nodo raíz, en Pseudopython sería:

def union(int []array, int node1, int node2):
    temp = array[node1]
    for i to len(array):
        if array[i] == temp:
            array[i] = array[node2]

Find

Con find se verifica si dos nodos están conectados y es una operación muy rápida, O(1), creo que por eso el nombre del algoritmo “Quick Find”, basta con verificar si los nodos tienen comparten la misma raíz arreglo[nodo1]==arreglo[nodo2]

 
  Imagen tomada de uno de los vídeos del curso en Coursera

Por ejemplo, en la imagen los nodos 0 5 y 6 están conectados. En el arreglo el valor en la posición id[0] id[5] e id[6] es 0 ya que el id 0 es algo así como el nodo raíz y la forma de verificar si están conectados es que todos tengan el mismo valor.

Dejo mi intento de implementar Quick Find en C#, muy parecido a la versión Java del curso, pero que imprime el arreglo  y el índice para visualizar mejor el resultado del algoritmo.

	using System;
	using System.Text;
	namespace QuickFind
	{
	class Program
	{
	static void Main(string[] args)
	{
	QuickFind quickFind = new QuickFind(9);
	quickFind.Union(4, 3);
	quickFind.Union(3, 8);
	quickFind.Union(6, 5);
	quickFind.Union(9, 4);
	Console.WriteLine(quickFind.Find(3, 9));
	Console.WriteLine(quickFind);
	}
	}
	/// <summary>
	/// Quickfind more info at https://www.cs.princeton.edu/~rs/AlgsDS07/01UnionFind.pdf
	/// </summary>
	public class QuickFind
	{
	private int[] _array;
	//Initialize the array: O(n)
	public QuickFind(int size)
	{
	_array = new int[size + 1];
	for (int i = 0; i < size + 1; i++)
	{
	_array[i] = i;
	}
	}
	//Find: O(1)
	public bool Find(int a, int b)
	{
	return _array[a] == _array[b];
	}
	/// <summary>
	/// Union: O(n)
	/// </summary>
	public void Union(int a, int b)
	{
	int temp = _array[a];
	for (int i = 0; i < _array.Length; i++)
	{
	if (_array[i] == temp)
	{
	_array[i] = _array[b];
	}
	}
	}
	#region Pretty print of the array and the indexes
	/// <summary>
	/// Pretty print of the array and the indexes
	/// </summary>
	public override string ToString()
	{
	StringBuilder result = new StringBuilder("i:\t");
	for (int i = 0; i < _array.Length; i++)
	{
	result.AppendFormat("{0}, ", i);
	}
	result.Append("\nid[i]:\t");
	foreach (int item in _array)
	{
	result.AppendFormat("{0}, ", item);
	}
	return result.ToString();
	}
	#endregion
	}
	}

view raw QuickFind.cs hosted with ❤ by GitHub

Salida
True
i:         0, 1, 2, 3, 4, 5, 6, 7, 8, 9
id[i]:  0, 1, 2, 8, 8, 5, 5, 7, 8, 8

Referencias:
Algorithms, Part I

https://www.cs.princeton.edu/~rs/AlgsDS07/01UnionFind.pdf