1. 优先级与优先级数

广度优先搜索(BFS)在每一步迭代中会优先考查更早被发现的顶点，深度优先搜索(DFS)会优先考查最后被发现的顶点。两种选择策略都等效于给所有顶点赋予不同的优先级，而且随着算法的推进不断调整；而每一步迭代所选取的顶点，都是当前优先级最高者。

按照这种理解，包括BFS和DFS在内的几乎所有的图搜索算法，都可以纳入统一的框架，即优先级搜索（priority-first search，PFS）。

在《图基础知识整理和代码实现》一文中，我们为顶点类Vertex设置了一个int型的成员变量priority（优先级数），并提供了get和set方法用于顶点优先级数的读取和修改。（这里我们约定优先级数越大的顶点优先级越低，初始状态下priority设置为int的最大值）

2. 优先级搜索的基本框架

优先级搜索算法的框架可具体实现为如下代码。

/**
 * 功能描述: 优先级搜索框架
 * @param: updater 优先级更新器，负责对顶点的优先级进行更新，不同的更新策略可以实现不同的算法
 * @param: visitedOperation 对优先访问的节点的访问后，执行的操作，由用户自己实现
 * @return:
 * @auther: 杨赟
 * @date: 2018/10/3 20:52
 */
public void pfs(Tv data, PriorityUpdater<Tv> updater, VisitedOperation<Tv> visitedOperation) {
    Integer i = hashMap.get(data);//根据顶点key找到顶点在向量中的秩
    if(i == null) return;//不存在该顶点，立即返回
    reset(); int v = i;//初始化
    do {//逐一检查所有顶点
        if(status(v) == VStatus.UNDISCOVERED) //一旦遇到未发现顶点
            PFS(v, updater, visitedOperation);//即从该顶点出发启动一次PFS
    }while (i!=(v=(++v%n)));//按序号检查，故不漏补重
}
private void PFS(int i, PriorityUpdater<Tv> updater, VisitedOperation<Tv> visitedOperation) {
    Vertex<Tv> vertex = V.get(i);
    vertex.setPriority(0); //0的优先级最大
    vertex.setStatus(VStatus.VISITED);//当前顶点已访问
    vertex.setParent(-1);//当前顶点没有夫顶点
    visitedOperation.doSomething(vertex);//访问完顶点后干什么
    while (true){
        for (int j=firstNeighbor(i);j>-1;j=nextNeighbor(i,j)){//遍历所有邻居
            updater.updatePriority(this,i,j);//对所有邻居的优先级进行更新
        }
        for (int shortest = Integer.MAX_VALUE,j=0;j<n;j++){//遍历所有顶点
            if(status(j) == VStatus.UNDISCOVERED){//如果顶点未被发现
                if(shortest > priority(j)){
                    shortest = priority(j);
                    i = j;//在所有未被发现的顶点中找出优先级数最小，即优先级最大的顶点
                }
            }
        }
        if(status(i) == VStatus.VISITED) break;//连通域内的所有顶点都已被访问，结束
        V.get(i).setStatus(VStatus.VISITED);  //顶点设置为已访问状态
        E.get(V.get(i).getParent()).get(i).setType(EType.TREE);//该顶点的父顶点与该顶点之间为TREE边
        visitedOperation.doSomething(V.get(i));//访问完顶点后干什么
    }
}

优先级更新器PriorityUpdater<Tv>接口（借助PriorityUpdater<Tv>接口，使算法设计者得以根据不同的问题需求，实现相应地更新策略）。

package com.whut.DataStructure.graph.interfaces;
import com.whut.DataStructure.graph.GraphMatrix;
/**
 * @Auther: 杨赟
 * @Date: 2018/10/2 20:56
 * @Description:
 */
public interface PriorityUpdater<Tv> {
    void updatePriority(GraphMatrix<Tv> graph, int vertex, int neighbor);
}

访问操作器VisitedOperation<Tv>接口（借助VisitedOperation<Tv>接口，使算法设计者可以按顶点的访问次序，对访问到的顶点进行一定的操作，比如打印该顶点）。

package com.whut.DataStructure.graph.interfaces;
import com.whut.DataStructure.graph.entity.Vertex;
/**
 * @Auther: 杨赟
 * @Date: 2018/10/3 8:58
 * @Description: 访问顶点后的自定义功能接口
 */
public interface VisitedOperation<Tv> {
    void doSomething(Vertex<Tv> vertex);        //访问顶点后，干点什么
}

可见，PFS搜索的基本过程和功能与常规的图搜索算法一样，也是以迭代方式逐步引入顶点和边，最终构成一颗遍历树（或遍历森林）。而每次迭代中总是引入优先级数最小（优先级最大）的顶点，并按照不同的策略更新其邻接顶点的优先级数。下面借助该框架，实现BFS和DFS。

3. 基于PFS实现BFS和DFS

