Dynamic Connectivity

by João Vitor Scheuermann

JavaScript

class Base {
	constructor (n) {
  	function initializeObject (n) {
    	let obj = {}
      
      for (let i = 0; i < n; i++) obj[i] = i
      
      return obj
    }
  
  
  	this.ids = initializeObject(n)
	}
  
  union (a, b) {
  }
  
  connected (a, b) {
  }
}


class QuickFind {
	constructor (n) {
  	function initializeObject (n) {
    	let obj = {}
      
      for (let i = 0; i < n; i++) obj[i] = i
      
      return obj
    }
  
  
  	this.ids = initializeObject(n)
	}
  
  union (a, b) {
  	let id = this.ids[b]
    let oldId = this.ids[a]
    
    for (let key in this.ids) 
    	this.ids[key] = this.ids[key] === oldId ? id : this.ids[key]
  }
  
  connected (a, b) {
  	return this.ids.hasOwnProperty(a) && this.ids.hasOwnProperty(b) ? this.ids[a] === this.ids[b] : false
  }
}

/* let qf = new QuickFind(10)

qf.union(4, 5)
qf.union(5, 7)
qf.union(1, 2)
qf.union(7, 2)
qf.union(2, 8)
qf.union(3, 6)

console.log(qf.ids, qf.connected(8, 4)) */


class QuickUnion extends Base {
	constructor (n) {
  	super(n)
  }
  
  /*_root (id) {
 	    while (id !== this.ids[id]) id = this.ids[id]
 	    return id
 	  } */
  
  // Implementar recursividade asyncrona, ou usar um web worker para nao bloquear o navegador de renderizar.
  _root (id) {
    while (id !== this.ids[id]) {
    	/* this.ids[id] = this.ids[this.ids[id]]; */
      id = this.ids[id]
    }
    return id
  }
  
  union (parent, child) {
  	let idA = this._root(parent)
    let idB = this._root(child)
    this.ids[idB] = idA
  }
  
  connected (a, b) {
  	return this._root(a) === this._root(b)
  }
}

/* const qu = new QuickUnion(10)

qu.union(3, 4)
qu.union(3, 8) */

/* console.log(qu.ids) */


class WheightedQuickUnion {
	constructor (n) {
		function initializeObject (n) {
    	let obj = {}
      
      for (let i = 0; i < n; i++) obj[i] = { parent: i, size: 1 }

      return obj
    }
  
  
  	this.ids = initializeObject(n)
  }

  _root (id) {
    while (id !== this.ids[id].parent) {
    	this.ids[id].parent...