MATHEMATICA 内置符号

BreadthFirstScan

执行图 g 的广度优先搜索，以顶点 s 为起始点，每次出现

时计算

.

BreadthFirstScan

执行整个图 g 的广度优度搜索.

更多信息

BreadthFirstScan 以广度优先顺序访问图 g 中与顶点 s 相连接的顶点.

广度优先搜索首先访问与当前被访问的顶点相邻接的所有顶点.

BreadthFirstScan 在 g 的顶点列表中从第一个顶点开始执行多个广度优先搜索，然后从顶点列表中第一个未被访问的顶点开始，搜索每个连接的分量.

BreadthFirstScan 给出表示一棵树的的列表，其中是的前趋结点，而是 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 的边是无向边 .

范例

关闭所有单元

例 (2)

以广度优先顺序访问树中的顶点：

突出显示广度优先树：

以广度优先顺序访问树中的顶点：

In[1]:=

突出显示广度优先树：

In[1]:=

Out[1]=

In[2]:=

Out[2]=

范围 (17)

使用事件在搜索时执行代码：

求广度优先搜索树的边：

BreadthFirstScan 可用于无向图：

有向图：

如果忽略起始顶点，BreadthFirstScan 搜索整个图：

可用于大规模图：

顶点以查找的顺序访问：

每次只访问一个顶点：

用于可产生未搜索过的顶点的边：

用于可产生搜索过的顶点的边：

在一个有向图中：

在一个无向图中：

当一个顶点被第一次找到，

事件被触发：

当探索已访问过的顶点时，

事件被触发：

对于重新访问未访问过的顶点，

事件被触发：

BreadthFirstScan 返回广度优先搜索树中前趋结点的列表：

前趋结点列表可用于重新构建广度优先搜索树：

构建每个顶点和它的前趋顶点之间的边：

本身是环的边不是树的一部分：

当搜索产生一棵生成树时，TreeGraph 更加便捷：

前趋结点也可以通过

事件得到：

使用 VertexList 初始化，并且当找到一个顶点时，重新赋值：

与 BreadthFirstScan 返回的值相比较：

广度优先搜索树也可以通过

事件得到：

选项 (42)

在

之后，每条边或者传递给

或者传递给

：

当且仅当一条边产生第一次搜索的顶点时，触发

：

在

之后，触发

或者

：

当且仅当相邻的顶点已经被访问时，触发

：

在一棵有向树中，标明对

函数的调用：

对这个图，不触发任何事件：

在一棵无向树中：

对每条边触发这个事件：

在一个有向 CycleGraph 中：

在一个无向 CycleGraph 中：

对于某些边，事件的触发次数超过一次：

在一个有向无圈图中：

突出显示圈中的边：

在一个网格图中：

对于某些边，事件的触发次数超过一次：

在

之后，对相邻的顶点触发

：

对起始顶点，也触发

：

当一个顶点第一次被搜索时，触发

事件：

它可以用于求顶点的广度优先搜索顺序：

事件在对

进行调用之前触发：

在一棵有向树中，显示传递给

函数的变量：

在一棵无向树中：

在一个有向 CycleGraph 中：

在一个无向 CycleGraph 中：

在一个有向无圈图中：

在一个网格图中：

在

后，每条边或者传递给

或者传递给

：

当且仅当一条边产生的顶点第一次被搜索才触发

：

在

之后，对相邻顶点触发

：

对起始顶点也触发

：

对一棵有向树中的每条边调用

函数：

对一棵无向树中的每条边，对它进行调用：

突出显示一个有向 CycleGraph 中的广度优先搜索树：

在一个无向 CycleGraph 中：

在一个有向无圈图中：

在一个网格图中：

是在一次顶点访问中最后触发的事件：

与

相似，它可以用于求顶点的广度优先顺序：

在

后，队列中的下一个未访问顶点继续访问过程：

、

和

的相对顺序：

在每次顶点访问开始时，触发

事件：

与

相似，它可以用来找到顶点的广度优先排序：:

在调用

后的某个时间触发

：

、

和

的相对顺序：

在

后，或者触发

或者触发

：

当且仅当相邻的顶点还未被访问时，触发

：

