图的广度优先搜索(Broad First Search)

所谓的深度优先搜索，指的是在搜索时，如果遇到一个结点既有子结点，又有兄弟结点，那么先找兄弟结点，然后找子结点。

类似于一个分层搜索的过程，广度优先遍历需要使用一个队列以保持访问过的结点的顺序，以便按这个顺序来访问这些结点的邻接结点

广度优先遍历算法步骤

1. 访问初始结点v并标记结点v为已访问。
2. 结点v入队列
3. 当队列非空时，继续执行，否则算法结束。
4. 出队列，取得队头结点u。
5. 查找结点u的第一个邻接结点w。
6. 若结点u的邻接结点w不存在，则转到步骤3
7. 否则循环执行以下三个步骤：
8.  若结点w尚未被访问，则访问结点w并标记为已访问。
9. 结点w入队列
10. 查找结点u的继w邻接结点后的下一个邻接结点w，转到步骤6。

 API设计

代码实现

package 深度优先搜索;

import 基本图.Graph;

public class DepthFirstSearch {
    //索引代表顶点，值表示当前顶底是否已经被搜索过
    private boolean[] marked;
    //记录有多少个顶点与s顶点相通
    private int count;

    //构造深度优先搜索对象，使用深度优先搜索找出G图中顶点的所有相邻顶点（找兄弟节点）
    //s为起点5
    public DepthFirstSearch(Graph G, int s){
        //初始化marked数组
        this.marked = new boolean[G.v()];
        //初始化跟顶点s相通的顶点的数量
        this.count = 0;
        dfs(G,s);
    }

    //使用深度优先搜索找出G图中v顶点的所有相通的顶点（找子节点）
    private void dfs(Graph G,int v){
        //把v标识为已搜索
        marked[v] = true;

        for (Integer w : G.adj(v)) {
            //判断当前w顶点有没有被搜索过，如果没有被搜索过 ，则递归调用dfs方法进行深度搜索
            if(!marked[w]){
                dfs(G,w);
            }
        }
        //相通顶点的数量+1,找到兄弟节点
        count++;
    }

    //判断w顶点与s顶点是否相通
    public boolean marked(int w){
        return marked[w];
    }

    //获取与顶点s相通的所有顶点的总数
    public int count(){
        return count;
    }
}

核心代码

    //使用深度优先搜索找出G图中v顶点的所有相通的顶点（找子节点）
    private void dfs(Graph G,int v){
        //把v标识为已搜索
        marked[v] = true;

        for (Integer w : G.adj(v)) {
            //判断当前w顶点有没有被搜索过，如果没有被搜索过 ，则递归调用dfs方法进行深度搜索
            if(!marked[w]){
                dfs(G,w);
            }
        }
        //相通顶点的数量+1,找到兄弟节点
        count++;
    }

Demo

package 深度优先搜索;

import 基本图.Graph;

public class DepthFirstSearchTest {
    public static void main(String[] args) {
        //准备Graph对象
        Graph G = new Graph(13);
        G.addEdge(0,5);
        G.addEdge(0,1);
        G.addEdge(0,2);
        G.addEdge(0,6);
        G.addEdge(5,3);
        G.addEdge(5,4);
        G.addEdge(3,4);
        G.addEdge(4,6);

        G.addEdge(7,8);

        G.addEdge(9,11);
        G.addEdge(9,10);
        G.addEdge(9,12);
        G.addEdge(11,12);

        //准备深度优先搜索对象
        DepthFirstSearch search = new DepthFirstSearch(G,0);

        //准备深度优先搜索对象
        int count = search.count();
        System.out.println("与起点0相通的顶点的数量为：" + count);

        //测试与某个顶点相通的顶点数量
        boolean marked1 = search.marked(5);
        System.out.println("顶点5和0是否相通：" + marked1);

        //测试某个顶点与起点是否相通
        boolean marked2 = search.marked(7);
        System.out.println("顶点7和0是否相通：" + marked2);
    }
}

导入的包

package 队列;

import java.util.Iterator;

public class Queue<T> implements Iterable<T>{
    //记录首结点
    private Node head;
    //记录最后一个结点
    private Node last;
    //记录队列中元素的个数
    private int N;


    private class Node{
        public T item;
        public Node next;

        public Node(T item, Node next) {
            this.item = item;
            this.next = next;
        }
    }
    public Queue() {
        this.head = new Node(null,null);
        this.last=null;
        this.N=0;
    }

    //判断队列是否为空
    public boolean isEmpty(){
        return N==0;
    }

    //返回队列中元素的个数
    public int size(){
        return N;
    }

    //向队列中插入元素t
    public void enqueue(T t){

        if (last==null){
            //当前尾结点last为null
            last= new Node(t,null);
            head.next=last;
        }else {
            //当前尾结点last不为null
            Node oldLast = last;
            last = new Node(t, null);
            oldLast.next=last;
        }

        //元素个数+1
        N++;
    }

    //从队列中拿出一个元素
    public T dequeue(){
        if (isEmpty()){
            return null;
        }

        Node oldFirst= head.next;
        head.next=oldFirst.next;
        N--;

        //因为出队列其实是在删除元素，因此如果队列中的元素被删除完了，需要重置last=null;

        if (isEmpty()){
            last=null;
        }
        return oldFirst.item;
    }


    @Override
    public Iterator<T> iterator() {
        return new QIterator();
    }

    private class QIterator implements Iterator{
        private Node n;

        public QIterator(){
            this.n=head;
        }
        @Override
        public boolean hasNext() {
            return n.next!=null;
        }

        @Override
        public Object next() {
            n = n.next;
            return n.item;
        }
    }


}