连通算法-Scala实现《算法》第一章(QuickFind)

需要得知两个物件是否已经被连接起来是现实生活中经常遇到的问题，比如复杂电路板上的两个原件是否是连通的，再引申一下，迷宫的两个出口是否可以形成一条路径，也可以归属此问题。下面将使用一维数组来简化解释该算法

有0-9个数在一维数组的0-9个位置上依次排列，现在要将第2位和第5位进行连接，我们称第2位为连接者，第5位为被连接者，同时我们定义，

当连接者和被连接者都是一个独立节点（即在数组中还没有重复的值存在），使用连接者去覆盖被连接者

可见，第5位也被改写成了数字2，于是第2位和第5位连通了起来。然后继续这一过程，将第5位再和第7位连接起来

继续连通第8位和第9位

再继续连通第7位和第8位

这样，当我们需要判定两点是否连通的时候，只需判断两者的值是否相等就可以了。下面将采用Scala来实现这一算法

package com.datacrafts.digitalevers.algorithm

class connectClass {

  val arr:Array[Int] = new Array[Int](10)
  for(i <- 0 to 9){
    arr(i) = i
  }

  /**
   * 连通两个节点
   * @param p  连接者为止
   * @param q  被连接者位置
   */
  def connect(p:Int,q:Int): Unit ={
     for(i <- 0 until  arr.length){
       if(arr(i) == arr(q)){
         arr(i) = arr(p)
       }
     }
  }

  /**
   * 测试两点是否连通
   * 连通为 true 否则为 false
   * @param p
   * @param q
   */
  def isconnect(p:Int,q:Int): Boolean ={
    if(arr(p) == arr(q)) true else false
  }
}

object connectClass{
  def main(args: Array[String]): Unit = {
    val cc = new connectClass
    cc.connect(1,3)
    cc.connect(3,5)
    println(cc.isconnect(1,5))
    println(cc.isconnect(1,6))
  }
}