DepthFirstScan

DepthFirstScan[g,s,{"event1"f1,"event2"f2,…}]

从顶点 s 开始，对图 g 进行深度优先搜索，并且当 "eventi" 出现时计算 fi.

DepthFirstScan[g,{"event1"f1,"event2"f2,…}]

对整个图 g 进行深度优先搜索.

DepthFirstScan[{vw,…},…]

用规则 vw 指定图 g.

更多信息

  • DepthFirstScan 也称为深度优先搜索（DFS）或深度优先遍历.
  • DepthFirstScan[g,s,{…}] 以深度优先顺序访问图 g 中与顶点 s 相连通的顶点.
  • 在深度优先顺序中，与最近访问的顶点相邻的顶点首先被访问.
  • DepthFirstScan[g,{…}] 从 g 的顶点列表中的第一个顶点开始，接着从顶点列表中第一个未访问的顶点开始，依次进行多重深度优先搜索，实际上这里访问了每个连通的分量.
  • DepthFirstScan[g,…] 给出表示一棵树的一个列表 {w1,w2,…}，其中 wi 是 vi 的前趋结点，而{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"在深度优先搜索树中的边
    "BackEdge"在深度优先搜索树中通向祖先结点的边
    "ForwardEdge"在深度优先搜索树中通向子孙结点的边
    "CrossEdge"其它边
  • 对于边 vu，"FrontierEdge"->ffe 调用 ffe[vu]，其中顶点 v 正在被访问，u 还未被找到. 这么做通常对扫描深度优先搜索树是很有用的.
  • 对于边 vu，"BackEdge"->fbe 调用 fbe[vu]，其中顶点 v 正在被访问，u 已经找到，并且在深度优先搜索树中它是 v 的祖先结点. 这么做通常对求回路很有用.
  • 对于边 vu，"ForwardEdge"->gfe 调用 gfe[vu]，其中顶点 v 正在被访问，u 已经找到，并且在深度优先搜索树中它是 v 的子孙结点.
  • 对于边 vu，"CrossEdge"->fce 调用 fce[vu]，其中顶点 v 正在被访问，u 已经找到，并且不在当前的深度优先搜索树中或者虽然在相同的深度优先搜索树，但在不同的分支中. 这对于探测多个深度优先搜索树通常是很有用的.
  • 对于一个无向图，用于callback 的边是无向边 vu.

背景

  • DepthFirstScan 从根顶点出发对图进行遍历，对每个分支它都会探索到尽头之后再返回. 在扫描过程中，每次相关事件（发现顶点，发现未访问过的顶点，重新发现顶点）被触发时，都可以执行一个用户定义的函数. 深度优先遍历在计算许多图性质时是很有用的，因为，正如 Tarjan 和 Hopcroft 在 1970 年代早期揭示的，它对图论中的许多问题都是一个线性时间的算法. 因此使用 DepthFirstScan 可以高效的实现用户自定义的图理论算法. 应用实例包括寻找连通分量，寻找桥，平面性检测，以及拓扑排序.
  • 在深度优先顺序中，与最近访问的顶点相邻的顶点首先被访问. 深度优先扫描可被用于搜索或访问图的所有顶点和边，或者只是从指定顶点出发可到达的顶点和边.
  • 深度优先扫描有时也被称为深度优先搜索（DFS）或深度优先遍历. 法国数学家 Charles Pierre Trémaux 在 19 世纪首先研究了深度优先扫描的一个版本，以此来求解迷宫.
  • BreadthFirstScan 是一个类似的遍历算法，它从一个根顶点出发，检查所有的相邻顶点，然后再访问刚才检查的邻居的邻居，如是重复继续下去.

范例

基本范例  (3)

以深度优先顺序访问一棵树中的各个顶点：

突出显示深度优先搜索树：

添加标签，以显示访问顶点的顺序：

Wolfram Research (2010)，DepthFirstScan，Wolfram 语言函数，https://reference.wolfram.com/language/ref/DepthFirstScan.html （更新于 2015 年）.

文本

Wolfram Research (2010)，DepthFirstScan，Wolfram 语言函数，https://reference.wolfram.com/language/ref/DepthFirstScan.html （更新于 2015 年）.

CMS

Wolfram 语言. 2010. "DepthFirstScan." Wolfram 语言与系统参考资料中心. Wolfram Research. 最新版本 2015. https://reference.wolfram.com/language/ref/DepthFirstScan.html.

APA

Wolfram 语言. (2010). DepthFirstScan. Wolfram 语言与系统参考资料中心. 追溯自 https://reference.wolfram.com/language/ref/DepthFirstScan.html 年

BibTeX

@misc{reference.wolfram_2024_depthfirstscan, author="Wolfram Research", title="{DepthFirstScan}", year="2015", howpublished="\url{https://reference.wolfram.com/language/ref/DepthFirstScan.html}", note=[Accessed: 22-November-2024 ]}

BibLaTeX

@online{reference.wolfram_2024_depthfirstscan, organization={Wolfram Research}, title={DepthFirstScan}, year={2015}, url={https://reference.wolfram.com/language/ref/DepthFirstScan.html}, note=[Accessed: 22-November-2024 ]}