广度优先搜索(Breadth-First Search, BFS, 台湾称“横向优先搜寻”)是最简单的图搜索算法之一。广度优先搜索的特点是总是沿已发现与未发现的边界，向外依次扩展。设起始节点为s，则广度优先搜索算法首先会发现与s距离为k的所有结点后，才会发现与s距离为k+1的结点。广度优先搜索在运行过程中将结点标识为三种状态： 白色：未被发现的结点； 灰色：已被发现，但与其相连的结点尚未全部发现的结点（下一轮进行发现的结点，也是发现结点集的边界）； 黑色：已被发现，且与之相连的其他结点也已经发现。 广度优先搜索因为存在单一的起始结点s，因此整个发现过程可以看作是以s为根节点的一棵树，称为广度优先树，广度优先搜索的过程也是建立一棵以s为根的广度优先树的过程。广度优先树中对每个结点u记录三种信息： π[u]：广度优先树中u的父结点，意味着u第一次被发现时所通过的上一级结点； d[u]：u与根节点s的距离，如果是无权图，也是s到u的最短距离； color[u]：u结点的颜色。 设图G = (V, E)，V是顶点集，E是边集。s是起始节点。则广度优先搜索(Breadth-First Search, BFS)算法如下： view sourceprint? 01.// 初始化整个图（除去起始结点s） 02.foreach(Vertex u in V[G] - {s}) 03.{ 04.    u.Color = BFSColor.WHITE; 05.    u.D = int.MaxValue; 06.    u.π = null; 07.} 08.   09.// 设置起始结点s 10.s.Color = BFSColor.GRAY; 11.s.D = 0; 12.s.π = null; 13.   14.// 初始化一个队列 15.Queue<Vertex> q = new Queue<Vertex>(); 16.q.Enqueue(s); 17.while(q.Count > 0) 18.{ 19.    Vertex u = q.Dequeue(); 20.    foreach(Vertex v in u.Neighbors) 21.    { 22.        if(v.Color == BFSColor.WHITE) 23.        { 24.            v.Color = BFSColor.GRAY; 25.            v.D = u.D + 1; 26.            v.π = u; 27.            q.Enqueue(v); 28.        } 29.    } 30.    u.Color = BFSColor.BLACK; 31.} 广度优先搜索(Breadth-First Search, BFS)的算法复杂度是O(V+E)，其中O(V)时间用于第一步初始化，O(E)时间用于遍历（因为每个结点的邻接表只会访问一次）。   http://www.nocoo.us/2009/01/breadth-first-search/

评论