/**
 * 功能描述: 基于PFS的BFS实现
 * @param: visitedOperation 访问
 * @return:
 * @auther: 杨赟
 * @date: 2018/10/4 11:41
 */
public void bfs2(Tv data, VisitedOperation<Tv> visitedOperation){
    pfs(data, new PriorityUpdater<Tv>() {
        @Override
        public void updatePriority(GraphMatrix<Tv> graph, int vertex, int neighbor) {
            if(graph.status(neighbor) == VStatus.UNDISCOVERED){
                if(graph.priority(neighbor) > graph.priority(vertex)+1){
                    graph.setPriority(neighbor,graph.priority(vertex)+1);
                    graph.setParent(neighbor,vertex);//越晚发现，优先级数越大，优先级越低
                }
            }
        }
    }, visitedOperation);
}
/**
 * 功能描述: 基于PFS的DFS实现
 * @param: 
 * @return: 
 * @auther: 杨赟
 * @date: 2018/10/4 11:57
 */
public void dfs2(Tv data, VisitedOperation<Tv> visitedOperation){
    pfs(data, new PriorityUpdater<Tv>() {
        @Override
        public void updatePriority(GraphMatrix<Tv> graph, int vertex, int neighbor) {
            if(graph.status(neighbor) == VStatus.UNDISCOVERED){
                if(graph.priority(neighbor) > graph.priority(vertex)-1){
                    graph.setPriority(neighbor,graph.priority(vertex)-1);
                    graph.setParent(neighbor,vertex);//越晚发现，优先级数越小，优先级越高
                }
            }
        }
    }, visitedOperation);
}

PFS搜索由两层循环构成，其中内层循环又含并列的两个循环，在基于PFS的BFS和DFS算法中，updatePriority函数的执行需要常数的时间。所以算法的总体复杂度为O(n²)。

4. 测试

采用《图基础知识整理和代码实现》）一文中的例子对新的BFS和DFS算法进行测试

private static void bfsTest(String start) {
    GraphMatrix<String> graphMatrix = new GraphMatrix<String>();
    graphMatrix.insert("A");
    graphMatrix.insert("B");
    graphMatrix.insert("C");
    graphMatrix.insert("D");
    graphMatrix.insert("E");
    graphMatrix.insert("F");
    graphMatrix.insert("G");
    graphMatrix.insert("S");
    graphMatrix.insert("S","A",new Edge(1,1));
    graphMatrix.insert("S","C",new Edge(1,2));
    graphMatrix.insert("S","D",new Edge(1,3));
    graphMatrix.insert("A","C",new Edge(1,4));
    graphMatrix.insert("A","E",new Edge(1,5));
    graphMatrix.insert("C","B",new Edge(1,6));
    graphMatrix.insert("D","B",new Edge(1,7));
    graphMatrix.insert("E","F",new Edge(1,8));
    graphMatrix.insert("E","G",new Edge(1,9));
    graphMatrix.insert("G","F",new Edge(1,10));
    graphMatrix.insert("G","B",new Edge(1,11));
    VisitedOperation<String> operation = new VisitedOperation<String>() {
        @Override
        public void doSomething(Vertex<String> vertex) {
            System.out.print(" "+vertex.getData());
        }
    };
    System.out.print("bfs2结果:");
    graphMatrix.bfs2(start,operation);
    System.out.println("");
}
private static void dfsTest(String start) {
    GraphMatrix<String> graphMatrix = new GraphMatrix<String>();
    graphMatrix.insert("A");
    graphMatrix.insert("B");
    graphMatrix.insert("C");
    graphMatrix.insert("D");
    graphMatrix.insert("E");
    graphMatrix.insert("F");
    graphMatrix.insert("G");
    graphMatrix.insert("A","B",new Edge(1,1));
    graphMatrix.insert("A","F",new Edge(1,2));
    graphMatrix.insert("A","C",new Edge(1,3));
    graphMatrix.insert("B","C",new Edge(1,4));
    graphMatrix.insert("F","G",new Edge(1,5));
    graphMatrix.insert("G","C",new Edge(1,6));
    graphMatrix.insert("D","A",new Edge(1,7));
    graphMatrix.insert("D","E",new Edge(1,8));
    graphMatrix.insert("E","F",new Edge(1,9));
    graphMatrix.insert("G","A",new Edge(1,10));
    VisitedOperation<String> operation = new VisitedOperation<String>() {

        @Override
        public void doSomething(Vertex<String> vertex) {
            System.out.print(" "+vertex.getData());
        }
    };
    System.out.print("dfs2结果:");
    graphMatrix.dfs2(start, operation);
    System.out.println("");
}
public static void main(String[] args) {
    bfsTest("S");
    dfsTest("A");
    dfsTest("D");
}

《图基础知识整理和代码实现》）一文中的遍历结果如图1所示，本文采用的基于PFS的DFS和BFS运行结果如图2所示，比较可以发现该算法是正确的。

图1.前文的运行结果 图2.本文的运行结果