图的广度优先遍历与无权图的最短路径

点击这里，前提知晓...

一、图的广度优先遍历

和树的广度优先遍历的思想一样，使用队列作为辅助的数据结构

---

广度优先遍历.png

上述广度优先遍历的结果为0 1 2 5 6 3 4，

1). 特征

1. 相对于遍历的起始点的各个点，先遍历的节点的距离要小于等于后遍历的节点！(无权图)，所以广度优先遍历可以求出无权图的最短路径。

二、广度优先遍历与最短路径寻找的实现

1. 代码实现

其他类的实现请点击文章开始的链接！

import java.util.LinkedList;
import java.util.Queue;
import java.util.Stack;
import java.util.Vector;

/**
 * @author Liucheng
 * @since 2019-10-13
 */
public class ShortestPath {

    private Graph G;   // 图的引用
    private int s;     // 起始点
    private boolean[] visited;  // 记录dfs的过程中节点是否被访问
    private int[] from;         // 记录路径, from[i]表示查找的路径上i的上一个节点
    private int[] ord;          // 记录路径中节点的次序。ord[i]表示i节点在路径中的次序。

    /**
     * 构造函数
     */
    public ShortestPath(Graph G, int s) {
        assert s >= 0 && s < G.V();

        this.G = G;     // 图的引用
        this.s = s;     // 起始点
        this.visited = new boolean[G.V()]; // 记录dfs的过程中节点是否被访问
        this.from = new int[G.V()];        // 记录路径, from[i]表示查找的路径上i的上一个节点
        this.ord = new int[G.V()];         // 记录路径中节点的次序。ord[i]表示i节点在路径中的次序。

        for (int i = 0; i < G.V(); i++) {
            visited[i] = false;
            from[i] = -1;
            ord[i] = -1;
        }

        this.bfs(s);
    }

    /**
     * 广度优先遍历
     * 寻路算法，寻找图graph从s点到其他点的路径
     */
    public void bfs(int v) {
        // 广度优先遍历+最短路径算法
        Queue<Integer> q = new LinkedList<>();
        q.add(v);
        visited[v] = true;
        ord[v] = 0;
        while (!q.isEmpty()) {
            int vO = q.remove();
            for (Integer i : G.adj(vO)) {
                if (!visited[i]) {
                    q.add(i);
                    visited[i] = true;
                    from[i] = vO;
                    ord[i] = ord[vO] + 1;
                }
            }
        }
    }

    /**
     * 查询从s点到w点是否有路径
     */
    public boolean hasPath(int w) {
        assert w >=0 && w < G.V();

        return visited[w];
    }

    /**
     * 查询从s点到w点的路径，存放在vec中
     */
    public Vector<Integer> path(int w) {
        assert hasPath(w);

        Stack<Integer> s = new Stack<>();
        // 通过from数字逆向查找从s到w的路径，存放到栈中
        int p = w;
        while (p != -1) {
            s.push(p);
            p = from[p];
        }

        // 从栈中依次取出元素，获得顺序的从s到w的路径
        Vector<Integer> res = new Vector<>();
        while (!s.empty()) {
            res.add(s.pop());
        }

        return res;
    }

    /**
     * 打印出从s点到w点的路径
     */
    public void showPath(int w) {
        assert w >= 0 && w < G.V();

        Vector<Integer> path = this.path(w);
        for (int i = 0; i < path.size(); i++) {
            System.out.print(path.elementAt(i));
            if (i == path.size() - 1) {
                System.out.println();
            } else {
                System.out.print(" -> ");
            }
        }
    }

    /**
     * 查看从s点到w点的最短路径的长度
     * 若从s到w不可达，返回-1
     */
    public int length(int w) {
        assert w >= 0 && w < G.V();

        return ord[w];
    }

    /**
     * 测试无权图最短路径算法
     */
    public static void main(String[] args) {
        String filename = Thread.currentThread().getContextClassLoader().getResource("testG.txt").getPath();
        SparseGraph g = new SparseGraph(7, false);
        ReadGraph readGraph = new ReadGraph(g, filename);
        g.show();

        // 比较使用深度优先遍历和广度优先遍历获得路径的不同
        // 广度优先遍历获得的是无权图的最短路径
        Path dfs = new Path(g,0);
        System.out.print("DFS : ");
        dfs.showPath(6);

        ShortestPath bfs = new ShortestPath(g,0);
        System.out.print("BFS : ");
        bfs.showPath(6);
    }
}

2. testG.txt文件内容

7 8
0 1
0 2
0 5
0 6
3 4
3 5
4 5
4 6

3. 执行结果

vertex 0:   1   2   5   6   
vertex 1:   0   
vertex 2:   0   
vertex 3:   4   5   
vertex 4:   3   5   6   
vertex 5:   0   3   4   
vertex 6:   0   4   
DFS : 0 -> 5 -> 3 -> 4 -> 6
BFS : 0 -> 6

三、图的广度优先遍历的复杂度分析

1. 稀疏图（邻接表）：
   • O(V + E) 表示点的个数加上边的个数
2. 稠密图（邻接矩阵 ：
   • O(V^2) 表示边的次方，因为稠密图计算每一个节点相邻不为空的所有情况