有向图的拓扑排序

拓扑排序是可以用图模拟的另一种操作方式。

  • 他可用于表示一种情况,即某些项目或事件必须按照某种顺序排列发生。

基本思想:

  • 步骤1、找到一个没有后继的顶点
  • 步骤2、从图中删除这个顶点,在列表的前面插入顶点标记 以下为java源码:
/**
 * @author hasee
 * @TIME 2017年5月4日
 * 有向图的拓补排序
 * 步骤1、找到一个没有后继的顶点
 * 步骤2、从图中删除这个顶点,在列表的前面插入顶点标记
 */
public class TopoApp {
    //测试
    public static void main(String[] args) {
        // TODO Auto-generated method stub
        Graph02 theGraph = new Graph02();
        theGraph.addVertex('A');
        theGraph.addVertex('B');
        theGraph.addVertex('C');
        theGraph.addVertex('D');
        theGraph.addVertex('E');
        theGraph.addVertex('F');
        theGraph.addVertex('G');
        theGraph.addVertex('H');
        theGraph.addEdge(0, 3);//AD
        theGraph.addEdge(0, 4);//AE
        theGraph.addEdge(1, 4);//BE
        theGraph.addEdge(2, 5);//CF
        theGraph.addEdge(3, 6);//DG
        theGraph.addEdge(4, 6);//EG
        theGraph.addEdge(5, 7);//FH
        theGraph.addEdge(6, 7);//GH
        theGraph.topo();
        }
}
/**
 * 有一种拓扑图是拓扑排序是做不到的,那就是有环的情况,所以需要判断是否为环
 */
/**
 * @author hasee
 * @TIME 2017年5月4日
 * 保存顶点信息的类
 */
class Vertex{
    public char label;
    public Vertex(char lab){
        this.label = lab;
    }
}
class Graph02{
    private final int MAX_VRERTS = 20;
    private Vertx vertxList[];//包含所有的节点信息
    private int adjMat[][];//邻接矩阵
    private int nVert;//当前vertxList的指向下标
    private char sortedArray[];//存储
    //初始化
    public Graph02(){
        vertxList = new Vertx[MAX_VRERTS];
        adjMat = new int[MAX_VRERTS][MAX_VRERTS];
        nVert = 0;
        for(int j=0;j<MAX_VRERTS;j++)
            for(int k = 0;k<MAX_VRERTS;k++)
                adjMat[j][k] = 0;
        sortedArray = new char[MAX_VRERTS];
    }
/**
 * @param lab
 */
public void addVertex(char lab){
    vertxList[nVert++] = new Vertx(lab);
}
/**
 * @param start
 * @param end
 * 邻接矩阵,和之前的无向图区分,单向
 */
public void addEdge(int start,int end){
    adjMat[start][end] = 1;
}
/**
 * @param v
 * 展示节点数值
 */
public void display(int v){
    System.out.println(vertxList[v].lable);
}
/**
 * 主要工作是在whil循环中完成的
 * 1、调用noSuccessor找到任意一个没有后继的顶点
 * 2、如果找到这样一个顶点把它放到数组sortedArray中,并且从图中删除
 * 3、如果没有这样的顶点则,则此图必然存在环
 * */
public void topo(){
    int orig_nVerts=nVert;//记住有多多少中下标
    while(nVert>0){
        int currentVerts = noSuccessor();//找到一个后继顶点下标
        if(currentVerts  == -1){
            System.out.println("图中存在环!!");
            return;
        }
        //从后往前保存要删除的顶点
        sortedArray[nVert-1] = vertxList[currentVerts].lable;
        
        deleteVertx(currentVerts);//在图中删除这个顶点
    }
    //如果没有环就输出所有的有向图顶点
    for(int i=0;i<orig_nVerts;i++)
        System.out.print(sortedArray[i]+" ");
}
/**
 * @return
 * noSuccessor方法使用邻接矩阵找到没有后继的的顶点,在外层循环中,沿着每一行考察每个顶点
 * 在每一行中,用内层循环扫描值为1的列,如果找一个就说明顶点后面有后继,然后跳出内层循环考察下一个顶点
 * 只有一整行都没有找到,则说明这个顶点没有后继,并返回它的行号。如果没有这样的顶点就返回-1说明这是个环
 */
public int noSuccessor(){
    boolean isEdge;
    for(int row = 0;row<nVert;row++){
        isEdge =false;
        for(int col =0;col<nVert;col++){
            if(adjMat[row][col]>0){
                isEdge = true;
                break;
            }
            if(!isEdge)
                return row;
        }
    }
    return -1;
}
/**
 * @param delVert
 * 删除一个顶点很简单,顶点从vertxList数组中删除,后面的顶点向前移动填补空位。同样的,顶点的行列从邻接矩阵中删除
 * 下面的行和右面的列移动来填补空位。这些操作有deleteVertx 、moveRow、moveColLeft来完成
 */
public void deleteVertx(int delVert){
        if(delVert != nVert -1){//如果不是最后的顶点
            //从数组中删除,后面的顶点向前移
            for(int j=delVert;j<nVert-1;j++)
                vertxList[j] = vertxList[j+1];
            for(int row =delVert; row<nVert-1;row++)
                moveRowUp(row,nVert);
            for(int col=delVert;col<nVert-1;col++)
                 moveColLeft(col,nVert-1);
                
        }
        nVert--;//数组下标减一
}
/**
 * @param row
 * @param length
 * 将后面的行向上移一位
 */
private void moveRowUp(int row,int length){
    for(int col=0;col<length;col++)
        adjMat[row][col] = adjMat[row+1][col];
}
/**
 * @param col
 * @param length
 * 将后面的列向左移一位
 */
private void moveColLeft(int col,int length){
    for(int row = 0;row<length;row++)
        adjMat[row][col] = adjMat[row][col+1];
}
}

