知识卡片
广度层数给出无权最少跳数
无权图中,从源点首次发现邻居时可记dist[v]=dist[u]+1,并记录父节点u。FIFO让更小层数先被扩展,因此首次发现的层数就是最少经过边数;沿父节点回溯可得到一条相应最短路。
02918从1到2/3各一跳,到4两跳,到5无可达路径。边数不是中间顶点数;最少跳数也不自动等于最小时延或最低费用,带不同权重时不能直接用这条结论。
父节点在首次发现时确定,源点没有搜索父节点,未到达顶点也不在这棵搜索树中。存在多条同长路径时只得到其中一条,不保证路径唯一;BFS树也不是一般带权最小生成树算法。
199的02939中源node1为0跳,node2/3为1,node4/5为2,node6为3;到node4可选1→2→4两跳。最少跳数不是带权“最佳路径”的普遍定义,图只是本例六节点模型,不是实时Internet测量。
201关闭航线后按剩余有向/双向边测试起终可达即可;不可达不说明每条关闭边单独都是桥,多边联合失效也能切断路径,且有向可达与无向桥不能混用。标准直接邻接BFS O(V+E)条件与本章链式查表实现区别已专卡说明。
这张卡片看不懂?
这张卡片已通过人工审查,不再接受失败反馈。
已有反馈 · 0 条
还没有人提交反馈。
在整书笔记中的位置
- · 广度层数给出无权最少跳数
- · 关于图的应用举例:计算网络跳数
- · 问与答
原书出处 · 3 处
- · 查看原书依据
最短路径只包含1跳,当找到顶点2和3时就记录下来。从顶点1到顶点4的最短路径包含2跳:其中1跳已经在找到顶点2时记录下来了,另外一跳则在从顶点2出发到顶点4时记录下来。也可以采用广度优先搜索法来生成一棵广度优先树。广度优先树是用来维护我们发现的每个顶点的祖先结点信息的数据结构。由于顶点只能被发现一次
- · 查看原书依据
node1作为起点,有不止1条可以通往node4的路径。<node1,node2,node4>,<node1,node3,node2,node4>,以及<node1,node3,node5,node4>都是可行的路径。广度优先搜索可以确定最短的路径选择,即<node1,node2,node4>,一共
- · 查看原书依据
航线不可用时,目的地就必须在图中变为不可达的顶点。关闭的航线在图中组成了桥。这个问题能够在O(V+E)的时间内解决,这里V代表助航设备的数量,而E代表航线的数量。这正是广度优先搜索的时间复杂度。 问:假设要使用计算机来模拟系统中的状态。比如,设想在十字路口处的交通灯系统,其中包含多种状态,以及系统需