两种优先搜索算法

两种优先搜索（查找）算法

     -- 深度优先 & 广度优先 （经典算法）

---

> 描述

”如果说深度优先查找遍历表现出来的是一种勇气（该算法尽可能地“离家”远些），广度优先查找遍历表现出来的则是一种谨慎。“

好吧，具体两种优先搜索算法逻辑描述，如下：

 1， DFS -- 深度优先搜索

 2， BFS -- 广度优先搜索

> 算法

 DFS(G)

 // 实现给定图的深度优先查找遍历

 // 输入: 图 G = <V, E>

 // 输出: 图G的顶点, 按照被DFS遍历第一次访问到的先后次序, 用连续的整数标记.

 V = { 0 } // 将V包含顶点标记为0, 表示均未访问状态.

 count = 0;

 for each vertex v in V do

if v is marked with 0

dfs(v)

dfs(v)

 // 递归访问所有和v相连接的未访问的顶点, 然后按照全局变量 count的值

 // 根据遇到它们的先后顺序, 给它们赋上相应的数字

 count +=1;

 mark v with count

 for each vertex w in V adjacent to v do

 if w is marked with 0

  dfs (w);

 BFS(G)

 // 实现给定图的广度优先查找遍历

 // 输入: 图 G = <V, E>

 // 输出: 图G的顶点, 按照被BFS遍历第一次访问到的先后次序, 用连续的整数标记.

 V = { 0 } // 将V包含顶点标记为0, 表示均未访问状态.

 count = 0;

 for each vertex v in V do

if v is marked with 0

bfs(v)

bfs(v)

// 访问所有和v相连接的未访问的顶点, 然后按照全局变量 count的值

// 根据访问它们的先后顺序, 给它们赋上相应的数字

count +=1;

mark v with count and initialize a queue with v

while the queue is not empty do

for each vertex w in V adjacent to the front vertex v do

if w is marked with 0

 cout += 1;

 mark w with count

 add w to the queue

 remove the front vertex from the queue

> 对比

两种优先搜索算法，多方面因素对比表如下：

项目	DFS	BFS
数据结构	栈(stack)	队列(queue)
顶点顺序的种类	两种顺序	一种顺序
边的类型(无向图)	树向边和回边	树向边和交叉边
应用	连通性/无环行/关节点	连通性/无环性/最少边路径
邻接矩阵的效率	O (|V|^2)	O (|V|^2)
邻接链表的效率	O (|V| + |E|)	O (|V| + |E|)

> 参考

A.

  文章描述包含有引用自《算法设计与分析基础（第2版）》涉及的章节内容。

B.

  二叉树的两种优先搜索（遍历），示例C++程序代码参见 Github。

void bfs_tree(treeT* tree);

void dfs_tree(treeT* tree);

还有，下面两道小算法题，可以借助深度优先搜索算法得到快速的求解。

a 简单栈的实现，前序遍历二叉树（深度优先搜索）。

b 关于二叉树，查找存在一条从根节点至叶子节点的路径的数值总和为Value。

     （结合深度优先搜索二叉树）