数据结构图的遍历

对于不同的跳转都有其对应出度或入度,遍历所有路径

代码

object GraphDemo {
  // 边
  var edgeSet: Set[String] = Set[String]()
  // 节点对应出度
  var nodeMap: scala.collection.mutable.Map[String, Seq[String]] = scala.collection.mutable.Map[String, Seq[String]]()

  /**
   * 生成节点对应出度信息
   * @param list
   */
  def generate(list: List[String]): Unit = {
    list.map(x => {
      val kv = x.split("->")
      var value: Seq[String] = nodeMap.getOrElse(kv(0), Seq[String]())
      value = value :+ kv(1)
      nodeMap.put(kv(0),value)
    })
  }

  /**
   * 输出指定节点到叶子节点的所有路径
   * @param root
   * @param path
   */
  def dis(root: String, path: String): Unit = {
    val nodes = nodeMap.getOrElse(root, Seq[String]())
    nodes.foreach(x => {
      val temp = path + x
      dis(x, temp)
    })
    if(nodes.isEmpty){
      println(path)
    }
  }

  def main(args: Array[String]): Unit = {
    val list = List("a->b", "c->d", "c->e", "b->c", "e->f")
    generate(list)
    println(nodeMap)
    // Map(e -> List(f), b -> List(c), a -> List(b), c -> List(d, e))
    dis("a", "a")
    // abcd
    // abcef
  }
}

---

处理逻辑

1.将所有边进行拆解,可以得到上游与下游的关系
2.对指定节点开始进行递归处理,直到节点没有下游节点为之
3.在没有下游节点时输出

---

注意

只适合DAG,如果出现环的情况下,该逻辑会有问题