algorithm - Guide to improve/optimize my terrible code for is graph bipartite in scala

Question

I wrote this code for https://leetcode.com/problems/is-graph-bipartite/ It works but I think the code is terrible. Issues:

1. How do I break when I find isBipartite=false
2. How do I only dfs(find if graph is bipartite) for g.keys which have not be visted. (when there are 2 graphs not connected to each other )

import scala.collection.immutable.Queue
case class Step(q: Queue[Int]=Queue(),visited: List[Int]=List(),colors: List[Int]=List(),isBipartite: Boolean = true)
object Solution {
    def isBipartite(graph: Array[Array[Int]]): Boolean = {
        val g= graph.foldLeft(Map[Int,List[Int]]())((mp,arr)=>{
            val i= graph.indexOf(arr)
             if(arr.isEmpty){
                 mp + (i->List())
}else
            arr.foldLeft(mp)((m,v)=>{
                m + (i->(m.getOrElse(i,Nil) :+ v))
            })
        })
        //println(g)
        val colors = List.fill(graph.size)(-1)
        //println(colors)
        g.keys.foldLeft(Step())((s,k)=>{
                if(!s.visited.contains(k) || s.isBipartite==true)
                bfs(k,g,s.copy(q=Queue(k),visited=(s.visited:+ k),colors=colors.updated(k,1)))
            else
                s.copy(isBipartite=false)
        
        }).isBipartite
    }
    
    
    def bfs(start: Int, g: Map[Int,List[Int]], step1: Step): Step = {
        
    val s=Stream.iterate(step1) {
      case (step) =>
        
        //dequeue
        val (vertex, rest)=step.q.dequeue
        val newS=g.getOrElse(vertex,Nil).foldLeft(step)((s,v)=>{
            //println("vertex color for vertex "+vertex+" "+s.colors(vertex))
             //println("v color "+s.colors(v))
            if(s.colors(vertex)==s.colors(v)){
                //println("is not bipartite")
                 step.copy(isBipartite=false)
            }else if(s.colors(v) == -1){
                 //println(s.colors)
                 s.copy(colors=s.colors.updated(v,(1-s.colors(vertex))))    
            }else{
                 s
            }                                       
        })
        //add neighbours to queue
       val newQueue=rest.enqueue(g.getOrElse(vertex,Nil).filterNot(newS.visited.contains))    
        //mark neighbours visited
       val newVisited: List[Int] = newS.visited ++ g.getOrElse(vertex,Nil)
            
        newS.copy(q=newQueue,visited=newVisited)
    }.takeWhile(t=> t.q.nonEmpty).filterNot(n=>n.isBipartite).headOption
       if(!s.isEmpty)
            s.get
        else
            Step()
   
  }
    
}

Answer 1

I came up with a little better solution

import scala.collection.immutable.Queue
case class Step(q: Queue[Int]=Queue(),colors: List[Int]=List(),isBipartite: Boolean = true)
object Solution {
    def isBipartite(graph: Array[Array[Int]]): Boolean = {
        //create a g
        val g= graph.foldLeft(Map[Int,List[Int]]())((mp,arr)=>{
            val i= graph.indexOf(arr)
             if(arr.isEmpty) mp + (i->List())
            else arr.foldLeft(mp)((m,v)=>m + (i->(m.getOrElse(i,Nil) :+ v)))
        })
        
        //init colors array
        val colors = List.fill(graph.size)(-1)
        
        //iterate over all g keys which are not processed
        g.keys.foldLeft(Step(Queue(),colors,true))((s,k)=>
                if(s.colors(k) == -1 || s.isBipartite==true){
                    bfs(k,g,s.copy(q=Queue(k),colors=s.colors.updated(k,1)))
                } else s
        ).isBipartite
    }
    
    //color of neighbors should be opposite of vertex to be bipartite
    def bfs(start: Int, g: Map[Int,List[Int]], step: Step): Step = {
        Stream.iterate(step) {
            case (step) =>
            val (vertex, rest)=step.q.dequeue
            g.getOrElse(vertex,Nil).foldLeft(step.copy(q=rest))((s,v)=>{
            if(!s.isBipartite)  s
            else if(s.colors(vertex)==s.colors(v)) s.copy(isBipartite=false)            
else if(s.colors(v) == -1) s.copy(q=s.q.enqueue(v),colors=s.colors.updated(v,(1-s.colors(vertex))))    
            else s                                      
        })  
    }.takeWhile(t=> t.q.nonEmpty).last
  }
    
}