从最小支撑树和最短路径树学习图的优先级搜索

待我称王封你为后i 2022-06-03 03:41 82阅读 0赞

在介绍最小支撑树和最短路径树之前，先对图的优先级搜索有个简单的了解，前面笔者介绍了[图的广度优先搜索算法][Link 1]和[图的深度优先搜索][Link 2]。这两种搜索虽然各有特点，但基本结构却几乎相同。都需要通过迭代逐一发现各顶点，将其归纳到遍历树中做相应的处理。两种算法的唯一差别在于，如何选取下一个节点的问题。对于广度优先搜索则为选取更早被发现的节点，而深度优先搜索则为最后被发现的节点。

如果将广度优先搜索或深度优先搜索选取下一个节点的策略抽象为根据优先级来选取。**每一步迭代选取的节点都是当前所有邻居中优先级的一个极值(或优先级最高，或优先级最低)。**因此，这种按照优先级来选取下一个节点的搜索过程就称为优先级搜索—PFS，亦称为最佳优先搜索。

按照上述的思路，抽象出PFS搜索的框架如下：  
**对节点添加优先级数：priority字段，默认值为Integer.MAX\_VALUE。优先级数越高，优先级越低**

private int priority = Integer.MAX_VALUE; //优先级数越高，优先级越低
        public int getPriority() {
            return priority;
        }
    
        public void setPriority(int priority) {
            this.priority = priority;
        }

PFS：

public void pfsTree(int index){
          int v = index;
          do{
              if(allNodes[v].getStatus() == 0 ){
                  this.pfs(v);
              }
          }while(index != (v = (++v%size)));//存在孤立节点，继续一次pfs遍历
      }
    
      public void pfs(int v){
         this.allNodes[v].setPriority(0);//该次pfs树中优先级最高的树
         this.allNodes[v].setStatus(2); //VISITED
         this.allNodes[v].setParent(-1);
    
         while(true){
             //遍历v的所有邻居，根据不同的策略，基于不同的优先级
              for(int i=0;i<size;i++) {
                  if(getEdge(v, i)!=null) {
                      //如果节点i尚未被发现
                      if(allNodes[i].getStatus() == 0) {
                          //根据不同策略来决定i的优先级
                          prioUpdater(v, i);
                      }
                  }
              }
              //从所有未被发现的节点中，找出与所有已发现的节点中，优先级树最低，优先级最高的节点
              int maxPriority = Integer.MAX_VALUE;
              for(int i=0;i<size;i++){
                  if(this.allNodes[i].getStatus() == 0 && maxPriority > this.allNodes[i].getPriority()){
                     maxPriority = this.allNodes[i].getPriority();
                     v = i;
                  }
              }
    
              //如果改成遍历中，v已经被发现。最所有的节点均全部被发现
              if(this.allNodes[v].getStatus() == 2) break;
              //如果发现该节点
              this.allNodes[v].setPriority(2);
              int parentV = this.allNodes[v].getParent();
              this.nodeGraphs[parentV][v].setType(1);
             //继续从该节点开始，访问其所有邻居
         }
      }
    
      //具体的决定优先级的策略,不同的算法优先级的策略不同
      private void prioUpdater(int v, int vNext){
    
      }

### 优先级生成策略 ###

要套用优先级搜索算法，就必须指定一种节点优先级生成策略。笔者前面提到，如果将之前介绍的广度优先搜索和深度优先搜索套用该框架，则优先级生成策略如下所示：

>  *  图的广度优先搜索中，越早被访问的节点，优先级越高
>  *  图的深度优先搜索中，越晚被访问的节点，优先级越高

### 以图的两个经典算法为例，深入理解优先级搜索 ###

#### 最小支撑树 ####

![某个连通图能够覆盖图G的所有节点，这称为支撑树][G]

如果某个连通图能够覆盖图的所有节点，这该连通图称为该图的支撑树。根据图的相关性质，不难想到，某个完全图的支撑树不唯一，但如果是n个节点，则支撑树的边均为n-1。

如果该图的边存在权重，则在某个图的所有支撑树中，各边权重的总和最小的支撑树即为最小支撑树，同样的，最小支撑树夜可能不唯一。

在某些应用中如网络架构设计，聚类分析等，边的权重对应于某种可量化的成本，因此对应于优化问题的基本模型，最小支撑树的价值不言而喻。

**Prim算法**  
Prim算法为一种生成最小支撑树的高效率算法。当然，也可以通过先生成图的所有支撑树，在找出其中权重最小的，但这效率可想而知。

在图G = (V;E)中，顶点集V的任一平凡子集U及其补集V\\U都构成G的一个割。若边uv满足：节点u属于集合U，但v不属于集合U，则称为该割的一条跨越边。

Prim算法的正确性基于：**最小支撑树总是会采用联接每一割的最短跨越边**

基于以上理论，可迭代出如下一个算法：每一步迭代之前都假设已经得到最小支撑树T的一颗子树T。于是，如果将T以及其现对于原图G的补集G\\T视作一个割，则找到该割中的一条最短跨越边后就可将T扩展为更大一个子树。如此迭代便可得到一个最小支撑树。

以一个包含8个顶点和15条边的无向图G为例，给出Prim算法的执行过程：

![这里写图片描述][SouthEast]  
![这里写图片描述][SouthEast 1]  
![这里写图片描述][SouthEast 2]

代码实现：

