UndirectedGraph for demo

UndirectedGraph

package rel

import scala.collection.mutable.ListBuffer

case class Graph(adj: Array[ListBuffer[Int]])

object GraphBuild {

  def apply(size: Int, data: (Int,Int) *) = {
    val vertexs = new Array[ListBuffer[Int]](size)
    (0 to size - 1).foreach(i => vertexs(i) = new ListBuffer[Int])

    data.foreach{ v =>
       vertexs(v._1) += v._2
       vertexs(v._2) += v._1
     }
    Graph(vertexs)
  }

}

object UndirectedGraph {

  val g = GraphBuild(7,(0,5),(4,3),(0,1),(6,4),(5,4),(0,2),(0,6),(5,3))
  val size = g.adj.length

  def dfs() = {

    val marked = new Array[Boolean](size)
    val edgeTo = new Array[Int](size)

    def dfs(v: Int) {
      marked(v) = true
      g.adj(v).foreach{ w =>
        if(!marked(w)){
          dfs(w)
          edgeTo(w) = v
        }
      }
    }

    dfs(0)
    edgeTo
  }

  def bfs(s: Int = 0) = {

    val marked = new Array[Boolean](size)
    val edgeTo = new Array[Int](size)
    val q = new scala.collection.mutable.Queue[Int]

    q.enqueue(s)
    marked(s) = true
    while(!q.isEmpty) {
      val v = q.dequeue()
      g.adj(v).foreach{ w =>
        if(!marked(w)){
          q.enqueue(w)
          marked(w) = true
          edgeTo(w) = v
        }
      }
    }
    edgeTo
  }

}


object UndirectedGraphDemo extends App {

  println("DFS:")
  val dfsEdge = UndirectedGraph.dfs()
  (0 to dfsEdge.length - 1).foreach{i =>
      println(i + "-" + dfsEdge(i))
  }

  println("BFS:")
  val bfsEdge = UndirectedGraph.bfs()
  (0 to bfsEdge.length - 1).foreach{i =>
    println(i + "-" + bfsEdge(i))
  }

}