邻接矩阵的BFS、Dijkstra算法学习

最近算法课的学到了Graph，于是老师就布置了一个图的最短路径的算法作业。在完成了作业之后，把自己学(写)的的两个算法整理整理，便于之后复习查看。

导言

学到Graph之后，有几种经典的数据结构来存储。

• 边的列表
• 邻接矩阵
• 邻接表
• 邻接集

由于初学，现在只钻研了邻接矩阵，且邻接矩阵的可读性和操作性都非常高，以此作为例子来学习比较好理解和把握。

下面是核心Class的概览，完整的代码在Matrix Class - Github。

public class Matrix {
    private int mSize;
    private int[][] mMatrix;
    private static final int INF = Integer.MAX_VALUE;   // INFINITE value

    public Matrix(int pSize){...}

    public void connect(String X, String Y, String Weight){...}

    public String BreadthFirstSearch(String pStartPoint, String pEndPoint){...}

    public String dijkstraSearch(String pStartPoint, String pEndPoint){...}

}

下面的内容皆节选自Matrix Class。

广度优先搜索

广度优先搜索算法（英语：Breadth-First-Search），简称BFS，是一种图形搜索算法。
简单的说，BFS是从根节点开始，沿着树的宽度遍历树的节点。
如果所有节点均被访问，则算法中止。

搜索步骤如下

1. 首先将根(起始)节点放入队列中。
2. 从队列中取出第一个节点，并检验它是否为目标。
   • 如果找到目标，则结束搜寻并回传结果。
   • 否则将它所有尚未检验过的直接子节点加入队列中。
3. 若队列为空，表示整张图都检查过了——亦即图中没有欲搜寻的目标。结束搜寻并回传“找不到目标”。
4. 重复步骤2。

其实很好理解，就相当于一个迷宫，我们同时派出与起点相邻点个数的人(广度)去遍历迷宫。

走到一个点就留下标记，说明这个点已经走过了，直到迷宫联通区域内的所有点都走完了。

那么在这其中有一个重复路径的问题，假设 A: 1->2->4, B: 1->3->4，两者都到达了4怎么处理？

以先后来算，如果是A先标记的4，那么4的前驱(父节点)就是2，以先到的为主线继续探索。

也就是说，如果4节点的下一个节点是5，那么就是A去标记的，与此同时B就归入A了。即，A不变，B: 1->3 就算结束了。因为最短路径，先到的肯定最短；同时到的，两者取其一皆可。

接下来直接看代码，关键地方留有注释。

/**
 * Breadth First Search Algorithm
 * @param pStartPoint start point
 * @param pEndPoint end point
 * @return result
 */
public String BreadthFirstSearch(String pStartPoint, String pEndPoint){
    // 如果起点和终点相同，则直接返回 pStartPoint  pEndPoint
    if(Objects.equals(pStartPoint, pEndPoint)) return pStartPoint + "\t" + pEndPoint;

    int[] edgeTo = new int[mSize];
    boolean[] marked = new boolean[mSize];
    for (int i = 0; i < mSize;i++) edgeTo[i] = -1;
    // 设置所有点的前驱为-1，即没有访问过

    Queue<Integer> queue = new Queue<Integer>();
    int startPoint = Integer.parseInt(pStartPoint) - 1;
    int endPoint = Integer.parseInt(pEndPoint) - 1;
    // 转换成计算机计数法，从0开始

    marked[startPoint] = true;
    // 标记起点

    queue.enqueue(startPoint);
    while (!queue.isEmpty()){
        int v = queue.dequeue();
        for (int i = 0; i < mSize; i++){
            if(mMatrix[i][v] != 0){
                if(!marked[i]){
                    // 如果标记了，则说明该点走过了
                    // 如果没有，则标记该点
                    edgeTo[i] = v;
                    marked[i] = true;
                    queue.enqueue(i);
                }
            }
        }
    }
    int i = endPoint;
    String result = "";
    while (edgeTo[i] != startPoint){
        if(edgeTo[i] == -1){
            result = "-1\t";
            break;
        }
        int num = edgeTo[i] + 1;
        result = num + "\t" + result;
        i = edgeTo[i];
    }
    return pStartPoint + "\t" + result + pEndPoint;
}