//最小支撑树
      public void pfsTreePrim(int index){
          int v = index;
          do{
              if(allNodes[v].getStatus() == 0 ){
                  this.pfsPrim(v);
              }
          }while(index != (v = (++v%size)));
      }
    
      //最小支撑树
      public void pfsPrim(int v){
         this.allNodes[v].setPriority(0);//该次pfs树中优先级最高的树
         this.allNodes[v].setStatus(2); //VISITED
         this.allNodes[v].setParent(-1);
    
         while(true){
             //遍历v的所有邻居，根据不同的策略，基于不同的优先级
              for(int i=0;i<size;i++) {
                  if(getEdge(v, i)!=null) {
                      //如果节点i尚未被发现
                      if(allNodes[i].getStatus() == 0) {
                          prioUpdaterForPrim(v, i);
                      }
                  }
              }
              //从所有未被发现的节点中，找出与所有已发现的节点中，优先级树最低，优先级最高的
              int maxPriority = Integer.MAX_VALUE;
              for(int i=0;i<size;i++){
                  if(this.allNodes[i].getStatus() == 0 && maxPriority > this.allNodes[i].getPriority()){
                     maxPriority = this.allNodes[i].getPriority();
                     v = i;
                  }
              }
              if(this.allNodes[v].getStatus() == 2) break;
              this.allNodes[v].setPriority(2);
              int parentV = this.allNodes[v].getParent();
              this.nodeGraphs[parentV][v].setType(1);
         }
      }
    
      //最小支撑树
      private void prioUpdaterForPrim(int v, int vNext){
          if(this.allNodes[vNext].getStatus() == 0){
              int vPriority = this.allNodes[vNext].getPriority();
              int weight = this.nodeGraphs[v][vNext].getWeight();
              //将边v—>VNext的权重视为v的优先级
              if(vPriority > weight){
                  this.allNodes[vNext].setPriority(weight);
                  this.allNodes[vNext].setParent(v);
              }
    
          }
      }

#### 最短路径树 ####

如果使用有权图来代表真实的交通，网络传输等信息，则各边的权重可能代表运输，通信成本等。我们关心的这一类问题，可概括为：  
**有权图G=(V,E) ,对于V中的节点s和v，s到v的最短路径的权重之和是多少？包括哪些边？**

最短路径具有单调性，如果s->v的最低路径为p，则对于路径p上的任何一个节点x，x->v的路径也一定是最短路径，否则p不为最短路径树。

图G中，一个节点到其他所有节点的最短路径即为最短路径树。根据最短路径的单调性可知，最短路径一定不存在环路。

Dijkstra算法：  
与Prim算法一致，它也可以归为优先级搜索的框架,但优先级数的更新策略不同。  
对于s->v的边，假设其权重为w。则v的优先级数为s的优先级数与w的和。

//最短路径
      public void pfsTreeDijkstra(int index){
          int v = index;
          do{
              if(allNodes[v].getStatus() == 0 ){
                  this.pfsPrim(v);
              }
          }while(index != (v = (++v%size)));
      }
    
      //最短路径
      public void pfsDijkstra(int v){
         this.allNodes[v].setPriority(0);//该次pfs树中优先级最高的树
         this.allNodes[v].setStatus(2); //VISITED
         this.allNodes[v].setParent(-1);
    
         while(true){
             //遍历v的所有邻居，根据不同的策略，基于不同的优先级
              for(int i=0;i<size;i++) {
                  if(getEdge(v, i)!=null) {
                      //如果节点i尚未被发现
                      if(allNodes[i].getStatus() == 0) {
                          prioUpdaterForPrim(v, i);
                      }
                  }
              }
              //从所有未被发现的节点中，找出与所有已发现的节点中，优先级树最低，优先级最高的
              int maxPriority = Integer.MAX_VALUE;
              for(int i=0;i<size;i++){
                  if(this.allNodes[i].getStatus() == 0 && maxPriority > this.allNodes[i].getPriority()){
                     maxPriority = this.allNodes[i].getPriority();
                     v = i;
                  }
              }
              if(this.allNodes[v].getStatus() == 2) break;
              this.allNodes[v].setPriority(2);
              int parentV = this.allNodes[v].getParent();
              this.nodeGraphs[parentV][v].setType(1);
         }
      }
    
      //最短路径
      private void prioUpdaterForDijkstra(int v, int vNext){
          if(this.allNodes[vNext].getStatus() == 0){
              int vPriority = this.allNodes[vNext].getPriority();
              int weight = this.allNodes[v].getPriority()+this.nodeGraphs[v][vNext].getWeight();
              if(vPriority > weight){
                  this.allNodes[vNext].setPriority(weight);
                  this.allNodes[vNext].setParent(v);
              }
          }
      }

### 优先级搜索的复杂度 ###

优先级更新方法只需常数级时间，但PSF搜索由两重循环构成，故复杂度为n的平方

[Link 1]: http://blog.csdn.net/canot/article/details/78705621
[Link 2]: http://blog.csdn.net/canot/article/details/78705704
[G]: /images/20220603/b0efde78fad743398773d22484e355e8.png
[SouthEast]: /images/20220603/60b96ffcf56b4be4889cfadf98744d5f.png
[SouthEast 1]: /images/20220603/a327bb7af017409784af87801e168102.png
[SouthEast 2]: /images/20220603/e349c81f29914f4c9114891347485995.png