Java学习者论坛

 找回密码
 立即注册

QQ登录

只需一步,快速开始

手机号码,快捷登录

恭喜Java学习者论坛(https://www.javaxxz.com)已经为数万Java学习者服务超过8年了!积累会员资料超过10000G+
成为本站VIP会员,下载本站10000G+会员资源,购买链接:点击进入购买VIP会员
JAVA高级面试进阶视频教程Java架构师系统进阶VIP课程

分布式高可用全栈开发微服务教程

Go语言视频零基础入门到精通

Java架构师3期(课件+源码)

Java开发全终端实战租房项目视频教程

SpringBoot2.X入门到高级使用教程

大数据培训第六期全套视频教程

深度学习(CNN RNN GAN)算法原理

Java亿级流量电商系统视频教程

互联网架构师视频教程

年薪50万Spark2.0从入门到精通

年薪50万!人工智能学习路线教程

年薪50万!大数据从入门到精通学习路线年薪50万!机器学习入门到精通视频教程
仿小米商城类app和小程序视频教程深度学习数据分析基础到实战最新黑马javaEE2.1就业课程从 0到JVM实战高手教程 MySQL入门到精通教程
查看: 1708|回复: 0

[算法学习]有向无环图(1):无后继的顶点优先拓扑排序

[复制链接]
  • TA的每日心情
    开心
    2021-3-12 23:18
  • 签到天数: 2 天

    [LV.1]初来乍到

    发表于 2014-12-7 00:07:08 | 显示全部楼层 |阅读模式
    对一个有向无环图(Directed Acyclic Graph简称DAG)G进行拓扑排序,是将G中所有顶点排成一个线性序列,使得图中任意一对顶点u和v,若<u,v> ∈E(G),则u在线性序列中出现在v之前。
    通常,这样的线性序列称为满足拓扑次序(TopoiSicai Order)的序列,简称拓扑序列
    注意:
    ①若将图中顶点按拓扑次序排成一行,则图中所有的有向边均是从左指向右的。
    ②若图中存在有向环,则不可能使顶点满足拓扑次序。
    ③一个DAG的拓扑序列通常表示某种方案切实可行。

    【例】一本书的作者将书本中的各章节学习作为顶点,各章节的先学后修关系作为边,构成一个有向图。按有向图的拓扑次序安排章节,才能保证读者在学习某章节时,其预备知识已在前面的章节里介绍过。
    ④一个DAG可能有多个拓扑序列。
    【例】对图G9进行拓扑排序,至少可得到如下的两个(实际远不止两个)拓扑序列:C0,C1,C2,C4,C3,C5,C7,C8,C6和C0,C6,C7,C1,C4,C2,C3,C8,C5。
       
      
       
       
         
       

         
       
      


    ⑤当有向图中存在有向环时,拓扑序列不存在

    无后继的顶点优先拓扑排序方法

    1、思想方法

    该方法的每一步均是输出当前无后继(即出度为0)的顶点。对于一个DAG,按此方法输出的序列是逆拓扑次序。因此设置一个栈(或向量)T来保存输出的顶点序列,即可得到拓扑序列。若T是栈,则每当输出顶点时,只需做人栈操作,排序完成时将栈中顶点依次出栈即可得拓扑序列。若T是向量,则将输出的顶点从T[n-1]开始依次从后往前存放,即可保证T中存储的顶点是拓扑序列。

    2、抽象算法描述
    算法的抽象描述为:
    NonSuccFirstTopSort(G){//优先输出无后继的顶点
       while(G中有出度为0的顶点)do {
         从G中选一出度为0的顶点v且输出v;
        从G中删去v及v的所有人边
      }
       if(输出的顶点数目<|V(G)|)
       Error("G中存在有向环,排序失败!");
    }

    代码:
    1. //有向无环图的拓扑排序:
    2. //第一步:在图中找到一个没有后继的顶点;
    3. //第二步:从图中删除这个顶点,在列表的前面插入顶点的标记
    4. //第三步:重复第一和第二步,直到所有顶点都从图中删除。这时列表显示的顶点顺序就是拓扑排序的结果。
    5. class Vertex {
    6.    public char label;      
    7.    public Vertex(char lab)  
    8.       { label = lab; }
    9.    }  
    10. class Graph{
    11.    private final int MAX_VERTS = 20;
    12.    private Vertex vertexList[]; //顶点列表
    13.    private int adjMat[][];     //邻接矩阵
    14.    private int nVerts;          // 当前的顶点数
    15.    private char sortedArray[];// 已经排序的顶点
    16. Graph() {
    17.       vertexList = new Vertex[MAX_VERTS];
    18.                                        
    19.       adjMat = new int[MAX_VERTS][MAX_VERTS];
    20.       nVerts = 0;
    21.       for(int j=0; j< MAX_VERTS; j++)     
    22.          for(int k=0; k< MAX_VERTS; k++)
    23.             adjMat[j][k] = 0;
    24.       sortedArray = new char[MAX_VERTS];  
    25.       }  
    26.    public void addVertex(char lab)//在图中增加一个顶点
    27.       {
    28.       vertexList[nVerts++] = new Vertex(lab);
    29.       }
    30.    public void addEdge(int start, int end)//在图中增加一条边
    31.       {
    32.       adjMat[start][end] = 1;
    33.       }
    34.    public void displayVertex(int v)
    35.       {
    36.       System.out.print(vertexList[v].label);
    37.       }
    38.    public void topo(){
    39.       int orig_nVerts = nVerts;  
    40.       while(nVerts > 0){
    41.         
    42.          int currentVertex = noSuccessors();//找一个没有后继的顶点(出度为0)
    43.          
    44.          if(currentVertex == -1){      // 没有找到,一定是一个环
    45.             System.out.println("ERROR: Graph has cycles");
    46.             return;
    47.          }
    48.          // 找到了,插入
    49.          sortedArray[nVerts-1] = vertexList[currentVertex].label;
    50.          deleteVertex(currentVertex);  // 删除顶点
    51.       }  
    52.       // 显示拓扑排序的结果
    53.       System.out.print("Topologically sorted order: ");
    54.       for(int j=0; j< orig_nVerts; j++)
    55.          System.out.print( sortedArray[j] );
    56.       System.out.println("");
    57.       }  
    58.    public int noSuccessors(){ // 从邻接矩阵中找一个没有后继的顶点(出度为0的)                  
    59.       boolean isEdge;  
    60.       for(int row=0; row< nVerts; row++){
    61.          isEdge = false;                 
    62.          for(int col=0; col< nVerts; col++){
    63.             if( adjMat[row][col] > 0 ){                        
    64.                isEdge = true;
    65.                break;                  
    66.                }                     
    67.          }                        
    68.          if( !isEdge )   
    69.             return row;   
    70.       }
    71.       return -1;      
    72.    }  
    73.    //删除一个顶点。顶点从vertexList[]数组删除,后面的顶点向前移动填补空位,同样的,顶点所在的行列
    74.   //从邻接矩阵中删除,下面的行的右面的列移动来填补空位。
    75.    public void deleteVertex(int delVert){
    76.       if(delVert != nVerts-1) {// 如果不是最后一个顶点
    77.          for(int j=delVert; j< nVerts-1; j++)
    78.             vertexList[j] = vertexList[j+1];
    79.          // 在邻接矩阵中删除一行
    80.          for(int row=delVert; row< nVerts-1; row++)
    81.             moveRowUp(row, nVerts);
    82.          // 在邻接矩阵中删除一列
    83.         for(int col=delVert; col< nVerts-1; col++)
    84.             moveColLeft(col, nVerts-1);
    85.       }
    86.       nVerts--;                  
    87.    }
    88.    private void moveRowUp(int row, int length){
    89.       for(int col=0; col< length; col++)
    90.          adjMat[row][col] = adjMat[row+1][col];
    91.       }
    92.    private void moveColLeft(int col, int length){
    93.       for(int row=0; row< length; row++)
    94.          adjMat[row][col] = adjMat[row][col+1];
    95.       }
    96.    }  
    97. public class TopoApp {
    98.    public static void main(String[] args){
    99.       Graph theGraph = new Graph();
    100.       theGraph.addVertex("0");   
    101.       theGraph.addVertex("1");   
    102.       theGraph.addVertex("2");   
    103.       theGraph.addVertex("3");   
    104.       theGraph.addVertex("4");   
    105.       theGraph.addVertex("5");   
    106.       theGraph.addVertex("6");   
    107.       theGraph.addVertex("7");   
    108.       theGraph.addVertex("8");   
    109.       theGraph.addEdge(0, 6);   
    110.       theGraph.addEdge(0, 2);   
    111.       theGraph.addEdge(6, 7);     
    112.       theGraph.addEdge(7, 8);     
    113.       theGraph.addEdge(2, 3);     
    114.       theGraph.addEdge(1, 2);     
    115.       theGraph.addEdge(1, 4);   
    116.       theGraph.addEdge(4, 5);  
    117.       theGraph.addEdge(4, 3);   
    118.       theGraph.addEdge(3, 5);
    119.       theGraph.addEdge(3, 8);               
    120.    
    121.       theGraph.topo();            // do the sort
    122.       }  
    123.    }  
    复制代码
    运行结果:
    C:        est>java TopoApp
    Topologically sorted order: 067142385


      
      
       
       

         
       

         
       
      
    复制代码

    源码下载:http://file.javaxxz.com/2014/12/7/000708140.zip
    回复

    使用道具 举报

    您需要登录后才可以回帖 登录 | 立即注册

    本版积分规则

    QQ|手机版|Java学习者论坛 ( 声明:本站资料整理自互联网,用于Java学习者交流学习使用,对资料版权不负任何法律责任,若有侵权请及时联系客服屏蔽删除 )

    GMT+8, 2024-3-29 17:54 , Processed in 0.359116 second(s), 46 queries .

    Powered by Discuz! X3.4

    © 2001-2017 Comsenz Inc.

    快速回复 返回顶部 返回列表