Scala使用不可变值替代var实现无向图有效路径存在性判断

问题背景 #

现有包含n个顶点的无向图，顶点标签为0到n-1（包含两端），图的边用二维整数数组edges表示，每个edges[i] = [ui, vi]代表顶点ui和vi之间存在一条双向边，任意顶点对之间最多有一条边，不存在顶点指向自身的边。
要求判断从顶点start到顶点end是否存在有效路径，给定edges、整数n、start、end，若存在有效路径返回true，否则返回false。

示例1 #

输入：n = 3, edges = [[0,1],[1,2],[2,0]], start = 0, end = 2
输出：true
解释：从顶点0到顶点2存在两条路径：

• 0 → 1 → 2
• 0 → 2

原有可变实现代码 #

package com.example

object Solution {

  var visited: Seq[Int] = Nil

  def validPath(n: Int, edges: Array[Array[Int]], start: Int, end: Int) : Boolean ={

    if(edges.length == 0)
      return true
    val finalMap = edges.foldLeft(Map.empty[Int, Seq[Int]]) { case(result, edge) =>
      val keyVal = result.getOrElse(edge(0) , Nil) :+ edge(1)
      val updatedMap = (result + (edge(0)-> keyVal ))
      val keyVal1 = updatedMap.getOrElse(edge(1) , Nil) :+ edge(0)
      (updatedMap + (edge(1)-> keyVal1 ))
    }
    helper(finalMap , end, start)
  }

  def helper(map:Map[Int, Seq[Int]],  end: Int, start: Int): Boolean = {

    println(visited)
    if(visited.contains(start)) {
      false
    }
    else {
     val resultList =  map.get(start)
      resultList match {
        case Some(l) =>  if (l.contains(end)) {
          true
        } else {
          l.foldLeft(false) {(a , b) =>
            visited = (visited :+ start).distinct
            a || helper(map, end, b)
          }
        }
        case None => false
      }
    }
  }

  def main(args: Array[String]): Unit = {
//    val input =   Array(Array(3,12),Array(26,84),Array(10,43),Array(68,47),Array(33,10),Array(87,35),Array(41,96),Array(70,92),Array(38,31),Array(88,59),Array(7,30),Array(89,26),Array(95,25),Array(66,28),Array(14,24),Array(86,11),Array(83,65),Array(14,4),Array(67,7),Array(89,45),Array(52,73),Array(47,85),Array(86,53),Array(68,81),Array(43,68),Array(87,78),Array(94,49),Array(70,21),Array(11,82),Array(60,93),Array(22,32),Array(69,99),Array(7,1),Array(41,46),Array(73,94),Array(98,52),Array(68,0),Array(69,89),Array(37,72),Array(25,50),Array(72,78),Array(96,60),Array(73,95),Array(7,69),Array(97,19),Array(46,75),Array(8,38),Array(19,36),Array(64,41),Array(61,78),Array(97,14),Array(54,28),Array(6,18),Array(25,32),Array(34,77),Array(58,60),Array(17,63),Array(98,87),Array(13,76),Array(58,53),Array(81,74),Array(29,6),Array(37,5),Array(65,63),Array(89,56),Array(61,18),Array(23,34),Array(76,29),Array(73,76),Array(11,63),Array(98,0),Array(54,14),Array(63,7),Array(87,32),Array(79,57),Array(72,0),Array(94,16),Array(85,16),Array(12,91),Array(14,17),Array(30,45),Array(42,41),Array(82,69),Array(24,28),Array(31,59),Array(11,88),Array(41,89),Array(48,12),Array(92,76),Array(84,64),Array(19,64),Array(21,32),Array(30,19),Array(47,43),Array(45,27),Array(31,17),Array(53,36),Array(88,3),Array(83,7),Array(27,48),Array(13,6),Array(14,40),Array(90,28),Array(80,85),Array(29,79),Array(10,50),Array(56,86),Array(82,88),Array(11,99),Array(37,55),Array(62,2),Array(55,92),Array(51,53),Array(9,40),Array(65,97),Array(25,57),Array(7,96),Array(86,1),Array(39,93),Array(45,86),Array(40,90),Array(58,75),Array(99,86),Array(82,45),Array(5,81),Array(89,91),Array(15,83),Array(93,38),Array(3,93),Array(71,28),Array(11,97),Array(74,47),Array(64,96),Array(88,96),Array(4,99),Array(88,26),Array(0,55),Array(36,75),Array(26,24),Array(84,88),Array(58,40),Array(77,72),Array(58,48),Array(50,92),Array(62,68),Array(70,49),Array(41,71),Array(68,6),Array(64,91),Array(50,81),Array(35,44),Array(91,48),Array(21,37),Array(62,98),Array(64,26),Array(63,51),Array(77,55),Array(25,13),Array(60,41),Array(87,79),Array(75,17),Array(61,95),Array(30,82),Array(47,79),Array(28,7),Array(92,95),Array(91,59),Array(94,85),Array(24,65),Array(91,31),Array(3,9),Array(59,58),Array(70,43),Array(95,13),Array(30,96),Array(51,9),Array(16,70),Array(29,94),Array(37,22),Array(35,79),Array(14,90),Array(75,9),Array(2,57),Array(81,80),Array(61,87),Array(69,88),Array(98,79),Array(18,70),Array(82,19),Array(36,27),Array(49,62),Array(67,75),Array(62,77),Array(83,96),Array(92,37),Array(95,22),Array(46,97),Array(35,0),Array(44,79),Array(82,89),Array(68,94),Array(96,31),Array(92,34),Array(25,0),Array(46,36),Array(38,84),Array(21,0),Array(0,80),Array(72,44),Array(56,97),Array(86,26),Array(94,57),Array(25,6),Array(81,13),Array(66,63),Array(57,5),Array(72,49),Array(46,86),Array(95,16),Array(95,37),Array(14,89),Array(44,22),Array(60,39),Array(37,47),Array(58,86),Array(89,96),Array(38,83),Array(51,91),Array(72,70),Array(14,82),Array(60,30),Array(58,39),Array(57,22),Array(95,70),Array(44,76),Array(5,68),Array(15,69),Array(33,61),Array(81,32),Array(21,68),Array(73,20),Array(22,72),Array(83,8),Array(15,54),Array(93,42),Array(68,95),Array(55,72),Array(33,92),Array(5,49),Array(17,96),Array(44,77),Array(24,53),Array(2,98),Array(33,81),Array(32,43),Array(20,16),Array(67,84),Array(98,35),Array(58,11),Array(72,5),Array(3,59),Array(78,79),Array(6,0),Array(26,71),Array(96,97),Array(18,92),Array(1,36),Array(78,0),Array(63,15),Array(20,43),Array(32,73),Array(37,76),Array(73,16),Array(76,23),Array(50,44),Array(68,2),Array(14,86),Array(69,65),Array(95,98),Array(53,64),Array(6,76),Array(7,11),Array(14,84),Array(62,50),Array(83,58),Array(78,92),Array(37,0),Array(13,55),Array(12,86),Array(11,59),Array(41,86),Array(27,26),Array(94,43),Array(20,78),Array(0,73),Array(58,90),Array(69,36),Array(62,34),Array(65,26),Array(32,85))
   val input = Array(Array(0,4))
    val result  = Solution.validPath(5, input,0,4)
    println(result)

  }

}

