图的广度优先搜索（bfs）

图的广度优先搜索(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为起点5public 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 implements Iterable{//记录首结点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;}//向队列中插入元素tpublic void enqueue(T t){if (last==null){//当前尾结点last为nulllast= new Node(t,null);head.next=last;}else {//当前尾结点last不为nullNode oldLast = last;last = new Node(t, null);oldLast.next=last;}//元素个数+1N++;}//从队列中拿出一个元素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;}@Overridepublic Iterator iterator() {return new QIterator();}private class QIterator implements Iterator{private Node n;public QIterator(){this.n=head;}@Overridepublic boolean hasNext() {return n.next!=null;}@Overridepublic Object next() {n = n.next;return n.item;}}}