Question

广度优先遍历是什么？

Answer 1

1.广度优先遍历的思想广度优先遍历类似树的按层次遍历。设初始状态时图中的所有顶点未被访问，则算法思想为：首先访问图中某指定的起始顶点v，并将其标记为已访问过，然后由v出发依次访问v的各个未被访问的邻接点v1，v2，…，vk；并将其均标识为已访问过，再分别从v1，v2，…，vk出发依次访问它们未被访问的邻接点，并使“先被访问顶点的邻接点”先于“后被访问顶点的邻接点”被访问。直至图中所有与顶点v路径相通的顶点都被访问到。

若G是连通图，则遍历完成；否则，在图G中另选一个尚未访问的顶点作为新源点继续上述搜索过程，直至图G中所有顶点均被访问为止。

2.广度优先遍历示例例如，对图7－18（a）所示的图G，假设指定从顶点v1开始进行广度优先遍历，首先访问v1，因与v1相邻并且未被访问过的顶点有v2和v6，则访问v2和v6，然后访问与v2相邻并未访问的邻接点v2，v7，再访问与v6相邻并且未被访问过的邻接点v5，按这样的次序依次访问与v2相邻并且未被访问过的邻接点v4，v8，与v7相邻并且未被访问过的邻接点v9，此时，与v5，v4，v8，v9相邻并且未被访问过的邻接点没有了，即图G中的所有顶点访问完，其遍历序列为：v1－＞v2－＞v6－＞v2－＞v7－＞v5－＞v4－＞v8－＞v9。这种顺序不是唯一的，如果从v1出发后，相邻的多个顶点优先选择序号大的顶点访问，其遍历序列为：v1－＞v6－＞v2－＞v5－＞v7－＞v2－＞v4－＞v9－＞v8。同理，图7－18（b）是假设从v1开始，相邻的多个顶点优先选择序号小的顶点访问，其遍历序列为：v1－＞v2－＞v2－＞v4－＞v5－＞v6－＞v7－＞v8；相邻的多个顶点优先选择序号大的顶点访问，其遍历序列为：v1－＞v2－＞v2－＞v7－＞v6－＞v5－＞v4－＞v8。图7－18（c）假设从a开始，相邻的多个顶点优先选择ASCII码小的顶点访问，其遍历序列为：a－＞b－＞d－＞e－＞f－＞c－＞g；相邻的多个顶点优先选择ASCII码大的顶点访问，其遍历序列为：a－＞f－＞e－＞d－＞b－＞g－＞c。

2.广度优先遍历的算法在广度优先遍历中，要求先被访问的顶点其邻接点也被优先访问，因此，必须对每个顶点的访问顺序进行记录，以便后面按此顺序访问各顶点的邻接点。应利用一个队列结构记录顶点的访问顺序，将访问的每个顶点入队，然后再依次出队。

在广度优先遍历过程中，为了避免重复访问某个顶点，也需要创建一个一维数组visited［n］（n是图中顶点的数目），用来记录每个顶点是否已被访问过。