总结A*,Dijkstra,广度优先搜索,深度优先搜索的复杂度比较
广度优先搜索(BFS)
1、将头结点放入队列Q中
2、while Q!=空
u出队
遍历u的邻接表中的每个节点v
将v插入队列中
当使用无向图的邻接表时,复杂度为O(V^2)
当使用有向图的邻接表时,因为每条边只访问一次,不会重复访问,所以总复杂度为O(V+E)
深度优先搜索(DFS)
for each vertex u∈V(G) //执行时间为O(V)
DFS(u)
DFS内部:
for each v 为u的邻接点 //执行时间为O(E)
DFS(v)
总执行时间为O(V+E)
A*搜索
从A开始,遍历周围的点,且避开close中以及障碍点,利用f(x) = g(x)+h(x)评价这些点,选取最佳点。并且如果第二次评价某点时,取记录中该点的f(x)值与现在计算得到的f(x)值更小的,放入到记录中
算法复杂度:
外循环中每次从open中取出点,共取n次,
内循环:遍历它的邻接点n(E),并将这些邻接点放入open中,对open进行排序,open表大小是O(n)量级的,若用快排就是O(nlogn),内循环总的复杂度为O(n*logn+E)=O(n*logn)
总复杂度为 O(n^2*logn)
Dijkstra(旅行商问题,最短距离遍历所有的城市)
行2--4的初始化对n个顶点进行,显然是O(n)
5--6行O(1)
7行n个顶点入队列O(n)
8行--14行,从8行可以看出进行了n遍循环,每遍在第九行调用一次ExtractMin过程,ExtractMin过程需要搜寻邻接表,每一次需要搜寻整个数组,所以一次操作时间是O(n);11行到14行对节点u的邻接表中的边进行检查,总共有|E|次(总共.每条边最多检查一次),因此是O(E);合起来就是O(E+n*n) = O(n^2);
以上合起来就是O(n)+O(1)+O(n)+O(n^2) == O(n^2)
算法复杂度:
O(V^2)