广度优先搜索(BFS)

一、概述

广度优先搜索英文全称为(breadth-first search,bfs),为图的一种遍历方式，所采用的策略可概况为越早被访问到的顶点，其邻居顶点越早被访问。于是，从根顶点s的BFS搜索，将首先访问顶点s；再依次访问s所有尚未访问到的邻居；再按后者被访问的先后次序，逐个访问它们的邻居。
若将bfs策略应用于树结构，其效果等同与层次遍历

二、实现

仿照树的层次遍历，借助队列来存储已访问过得顶点。
过程：先从图中选取一个顶点，作为遍历图的起始顶点，并加入队列中，然后依次访问该顶点的邻居顶点，并按照顺序加入队列中。 当访问了该顶点的所有邻居顶点后，把该顶点从队列中移除。接着获取新的队列头，访问该顶点的邻居顶点，最后以此类推，直到所有顶点被访问。
在遍历时，该顶点的邻居顶点有可能已经被访问过了，意味着边不属于遍历树，可将该边归类为跨边(cross edge)

下图给出一个8个顶点，11条边的有向图的BFS，始于顶点s

通过获取顶点出队列的顺序，得到图的遍历顶点的顺序

三、代码

下列代码是java编写的，用一个整型数值来代表一个顶点

创建图的操作接口

package cn.adt.bfs.graph;

import java.util.Set;

/**
 * Created by YangT on 2017-8-10.
 * 图的顶点用整形来表示
 */
public interface Graph {
    boolean addVertex(Integer v);

    Double addEdge(Integer from,Integer to);

    boolean addEdge(Integer from,Integer to,Double weigth);

    boolean removeVertex(Integer v);

    boolean removeEdge(Integer from,Integer to);

    Set<Integer> getVertices();

    Set<Integer> getNeighbors(Integer v);

    int size();
}

一个有向图实例

package cn.adt.bfs.graph;

import java.util.HashMap;
import java.util.HashSet;
import java.util.Map;
import java.util.Set;

import cn.adt.bfs.graph.Graph;

/**
 * Created by YangT on 2017-8-10.
 * 有向图
 */
public class DirectedGraph implements Graph {
    private Map<Integer,Set<Integer>> vertexMap = new HashMap<>();

/**
 * map的键存放顶点，值存放与该顶点相连的顶点
 */
@Override
public boolean addVertex(Integer v) {
    vertexMap.put(v, new HashSet<Integer>());
    return true;
}

@Override
public Double addEdge(Integer from, Integer to) {
    if(!vertexMap.containsKey(from)) return -1d;
    if(!vertexMap.containsKey(to)) return -1d;
    vertexMap.get(from).add(to);
    return 0d;
}

@Override
public boolean addEdge(Integer from, Integer to, Double weigth) {
    //当前不支持带权图
    return false;
}

@Override
public boolean removeVertex(Integer v) {
    if(!vertexMap.containsKey(v)) return false;
    vertexMap.remove(v);
    return true;
}

@Override
public boolean removeEdge(Integer from, Integer to) {
    if(!vertexMap.containsKey(from)) return false;
    if(!vertexMap.containsKey(to)) return false;
    vertexMap.get(from).remove(to);
    return true;
}

@Override
public Set<Integer> getVertices() {
    return vertexMap.keySet();
}

@Override
public Set<Integer> getNeighbors(Integer v) {
    return vertexMap.get(v);
}

@Override
public int size() {
    return vertexMap.size();
}

}

BFS实现

package cn.graph.bfs;

import java.util.HashSet;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;
import java.util.Set;
import cn.adt.bfs.graph.Graph;
/**
 * Created by YangT on 2017-8-10.
 * BFS
 */
public class BFS {
    //需要创建一个图
    private Graph graph;
    //路径和队列
    private List<Integer> path = new LinkedList<>();
    private Queue<Integer> queue = new LinkedList<>();
    public BFS(Graph graph){
        this.graph = graph;
    }
    //搜索
    public void search(Integer root){
        if(root == null || !graph.getVertices().contains(root))
            return;
        //已访问的顶点存入该set中
        Set<Integer> visited = new HashSet<>();
        visited.add(root);
        path.add(root);
        queue.add(root);
        while(!queue.isEmpty()){
            Integer vertex = queue.peek();
        for (Integer neighbor : graph.getNeighbors(vertex)) {
                //判断邻居顶点是否为未加入队列的顶点和未被访问的顶点
                if(!queue.contains(neighbor) && !visited.contains(neighbor)){
                    queue.add(neighbor);
                    visited.add(neighbor);
                    path.add(neighbor);
                }
            }
            queue.remove();
        }
    }
    //返回遍历顶点顺序
    public List<Integer> getPath(Integer source){
        if(source == null || !graph.getVertices().contains(source))
            return null;
        search(source);
        return path;
    }
}

测试代码

package cn.test;

import java.util.List;

import cn.adt.bfs.graph.DirectedGraph;
import cn.adt.bfs.graph.Graph;
import cn.graph.bfs.BFS;

/**
 * Created by YangT on 2017-8-10.
 * test
 */
public class GraphTest {
    public static void main(String[] args) {
        /**
         * 创建有向图
         * 节点由整型数值代替
         * 输出为节点访问路径
         */
        Graph g = new DirectedGraph();
        for (int i = 1; i < 9; i++) {
            g.addVertex(i);
        }
        g.addEdge(2, 1);
        g.addEdge(3, 1);
        g.addEdge(3, 4);
        g.addEdge(5, 2);
        g.addEdge(5, 6);
        g.addEdge(5, 8);
        g.addEdge(6, 1);
        g.addEdge(7, 3);
        g.addEdge(7, 4);
        g.addEdge(8, 7);
        BFS bfs = new BFS(g);
        List<Integer> paths = bfs.getPath(5);
        for (Integer v : paths) {
            System.out.print(v + " ");
        }
    }
}

图的构造顶点由整型来代替。测试类创建的图仿照上面图片建立
如果选取的起始顶点是其它的顶点，一遍广度优先搜索可能不能全部遍历到所有顶点。

对于无向的连通图或者有向的强连通图，一遍BFS可以全部访问到，对于无向的非连通图就不可能一次遍历访问到所有顶点了，对于有向的非强连通图则有可能能,有可能不能

**代码写的不是特别好，不是很完善，希望能指出。
如有哪里错了，希望大家能指正，谢谢。**

参考书籍：数据结构第三版 作者：邓俊辉
参考代码：
https://github.com/sherxon/AlgoDS/blob/master/src/algo/graph/BFS.java