在GraphX（Scala）中查找源顶点与目标顶点间的所有路径

嘿，看起来你想要拿到GraphX里两个顶点之间所有关联的顶点和边，思路是先找全路径再去重，这个方向完全没问题！我来给你捋捋怎么实现～

你现有的BFS代码只能拿到最短路径，但我们需要所有可能的路径，然后从这些路径里提取出所有不重复的顶点和边。这里我用DFS（深度优先搜索）来遍历所有路径，因为它更适合探索所有分支路径，避免遗漏。

第一步：实现全路径搜索函数 #

首先写一个DFS函数，遍历从源顶点到目标顶点的所有路径，同时记录已访问的顶点防止循环：

import org.apache.spark.graphx.{Graph, VertexId}

/**
 * 返回图中从src到dst的所有有向路径（顶点序列）
 */
def findAllPaths[VD, ED](graph: Graph[VD, ED], src: VertexId, dst: VertexId): List[List[VertexId]] = {
  // 先把图的邻接关系拉到本地（中小规模图适用）
  val adjacencyList = graph.collectNeighbors(org.apache.spark.graphx.EdgeDirection.Out).collectAsMap()

  // 递归DFS遍历路径
  def dfs(current: VertexId, visited: Set[VertexId], path: List[VertexId]): List[List[VertexId]] = {
    if (current == dst) {
      // 找到目标顶点，返回当前路径
      List(path :+ current)
    } else {
      // 遍历当前顶点的所有出边邻居，跳过已访问的节点
      adjacencyList.getOrElse(current, List.empty)
        .filter(!visited.contains(_))
        .flatMap(next => dfs(next, visited + current, path :+ current))
        .toList
    }
  }

  dfs(src, Set.empty, List.empty)
}

注意：如果你的图是无向图，把EdgeDirection.Out改成EdgeDirection.Either就行；如果是超大规模分布式图，这种把邻接表拉到Driver的方式可能性能不够，这时候可以考虑用Spark的Pregel API做分布式路径搜索。

第二步：提取去重后的顶点和边 #

拿到所有路径后，我们把里面的顶点和边都收集起来，然后去重：

/**
 * 从所有路径中提取唯一的顶点和边（包含边属性）
 */
def extractUniqueVerticesAndEdges[VD, ED](graph: Graph[VD, ED], paths: List[List[VertexId]]): (Set[VertexId], Set[(VertexId, VertexId, ED)]) = {
  // 提取所有不重复的顶点
  val uniqueVertices = paths.flatten.toSet

  // 先把边的(src,dst)->属性映射拉到本地
  val edgeAttrMap = graph.edges.map(e => ((e.srcId, e.dstId), e.attr)).collectAsMap()
  // 遍历每条路径的连续顶点对，提取对应的边
  val uniqueEdges = paths.flatMap { path =>
    path.sliding(2).map { case List(u, v) =>
      (u, v, edgeAttrMap((u, v)))
    }
  }.toSet

  (uniqueVertices, uniqueEdges)
}

第三步：整合使用示例 #

把上面的函数串起来用，比如你的图已经创建好了：

// 假设你已经有一个Graph实例（这里用String类型的顶点属性和边属性举例）
val graph: Graph[String, String] = ... // 替换成你的图数据
val srcVertex: VertexId = 1L // 源顶点ID
val dstVertex: VertexId = 5L // 目标顶点ID

// 获取所有路径
val allPaths = findAllPaths(graph, srcVertex, dstVertex)
// 提取去重后的顶点和边
val (vertices, edges) = extractUniqueVerticesAndEdges(graph, allPaths)

// 打印结果
println("两个顶点之间的所有唯一顶点：")
vertices.foreach(println)
println("\n两个顶点之间的所有唯一边：")
edges.foreach { case (u, v, attr) =>
  println(s"$u -> $v (属性：$attr)")
}

• 如果图里有环，visited集合会帮我们避免无限递归，放心用。
• 要是你的图特别大，单机处理不过来，可以考虑把路径搜索逻辑改成分布式的，比如用Pregel迭代来跟踪所有可能的路径状态。

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