首页
学习
活动
专区
工具
TVP
发布
社区首页 >专栏 >有向图的拓扑排序

有向图的拓扑排序

作者头像
用户1418372
发布2018-10-10 10:49:31
1.1K0
发布2018-10-10 10:49:31
举报
文章被收录于专栏:清晨我上码清晨我上码

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

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

基本思想:

  • 步骤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

本文参与 腾讯云自媒体分享计划,分享自作者个人站点/博客。
原始发表:2018.09.22 ,如有侵权请联系 cloudcommunity@tencent.com 删除

本文分享自 作者个人站点/博客 前往查看

如有侵权,请联系 cloudcommunity@tencent.com 删除。

本文参与 腾讯云自媒体分享计划  ,欢迎热爱写作的你一起参与!

评论
登录后参与评论
0 条评论
热度
最新
推荐阅读
目录
  • 拓扑排序是可以用图模拟的另一种操作方式。
    • 基本思想:
    领券
    问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档