DepthFirstScan

DepthFirstScan[g, s, {"event1"->f1, "event2"->f2, ...}]
从顶点 s 开始,对图 g 进行深度优先搜索,并且当 出现时计算 .

DepthFirstScan[g, {"event1"->f1, "event2"->f2, ...}]
对整个图 g,进行深度优先搜索 .

更多信息更多信息

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

范例范例打开所有单元关闭所有单元

基本范例 (3)基本范例 (3)

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

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

In[1]:=
Click for copyable input
Out[1]=
In[2]:=
Click for copyable input
Out[2]=

添加标签,以显示访问顶点的顺序:

In[1]:=
Click for copyable input
In[2]:=
Click for copyable input
Out[2]=
In[3]:=
Click for copyable input
In[4]:=
Click for copyable input
Out[4]=
版本 8 的新功能
New to Mathematica? Find your learning path »
Have a question? Ask support »