内容概要：
- BFS类的实现
- BFS求解连通分量
- BFS求解无向图点对之间的一条最短路径
- BFS判定无环图和二分图
- BFS与DFS的联系
树与图的广度优先遍历对比
树的层次遍历其实就是一种广度优先遍历。图的广度优先遍历和树的广度优先遍历非常类似，区别只在于图要对节点是否被遍历做记录。
广度优先遍历类
BFS只是和DFS的遍历逻辑不通，有了DFS的基础，不难给出BFS的相关类。
广度优先遍历到某个顶点后，要遍历与它相邻的所有顶点。这个过程使用队列实现。
import java.util.ArrayList;
import java.util.LinkedList;
import java.util.Queue;
public class GraphBFS {
private Graph G;
private boolean[] visited;
private ArrayList<Integer> order = new ArrayList<>();
public GraphBFS(Graph G){
this.G = G;
visited = new boolean[G.V()];
for(int v = 0; v < G.V(); v ++)
if(!visited[v])
bfs(v);
}
private void bfs(int s){
// 从 s 开始进行BFS
Queue<Integer> queue = new LinkedList<>();
queue.add(s);
visited[s] = true;
while(!queue.isEmpty()) {
int v = queue.remove(); // 取队头
order.add(v);
for (int w : G.adj(v))
if (!visited[w]) {
queue.add(w);
visited[w] = true;
}
}
}
public Iterable<Integer> order(){
return order;
}
public static void main(String[] args){
Graph g = new Graph("g.txt");
GraphBFS graphBFS = new GraphBFS(g);
System.out.println("BFS :" + graphBFS.order());
}
}
广度优先遍历一样可以解决求图的连通分量个数、环检测、二分图检测等。
BFS解决单源路径问题
BFS的性质
遍历时由顶点到顶点一定是跨越边数最少的路径。
求解路径问题
两个顶点在同一连通分量表示有路径，从一点出发，记录经过的顶点，直到到达另一顶点这就是一条路径。具体做法就是记录每个顶点是从哪里来的，由于会有访问标记，所以这个值是唯一的，最后从终点到源点反推即得到路径。
由BFS的性质，这个路径一定是跨过的边数最少的路径，如果是无权图，就是最短路径。
import java.util.ArrayList;
import java.util.Collections;
import java.util.LinkedList;
import java.util.Queue;
public class ShortestPath {
private Graph G;
private int s;
private boolean[] visited;
private int[] pre;
private int[] dis;
public ShortestPath(Graph G, int s){
this.G = G;
this.s = s;
visited = new boolean[G.V()];
dis = new int[G.V()];
pre = new int[G.V()];
for(int i = 0; i < G.V(); i ++) {
pre[i] = -1;
dis[i] = -1;
}
bfs(s);
}
private void bfs(int s){
// 从 s 开始进行BFS
Queue<Integer> queue = new LinkedList<>();
queue.add(s);
visited[s] = true;
pre[s] = s;
dis[s] = 0;
while(!queue.isEmpty()) {
int v = queue.remove(); // 取队头
for (int w : G.adj(v))
if (!visited[w]) {
queue.add(w);
visited[w] = true;
pre[w] = v;
dis[w] = dis[v] + 1;// 距离加一
}
}
}
public boolean isConnectedTo(int t){
G.validateVertex(t);
return visited[t];// 意味着 s 与 t 在同一连通分量;
}
public Iterable<Integer> path(int t){
// s -> t 的路径
ArrayList<Integer> res = new ArrayList<>();
if(!isConnectedTo(t)) return res;
int cur = t;
while(cur != s){
res.add(cur);
cur = pre[cur];
}
res.add(s);
Collections.reverse(res);
return res;
}
public int dis(int t){
// s -> t 的距离，不关注路径，只关注最短距离
G.validateVertex(t);
return dis[t];
}
public static void main(String[] args){
Graph g = new Graph("g.txt");
ShortestPath sp = new ShortestPath(g,0);
System.out.println("0 -> 3: " + sp.dis(3));
}
}
由上也不难得到所有点对之间的最短路径。
BFS求解连通分量
与DFS解决连通分量问题思路一样，将visited数组定义为整型数组，初值为-1表示没有访问过这个顶点，而非负值就代表顶点所属的连通分量。
import java.util.ArrayList;
import java.util.LinkedList;
import java.util.Queue;
public class ConnectedComponents {
private Graph G;
private int[] visited;
private int cccount = 0;
public ConnectedComponents(Graph G){
this.G = G;
visited = new int[G.V()];
for(int i = 0; i < visited.length; i ++)
visited[i] = -1;
for(int v = 0; v < G.V(); v ++)
if(visited[v] == -1) {
bfs(v, cccount);
cccount ++;
}
}
private void bfs(int s, int ccid){
Queue<Integer> queue = new LinkedList<>();
queue.add(s);
visited[s] = ccid;
while(!queue.isEmpty()){
int v = queue.remove();
for(int w: G.adj(v))
if(visited[w] == -1){
queue.add(w);
visited[w] = ccid;
}
}
}
public int count(){ // 返回连通分量个数
return cccount;
}
public boolean isConnected(int v, int w){
return visited[v] == visited[w];
}
public ArrayList<Integer>[] components(){
// 返回各个连通分量
ArrayList<Integer>[] res = new ArrayList[cccount];
for(int i = 0; i < cccount; i ++)
res[i] = new ArrayList<>();
for(int v = 0; v < G.V(); v ++)
res[visited[v]].add(v);
return res;
}
public static void main(String args[]){
Graph g = new Graph("g.txt");
ConnectedComponents cc = new ConnectedComponents(g);
ArrayList<Integer>[] comp = cc.components();
for(int ccid = 0; ccid < comp.length; ccid ++) {
System.out.print(ccid + ": ");
for (int w : comp[ccid])
System.out.print(w + " ");
System.out.println();
}
}
}
BFS求解环检测
与DFS解决该问题思路一样，如果一个被访问的顶点再次被访问到，且这个顶点不是它前一个节点，则说明图中存在环。
import java.util.LinkedList;
import java.util.Queue;
public class CycleDetection {
private Graph G;
private boolean[] visited;
private int[] pre;
private boolean hasCycle = false;
public CycleDetection(Graph G){
this.G = G;
visited = new boolean[G.V()];
pre = new int[G.V()];
for(int v = 0; v < G.V(); v ++)
pre[v] = -1;
for(int v = 0; v < G.V(); v ++)
if(!visited[v])
if(bfs(v)){ // 如果通过BFS检测出环
hasCycle = true;
break;
}
}
private boolean bfs(int s){
Queue<Integer> queue = new LinkedList<>();
queue.add(s);
visited[s] = true;
pre[s] = s;
while(!queue.isEmpty()){
int v = queue.remove();
for(int w: G.adj(v)){
if(!visited[w]){
queue.add(w);
visited[w] = true;
pre[w] = v;
}
// 这里是逻辑的关键
// 如果 w 已经被访问过了，我们还必须判断，w 不是 v 的上一个节点
// 如果 w 不是 v 的上一个节点，说明我们找到了一个环
else if(pre[v] != w)
return true;
}
}
return false;
}
public boolean hasCycle(){
return hasCycle;
}
public static void main(String[] args) {
Graph g = new Graph("g.txt");
CycleDetection cycleDetection = new CycleDetection(g);
System.out.println(cycleDetection.hasCycle());
}
}
BFS判定二分图
通过染色操作完成，用两种颜色对图进行染色，如果可以每两个相邻顶点都不同色，则这个图是二分图。
import java.util.LinkedList;
import java.util.Queue;
public class BiPartitionDetection {
private Graph G;
private boolean[] visited;
private int[] colors; // 两种颜色,实际 colors 可以兼有 visited 的功能
private boolean isBipartite = true;
public BiPartitionDetection(Graph G){
this.G = G;
visited = new boolean[G.V()];
colors = new int[G.V()];
for(int v = 0; v < G.V(); v ++)
colors[v] = -1;
for(int v = 0; v < G.V(); v ++)
if(!visited[v])
if(!bfs(v)){
isBipartite = false;
break;
}
}
private boolean bfs(int s){
// 从s 点开始看整张图是否是二分图
Queue<Integer> queue = new LinkedList<>();
queue.add(s);
visited[s] = true;
colors[s] = 0;
while (!queue.isEmpty()){
int v = queue.remove();
for(int w: G.adj(v)) {
if (!visited[w]) {
queue.add(w);
visited[w] = true;
colors[w] = 1 - colors[v];
}
else if(colors[v] == colors[w]){
return false;
}
}
}
return true;
}
public static void main(String[] args) {
Graph g = new Graph("g.txt");
BiPartitionDetection bipartitionDetection = new BiPartitionDetection(g);
System.out.println(bipartitionDetection.isBipartite);
}
}
BFS与DFS之间的联系
观察BFS和DFS的非递归代码：
BFS
visited[0...V-1] = false;
for(int v = 0; v < G.V(); v ++)
if(!visited[v])
bfs(v);
void bfs(int s){
Queue<Integer> queue = new LinkedList<>();
queue.add(s);
visited[s] = true;
while(!queue.isEmpty()) {
int v = queue.remove();
order.add(v);
for (int w : G.adj(v))
if (!visited[w]) {
queue.add(w);
visited[w] = true;
}
}
}
DFS
visited[0...V-1] = false;
for(int v = 0; v < G.V(); v ++)
if(!visited[v])
bfs(v);
void dfs(int s){
Stack<Integer> stack = new Stack<>();
stack.add(s);
visited[s] = true;
while(!stack.isEmpty()) {
int v = stack.remove();
order.add(v);
for (int w : G.adj(v))
if (!visited[w]) {
stack.add(w);
visited[w] = true;
}
}
}
它们的非递归代码的区别只在于数据结构使用的不同，一个用栈一个用队列，而其它的逻辑完全一样。也就只是在容器中循环取元素的顺序不同而已。
