BreadthFirstScan

BreadthFirstScan[g,s,{"event1"f1,"event2"f2,}]
执行图 g 的广度优先搜索,以顶点 s 为起始点,每次出现 时计算 .

BreadthFirstScan[g,{"event1"f1,"event2"f2,}]
执行整个图 g 的广度优先搜索.

更多信息更多信息

  • BreadthFirstScan[g,s,{}] 以广度优先顺序访问图 g 中与顶点 s 相连接的顶点.
  • 广度优先搜索首先访问与当前被访问的顶点相邻接的所有顶点.
  • BreadthFirstScan[g,{}]g 的顶点列表中从第一个顶点开始执行多个广度优先搜索,然后从顶点列表中第一个未被访问的顶点开始,搜索每个连接的分量.
  • BreadthFirstScan[g,] 给出表示一棵树的 的列表,其中 的前趋结点,而g 的顶点列表.
  • 提供对顶点的探索的事件包括:
  • "DiscoverVertex"当找到顶点时
    "UnvisitedVertex"当未访问顶点被再次找到时
    "VisitedVertex"当已访问顶点被再次找到时
  • 当顶点 u 从已访问顶点 v 被发现,并且 v 距离起始顶点 s 的距离为 d 时,"DiscoverVertex"->fd 调用 .
  • 当未访问顶点 u 从已访问顶点 v 中再次找到时,"UnvisitedVertex"->fru 调用 .
  • 当已访问顶点 u 从已访问顶点 v 中再次找到时,"VisitedVertex"->frv 调用 .
  • 提供对顶点的访问的选项包括:
  • "PrevisitVertex"在访问一个顶点之前
    "PostvisitVertex"在访问一个顶点之后
  • 在顶点 u 被访问之前,"PrevisitVertex"->fs 调用 .
  • 在顶点 u 被访问之后,"PostvisitVertex"->fe 调用 .
  • 一棵广度优先树是由在广度优先搜索中所遍历的边生成的树.
  • 提供对从已访问顶点开始的边的搜索的选项包括:
  • "FrontierEdge"在广度优先搜索树中的边
    "CycleEdge"不在广度优先搜索树中的边
  • 对于边 "FrontierEdge"->ffe 调用 ,其中顶点 v 正在被访问,u 还未被访问过. 通常对扫描广度优先搜索树是很有用的.
  • 对于边 "CycleEdge"->fce 调用 ,其中顶点 v 正在被访问,u 已经被访问过. 通常对寻找不位于广度优先搜索树中的环或者边是很有用的.
  • 对于一个无向图,用于 callback 的边是无向边 .
2010年引入
(8.0)