BFS

run API

• API

  def run[VD: ClassTag, ED: ClassTag](graph: Graph[VD, ED],sourceID: Long,isDirected: Boolean,depthLimit: Int): Graph[(Int, Array[Long]), ED]

• 功能描述

  对于给定源点，最大搜索深度，以广度优先搜索的方式对无权图进行搜索，直到达到最大搜索深度或访问完所有可达节点，记录节点位于的层数和邻居信息

• API描述
  1. 包名：package org.apache.spark.graphx.lib
  2. 类名：BFS
  3. 方法名：run
  4. 输入：Graph[VD, ED]，无权图。
  5. 参数详情：

     参数名称	参数含义	取值类型
     graph	有向图或无向图	Graph[VD, ED]，VD表示节点属性，ED表示边属性
     sourceID	源节点ID	Long型如5907828等，正整数
     isDirected	图类型，有向/无向图	true或false，boolean类型，true表示有向图
     depthLimit	最大搜索深度	Int型，系统当前最大为10，如8等，正整数

  6. 核心参数：
     1. sourceID：源节点。
     2. isDirected：是否为有向图。
     3. depthLimit：最大搜索深度。
  7. 输出：Graph[(Int, Array[Long]), ED]: 输出一个Graph，节点属性信息为(节点位于的层数，节点的邻居)。
• 使用样例

  BFS有向图样例：

  val conf = new SparkConf().setAppName("bfs").setMaster(host)
  val sc = new SparkContext(conf)
  val input = sc.parallelize(Array((1, 2), (1, 3), (2, 4), (2, 5), (3, 6), (3, 7)))
     .map(f => Edge(f._1.toLong, f._2.toLong, 0))
  val graph = Graph.fromEdges[Int, Int](input, 0) 
  val sourceID = 1L 
  val isDirected = true 
  val depthLimit = 10  
  val res = BFS.run(graph, sourceID, isDirected, depthLimit)

  BFS无向图样例：

  val conf = new SparkConf().setAppName("bfs").setMaster(host)
  val sc = new SparkContext(conf)
  val input = sc.parallelize(Array((1, 2), (1, 3), (2, 3), (2, 4), (2, 5)))
     .map(f => Edge(f._1.toLong, f._2.toLong, 0))
  val graph = Graph.fromEdges[Int, Int](input, 0) 
  val sourceID = 1L 
  val isDirected = false 
  val depthLimit = 10  
  val res = BFS.run(graph, sourceID, isDirected, depthLimit)

• 样例结果：
  

  有向图样例结果，以分号为分隔符，第一列为节点ID，第二列为该节点的邻居，第三列为该节点的深度信息（未遍历到的为Int.MaxValue）。

  1;2,3;0
  2;4,5;1
  3;6,7;1
  4;;2
  5;;2
  6;;2
  7;;2

  

  无向图样例结果，以分号为分隔符，第一列为节点ID，第二列为该节点的邻居，第三列为该节点的深度信息（未遍历到的为Int.MaxValue）。

  1;2,3;0
  2;1,3,4,5;1
  3;1,2;1
  4;2;2
  5;2;2