在一棵有向树中标明传递给

函数的前趋：

对这个图不触发事件：

在一棵有向树中：

对这个图，从不触发事件：

在一个有向 CycleGraph 中：

对这个图从不触发事件：

在一个无向 CycleGraph 中：

在一个有向无圈图中：

在访问一个已搜索的顶点之前，它可能被搜索过0次、1次或者更多次：

在一个网格图中：

在

后，触发

或者

：

当且仅当相邻的顶点已经被访问才触发

：

在一棵有向树中标明传递给

函数的前趋结点：

对这个图从不触发事件：

在一棵无向树中：

在一个顶点被访问之后，从它的每个子结点对其进行访问：

在一个有向 CycleGraph 中：

在一个无向 CycleGraph 中：

在一个有向无圈图中：

对这个图从不触发事件：

在一个网格图中：

在访问每个顶点之后，它可能重新被访问0次、1次或者更多次：

应用 (17)

求单个顶点的出分量：

求一个顶点集合的出分量，作为出分量的并集：

求顶点的入分量：

突出显示不同的出分量：

求一个无向图中顶点的连通分量：

突出显示找到的分量顶点：

求两个顶点之间的最短距离：

建立顶点访问函数（忽略预计算距离）：

初始化源顶点，以广度优先顺序遍历图：

提取目标处的距离，并且与 GraphDistance 相比较：

求与 1 最接近的黑顶点：

当搜索整个图时，计算搜索次数：

建立每个顶点的计数器，和搜索计数的事件句柄：

一些顶点已被搜索若干次：

计算所有连通分量：

在一个无向图中，BreadthFirstScan 访问连通分量中的每个顶点：

重复这个过程直至每个顶点都已经被访问：

与 ConnectedComponents 相比较：

检验一个图是否是二部图：

尝试查找每个顶点的

的一致赋值：

取决于前趋结点的值，每个顶点被赋予值

或者

：

当一个顶点被重新搜索到时，它必须与相邻顶点不具有相同的值：

如果可以搜索一个图，并且找不到任何不一致的地方，则这个图是二部图：

利用

构建一个广度优先搜索树：

突出显示树：

在一个有向图中，

边可以归类为后边（back edges）或者交叉边（cross edges）：

将树的边变成黑色，后边变成蓝色，交叉边变成点状线：

后面的边讲形成圈，如果这些边添加到广度优先搜索树中：

在每个顶点的时间轴中，在搜索的时间处放置一个点，从 previsit 到 postvisit 处放置一条线：

显示一棵有向树中事件的时间轴：

在一棵无向树中：

在一个有向 CycleGraph：

在一个无向 CycleGraph 中：

在一个有向无圈图中：

在一个网格图中：

显示在搜索中顶点的状态如何改变：

把搜索过的顶点变为红色，活动中的顶点变为黄色，访问过的顶点变为蓝色，将不是树的边颜色用来显示它们是否产生

（红色）或者

（蓝色）调用：

求一个未加权的图中的最短路径：

构建顶点访问函数：

以广度优先顺序遍历整个图：

从目标顶点回溯重新构建路径：

与 FindShortestPath 相比较：

求一个未加权的图中的所有最短路径：

构建顶点访问函数：

初始化属性，并且以广度优先顺序遍历整个图：

在目标处提取结果：

在一个空手道俱乐部中，Zachary 的传统友谊网络的中介中心性：

建立顶点访问函数：

在考虑从每个顶点的所有最短路径时，对

进行累积：

中介中心性的累积分布显示有两个得分是突出的：

以中介中心性为顺序对顶点进行排序（1 是管理员，而 34 是教员）：

突出显示上端的两个顶点：

属性和关系 (4)

顶点以广度优先顺序搜索：

对于一个有向图，搜索过程遵循边的方向：

仅搜索通过起始顶点可到达的顶点：

通过从每个连通分量中选出一个起始顶点搜索所有顶点：

对于一个有向图，仅搜索沿着边的方向可到达的顶点：

参见

DepthFirstScan Graph TreeGraph

更多关于

图编程

图与网络

Mathematica 8的新功能概要

8.0的新功能：字母列表

8.0的新功能：数学与算法

版本 8 的新功能