【答案解析】Ⅰ:对于无权图,广度优先搜索总是按照距离源点由近到远来遍历图中每个顶点(这里的距离是指当前顶点到源点路径上顶点的个数),如图3-10所示。图中各顶点分布在3个层上,同一层上的顶点距离源点的距离是相同的。广度优先搜索就是沿着从1~3的层次顺序来遍历各个顶点,并在遍历的过程中形成了一棵树,称之为广度优先搜索生成树,树的分支总是连接不同层上的点,如图3-10中粗线所连。由源点沿生成树分支到达其余顶点的距离都是最近的(可以用层号来描述其远近)。因此对于无权图,可用广度优先搜索遍历的方法来求最短路径。而对于有权图,当图中各个边的权值相同的时候,就可以类比为无权图(无权图可理解为各边权值为1),因为各边没有了权的大小之分,则同样可以用广度优先搜索遍历的方式来求最短路径,所以Ⅰ正确。
