BreadthFirstScan

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

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

BreadthFirstScan[{vw,},]
使用 vw 规则来指定图 g.

更多信息更多信息

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