测试结果: H G F E D C B A

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏pangguoming

JDBC上关于数据库中多表操作一对多关系和多对多关系的实现方法

我们知道,在设计一个Java bean的时候,要把这些BEAN 的数据存放在数据库中的表结构,然而这些数据库中的表直接又有些特殊的关系,例如员工与部门直接有一对...

88470
来自专栏从流域到海域

《数据结构》 队列(Queue)操作代码集合

队列基本操作代码集合,来自《数据结构-用C语言描述》(第二版) 高教社 队列是受限制的链表或顺序表(只能从队首取结点,先进先出FIFO),相关操作可以...

23450
来自专栏积累沉淀

初识HtmlParser

1、概念 网页解析,即程序自动分析网页内容、获取信息,从而进一步处理信息。 htmlparser包提供方便、简洁的处理html文件的方法,它将html页面中...

23950
来自专栏Ldpe2G的个人博客

Graphviz4S ---- 在Scala中使用DOT语言绘图的开源工具

22560
来自专栏魂祭心

原 荐 NEO VM原理及其实现

44080
来自专栏iOS开发笔记

Objective-C的内省(Introspection)

内省(Introspection)是面向对象语言和环境的一个强大特性,Objective-C和Cocoa在这个方面尤其的丰富。内省是对象揭示自...

21860
来自专栏自由而无用的灵魂的碎碎念

通过写Java代码来对MyEclipse进行注册

import java.io.BufferedReader; import java.io.IOException; import java.io...

13940
来自专栏Golang语言社区

Golang中time包用法--转

time包中包括两类时间:时间点(某一时刻)和时常(某一段时间) 1时间常量(时间格式化) const ( ANSIC = "Mon Jan...

1.8K80
来自专栏古时的风筝

模拟实现Spring中的注解装配

在Spring中,XML文件中的bean配置是实现Spring IOC的核心配置文件,在早版本的Spring中,只能基于XML配置文件,配置各个对象之间的依赖关...

23950
来自专栏机器学习与自然语言处理

06-图1 列出连通集

题目来源:http://pta.patest.cn/pta/test/18/exam/4/question/624 给定一个有N个顶点和E条边的无向图,请用DF...

22390

扫码关注云+社区

领取腾讯云代金券