내 끔찍한 코드를 개선 / 최적화하는 가이드는 스칼라의 그래프 이분법입니다.
Nov 13 2020
이 코드를 작성했습니다. https://leetcode.com/problems/is-graph-bipartite/작동하지만 코드가 끔찍하다고 생각합니다. 문제 :
- isBipartite = false를 찾으면 어떻게 중단합니까?
- visted하지 않은 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()
}
}
답변
DhavalKolapkar Nov 13 2020 at 20:18
나는 조금 더 나은 해결책을 생각해 냈습니다.
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
}
}