首页 > 代码库 > BFS 和 DFS

BFS 和 DFS

BFS and DFS

一般来说,能用DFS解决的问题,都能用BFS。DFS容易爆栈,而BFS可以自己控制队列的长度。深度优先一般是解决连通性问题,而广度优先一般是解决最短路径问题。

 

 

  • 广优的话,占内存多,能找到最优解,必须遍历所有分枝. 广优的一个应用就是迪科斯彻单元最短路径算法.

  • 深优的话,占内存少,能找到最优解(一定条件下),但能很快找到接近解(优点),可能不必遍历所有分枝(也就是速度快), 深优的一个应用就是连连看游戏.

  • 两个算法都是O(V+E),在用到的时候适当选取。

 

A Tree is typically traversed in two ways:

  • Breadth First Traversal (Or Level Order Traversal)

  • Depth First Traversals

    • Inorder Traversal (Left-Root-Right)

    • Preorder Traversal (Root-Left-Right)

    • Postorder Traversal (Left-Right-Root)

 

BFS(G,s)

   for each vertex v in V[G]

       status[v] = WHITE

       /******其他初始化******/

   status[s] = GRAY //s是原点

   queue q

   入队(q,s);

   while q非空

       t = 出队(q);

       for each vertex v in Adj[t] //与t邻接的点

           if status[v] = WHITE //只对未访问的操作

               status[v] = GRAY //标记为第一次访问

               /******其他操作******/

               入队(q,v)

       status[t] = BLACK   //此点已经处理完了

 

 

 

DFS(G,s)

   for each vertex v in V(G)

       status[v] = WHITE

       /******其他初始化******/

   for each vertex v in V(G)

       if(status[v]==WHITE)

           DFS-VISIT(v)

 

DFS-VISIT(v)

   status[v] = GRAY

   for each vertex t in Adj(v)

       if status[t] = WHITE

           DFS-VISIT(t)

           /******其他操作******/

   status[v] = BLACK

 

BFS 和 DFS