BFS求源代码及思路？
发布网友
共3个回答
热心网友
BFS是广度搜索，这意味从当前点出发，都会到达与它链接的点，你可以想象一下，这样的搜索，是不是很有层次感，是一层层地，如果代价一样的话，相当是求层次最少的，如果代价不一样的话，这里的层次就没有意义了。
热心网友
BFS即宽度优先搜索。从出发点开始，第一次遍历到终点时过的那条路径就是最短的路径。因为这条路径没有多绕一个不相关节点啊，所以它是最短的。
热心网友
BFS在树的遍历中又称作层次遍历（设树的根结点所在层为第0层，从根结点开始依次遍历第1层、第2层、.......、第n层），在从每层到下一层所花费的代价（即问题中所说的每一步的代价）一样的情况下，所花费的总代价和所经过的层数成正比关系，所经过的层数多少（即走过多少步）即可象征所花费的总代价的多少。又由于BFS遍历是由低层到高层的顺序遍历，所以在每一层到下一层所花费代价相同时，即为一种从低花费到高花费的遍历，所以在这种情况下可以用BFS求最短路。
若从每一层到下一层所花费的代价不同，则不能用所经过层数的多少象征所花费的总代价，这时就不能用BFS求最短路。
图的话同理。在每步代价不同时，若求单源最短路可用Dijkstra（适用于不含负权的图）、SPFA（可处理有负权边的图（但不能有负权回路）），若要求任意两点间的最短路可用Floyd算法