空间复杂度
因为所有节点都必须被储存，因此BFS的空间复杂度为O(|V| + |E|)，其中|V|是节点的数目，而|E|是图中边的数目。
注：另一种说法称BFS的空间复杂度为O(B^M)，其中B是最大分支系数，而M是树的最长路径长度。由于对空间的大量需求，因此BFS并不适合解非常大的问题。

时间复杂度
最差情形下，BFS必须寻找所有到可能节点的所有路径，因此其时间复杂度为O(|V| + |E|)，其中|V|是节点的数目，而|E|是图中边的数目。

注：引用内容皆来自于维基百科。

Dijkstra路径搜索

Dijkstra算法使用了广度优先搜索解决非负权有向图的单源最短路径问题，算法最终得到一个最短路径树。
举例来说，如果图中的顶点表示城市，而边上的权重表示城市间开车行经的距离，该算法可以用来找到两个城市之间的最短路径。

搜索步骤如下

1. 初始化
   • 起始点外所有点皆未访问
   • 起始点外所有点的前驱(父节点)为起始点，起始点为-1
   • 起始点外所有点的最小权值为-1(未访问或不连通)，起始点为0
2. 开始循环所有的点，选择权值最小且没有访问过的点作为当前点，并标记当前点已访问
3. 循环计算与当前点相邻的点，如果当前点加上相邻点的权小于该点的最小权值(distTo[adj])，则覆写该点到起点的最小权值
4. 重复步骤(2)和(3)，直到遍历完所有顶点。

单纯的看上面的理论可能比较难以理解，下面通过实例来对该算法进行说明。

/**
 * Dijkstra Search Algorithm
 * @param pStartPoint start point
 * @param pEndPoint end point
 * @return result
 */
public String dijkstraSearch(String pStartPoint, String pEndPoint){
    // 如果起点和终点相同，则直接返回 pStartPoint  pEndPoint
    if(Objects.equals(pStartPoint, pEndPoint)) return pStartPoint + "\t" + pEndPoint;
    int[] distTo = new int[mSize];          // 判断是否经过这一点
    int[] previous = new int[mSize];        // 该点的前驱(父节点)
    boolean[] visited = new boolean[mSize]; // 该点到起点的最小权值(距离)

    // 计算机语言化，从0开始计数
    int startPoint = Integer.parseInt(pStartPoint) - 1;
    int endPoint = Integer.parseInt(pEndPoint) - 1;

    // 初始化状态
    for (int i = 0; i < mSize; i++) {
        visited[i] = false;         // 所有点皆未访问
        distTo[i] = INF;            // 所有点的最小权值INFINITE
        previous[i] = startPoint;   // 所有点的前驱(父节点)为起始点
    }

    distTo[startPoint] = 0;         // 起始点的最小权值为0
    previous[startPoint] = -1;      // 起始点的前驱(父节点)为-1
    visited[startPoint] = true;     // 标记起始点已被访问

    int current = startPoint;       // 初始化当前点
    for (int i = 1; i < mSize; i++){
        // Dijkstra算法的核心操作
        int min = INF;
        for (int j = 0; j< mSize; j++){
            if(!visited[j] && distTo[j] < min){
                // 寻找当前权值最小且没被访问过的点
                min = distTo[j];
                current = j;
            }
        }
        visited[current] = true;    // 设置该点为当前点
        for (int v = 0; v < mSize; v++){
            if(mMatrix[current][v] > 0 && 
                    distTo[v] > distTo[current] + mMatrix[current][v]){
                // 循环计算与当前点相邻的点
                // 如果当前点加上相邻点的权小于该点的最小权值(distTo[v])
                // 则覆写该点到起点的最小权值
                distTo[v] = distTo[current] + mMatrix[current][v];
                previous[v] = current;
            }
        }
    }

    int i = endPoint;
    String result = "";
    while (previous[i] != startPoint || distTo[i] == INF){
        if(previous[i] == -1 || distTo[i] == INF){
            result = "-1\t";
            break;
        }
        int num = previous[i] + 1;
        result = num + "\t" + result;
        i = previous[i];
    }
    return pStartPoint + "\t" + result + pEndPoint;
}

由于该代码基于的是邻接矩阵，所以时间复杂度为O(n^2)

注：引用内容皆来自于维基百科。

引用

Matrix Class - Github