修改思路 #

• 移除全局可变变量visited，将访问标记集合改为helper函数的入参，每次递归传递新生成的不可变访问集合
• 用Set替代Seq存储访问标记，contains查找时间复杂度为O(1)，性能更优
• 调整递归逻辑，每次访问新节点前先将当前节点加入访问集合，避免重复遍历
• 修复原代码边为空时的边界判断bug：原代码只要边为空就返回true，实际上只有start和end相等的时候才应该返回true

修改后的不可变实现代码 #

package com.example

object Solution {

  def validPath(n: Int, edges: Array[Array[Int]], start: Int, end: Int) : Boolean ={
    // 边界判断：起点终点相同直接返回true
    if(start == end) return true
    if(edges.isEmpty) return false

    // 构建邻接表逻辑不变，本身就是不可变操作
    val adjacencyMap = edges.foldLeft(Map.empty[Int, Seq[Int]]) { case(result, edge) =>
      val u = edge(0)
      val v = edge(1)
      val updatedU = result + (u -> (result.getOrElse(u, Nil) :+ v))
      updatedU + (v -> (updatedU.getOrElse(v, Nil) :+ u))
    }
    // 初始访问集合为空，调用helper
    helper(adjacencyMap, end, start, Set.empty[Int])
  }

  // 新增不可变Set类型的visited参数，替代全局var
  def helper(map: Map[Int, Seq[Int]], end: Int, current: Int, visited: Set[Int]): Boolean = {
    // 当前节点已访问过，直接返回false
    if(visited.contains(current)) return false
    // 拿到当前节点的邻居列表
    val neighbors = map.getOrElse(current, Nil)
    // 邻居里有终点直接返回true
    if(neighbors.contains(end)) return true
    // 把当前节点加入访问集合，递归遍历所有邻居，有一个返回true就整体为true
    val newVisited = visited + current
    neighbors.exists(neighbor => helper(map, end, neighbor, newVisited))
  }

  def main(args: Array[String]): Unit = {
    val input = Array(Array(0,4))
    val result  = Solution.validPath(5, input,0,4)
    println(result) // 输出true
    // 示例1测试
    val testEdges = Array(Array(0,1), Array(1,2), Array(2,0))
    println(Solution.validPath(3, testEdges, 0, 2)) // 输出true
  }
}

内容的提问来源于stack exchange，提问作者Krishhna