改善/优化我的糟糕代码的指南是Scala中的图二分法 [英] Guide to improve/optimize my terrible code for is graph bipartite in scala
本文介绍了改善/优化我的糟糕代码的指南是Scala中的图二分法的处理方法,对大家解决问题具有一定的参考价值,需要的朋友们下面随着小编来一起学习吧!
问题描述
我为> https://leetcode.com/problems/is-graph编写了此代码-bipartite/它可以工作,但是我认为代码很糟糕.问题:
I wrote this code for https://leetcode.com/problems/is-graph-bipartite/ It works but I think the code is terrible. Issues:
- 当我发现isBipartite = false时我该如何休息
- 对于未访问的g.key,如何仅对它们进行dfs(如果图形是二部图,则查找).(当有2个图未相互连接时)
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()
}
}
推荐答案
我想出了一个更好的解决方案
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
}
}
这篇关于改善/优化我的糟糕代码的指南是Scala中的图二分法的文章就介绍到这了,希望我们推荐的答案对大家有所帮助,也希望大家多多支持IT屋!
查看全文