devbox
人工智能uu
这个屌丝很懒，什么也没留下！
关注作者
热门标签
热门文章
当前位置:   article > 正文

拓扑排序的算法实现_如何实现拓扑排序算法

作者：人工智能uu | 2024-07-23 17:00:33

赞

踩

如何实现拓扑排序算法

一、定义

对一个有向无环图(Directed Acyclic Graph简称DAG)G进行拓扑排序，是将G中所有顶点排成一个线性序列，使得图中任意一对顶点u和v，若边<u,v>∈E(G)，则u在线性序列中出现在v之前。通常，这样的线性序列称为满足拓扑次序(Topological Order)的序列，简称拓扑序列。简单的说，由某个集合上的一个偏序得到该集合上的一个全序，这个操作称之为拓扑排序。

二、DFS算法

找出一个入度为 0 的顶点，通过递归的方式遍历它所有可达的顶点，将其输出到拓扑排序的结果序列中，对遍历过的顶点做标记，避免其被重复访问。循环执行上面的过程，直到所有的顶点都被输出。

1.基于邻接表实现

  1. public class TopologicalSort_AdjacencyList_Dfs {
  2.  
  3.     private int mVertexNum; // 顶点数
  4.     private int[] mInDegree; // 顶点入度数
  5.     private List<Integer> mAdjacencyList[]; // 邻接表
  6.  
  7.     private boolean[] isVisited; // 用来避免顶点被重复访问
  8.     private Stack<Integer> mReversePost; // 用栈来保存排序结果
  9.  
  10.     public TopologicalSort_AdjacencyList_Dfs(int vertexNum) {
  11.         this.mVertexNum = vertexNum;
  12.         this.mInDegree = new int[vertexNum];
  13.         this.mAdjacencyList = new LinkedList[vertexNum];
  14.         for (int i = 0; i < vertexNum; ++i) {
  15.             mAdjacencyList[i] = new LinkedList<>();
  16.         }
  17.         this.isVisited = new boolean[vertexNum];
  18.         this.mReversePost = new Stack<>();
  19.     }
  20.  
  21.     /**
  22.      * 添加图的边，累计终止顶点入度
  23.      *
  24.      * @param s 起始顶点
  25.      * @param t 终止顶点
  26.      */
  27.     public void addEdge(int s, int t) {
  28.         mAdjacencyList[s].add(t);
  29.         mInDegree[t]++;
  30.     }
  31.  
  32.     /**
  33.      * 拓扑排序
  34.      */
  35.     public void sort() {
  36.         for (int i = 0; i < mVertexNum; i++) {
  37.             if (mInDegree[i] == 0) {
  38.                 recurDfs(i);
  39.             }
  40.         }
  41.  
  42.         System.out.println(mReversePost);
  43.     }
  44.  
  45.     /**
  46.      * 递归方法
  47.      *
  48.      * @param s
  49.      */
  50.     private void recurDfs(int s) {
  51.         if (isVisited[s] || mReversePost.size() == mVertexNum) {
  52.             return;
  53.         }
  54.  
  55.         isVisited[s] = true;
  56.         mReversePost.push(s);
  57.  
  58.         for (int i = 0; i < mAdjacencyList[s].size(); i++) {
  59.             int w = mAdjacencyList[s].get(i);
  60.             if (isVisited[w]) {
  61.                 return;
  62.             }
  63.  
  64.             mInDegree[w]--;
  65.             if (mInDegree[w] == 0) {
  66.                 recurDfs(w);
  67.             }
  68.         }
  69.     }
  70.  
  71.     public static void main(String[] args) {
  72.         TopologicalSort_AdjacencyList_Dfs graph = new TopologicalSort_AdjacencyList_Dfs(8);
  73.         graph.addEdge(0, 1);
  74.         graph.addEdge(0, 3);
  75.         // graph.addEdge(1, 2);
  76.         graph.addEdge(1, 4);
  77.         graph.addEdge(2, 5);
  78.         graph.addEdge(4, 5);
  79.         graph.addEdge(4, 6);
  80.         graph.addEdge(5, 7);
  81.         graph.addEdge(6, 7);
  82.         graph.sort();
  83.     }
  84. }

2.基于邻接矩阵实现

  1. public class TopologicalSort_AdjacencyMatrix_Dfs {
  2.  
  3.     private int mVertexNum; // 顶点数
  4.     private int[] mInDegree; // 顶点入度数
  5.     private int[][] mAdjacencyMatrix; // 邻接矩阵
  6.  
  7.     private boolean[] isVisited; // 用来避免顶点被重复访问
  8.     private Stack<Integer> mReversePost; // 用栈来保存排序结果
  9.  
  10.     public TopologicalSort_AdjacencyMatrix_Dfs(int vertexNum) {
  11.         this.mVertexNum = vertexNum;
  12.         this.mInDegree = new int[vertexNum];
  13.         this.mAdjacencyMatrix = new int[vertexNum][vertexNum];
  14.         for (int i = 0; i < vertexNum; i++) {
  15.             for (int j = 0; j < vertexNum; j++) {
  16.                 mAdjacencyMatrix[i][j] = 0;
  17.             }
  18.         }
  19.         this.isVisited = new boolean[vertexNum];
  20.         this.mReversePost = new Stack<>();
  21.     }
  22.  
  23.     /**
  24.      * 添加图的边，累计终止顶点入度
  25.      *
  26.      * @param s 起始顶点
  27.      * @param t 终止顶点
  28.      */
  29.     public void addEdge(int s, int t) {
  30.         mAdjacencyMatrix[s][t] = 1;
  31.         mInDegree[t]++;
  32.     }
  33.  
  34.     /**
  35.      * 拓扑排序
  36.      */
  37.     public void sort() {
  38.         for (int i = 0; i < mVertexNum; i++) {
  39.             if (mInDegree[i] == 0) {
  40.                 recurDfs(i);
  41.             }
  42.         }
  43.  
  44.         System.out.println(mReversePost);
  45.     }
  46.  
  47.     /**
  48.      * 递归方法
  49.      *
  50.      * @param s
  51.      */
  52.     private void recurDfs(int s) {
  53.         if (isVisited[s] || mReversePost.size() == mVertexNum) {
  54.             return;
  55.         }
  56.  
  57.         isVisited[s] = true;
  58.         mReversePost.push(s);
  59.  
  60.         for (int i = 0; i < mVertexNum; i++) {
  61.             if (mAdjacencyMatrix[s][i] == 1 && !isVisited[i]) {
  62.                 mInDegree[i]--;
  63.                 if (mInDegree[i] == 0) {
  64.                     recurDfs(i);
  65.                 }
  66.             }
  67.         }
  68.     }
  69.  
  70.     public static void main(String[] args) {
  71.         TopologicalSort_AdjacencyMatrix_Dfs graph = new TopologicalSort_AdjacencyMatrix_Dfs(8);
  72.         graph.addEdge(0, 1);
  73.         graph.addEdge(0, 3);
  74.         // graph.addEdge(1, 2);
  75.         graph.addEdge(1, 4);
  76.         graph.addEdge(2, 5);
  77.         graph.addEdge(4, 5);
  78.         graph.addEdge(4, 6);
  79.         graph.addEdge(5, 7);
  80.         graph.addEdge(6, 7);
  81.         graph.sort();
  82.     }
  83. }

三、Kahn算法

找出一个入度为 0 的顶点，将其输出到拓扑排序的结果序列中，并且把这个顶点从图中删除。循环执行上面的过程，直到所有的顶点都被输出。

1.基于邻接表实现

  1. public class TopologicalSort_AdjacencyList_Kahn {
  2.  
  3.     private int mVertexNum; // 顶点数
  4.     private int[] mInDegree; // 顶点入度数
  5.     private List<Integer> mAdjacencyList[]; // 邻接表
  6.     private Deque<Integer> mZeroDegreeDeque; // 入度数为0的顶点
  7.  
  8.     public TopologicalSort_AdjacencyList_Kahn(int vertexNum) {
  9.         this.mVertexNum = vertexNum;
  10.         this.mInDegree = new int[vertexNum];
  11.         this.mAdjacencyList = new LinkedList[vertexNum];
  12.         for (int i = 0; i < vertexNum; ++i) {
  13.             mAdjacencyList[i] = new LinkedList<>();
  14.         }
  15.         this.mZeroDegreeDeque = new ArrayDeque<>();
  16.     }
  17.  
  18.     /**
  19.      * 添加图的边，累计终止顶点入度
  20.      *
  21.      * @param s 起始顶点
  22.      * @param t 终止顶点
  23.      */
  24.     public void addEdge(int s, int t) {
  25.         mAdjacencyList[s].add(t);
  26.         mInDegree[t]++;
  27.     }
  28.  
  29.     /**
  30.      * 拓扑排序
  31.      */
  32.     public void sort() {
  33.         for (int i = 0; i < mVertexNum; i++) {
  34.             if (mInDegree[i] == 0) {
  35.                 mZeroDegreeDeque.offer(i);
  36.             }
  37.         }
  38.  
  39.         List<Integer> result = new ArrayList<>();
  40.  
  41.         while (!mZeroDegreeDeque.isEmpty()) {
  42.             int s = mZeroDegreeDeque.poll();
  43.             for (int j = 0; j < mAdjacencyList[s].size(); j++) {
  44.                 int w = mAdjacencyList[s].get(j);
  45.                 mInDegree[w]--;
  46.                 if (mInDegree[w] == 0) {
  47.                     mZeroDegreeDeque.offer(w);
  48.                 }
  49.             }
  50.             result.add(s);
  51.         }
  52.  
  53.         System.out.println(result);
  54.     }
  55.  
  56.     public static void main(String[] args) {
  57.         TopologicalSort_AdjacencyList_Kahn graph = new TopologicalSort_AdjacencyList_Kahn(8);
  58.         graph.addEdge(0, 1);
  59.         graph.addEdge(0, 3);
  60.         graph.addEdge(1, 2);
  61.         graph.addEdge(1, 4);
  62.         graph.addEdge(2, 5);
  63.         graph.addEdge(4, 5);
  64.         graph.addEdge(4, 6);
  65.         graph.addEdge(5, 7);
  66.         graph.addEdge(6, 7);
  67.         graph.sort();
  68.     }
  69. }

2.基于邻接矩阵实现

  1. public class TopologicalSort_AdjacencyMatrix_Kahn {
  2.  
  3.     private int mVertexNum; // 顶点数
  4.     private int[] mInDegree; // 顶点入度数
  5.     private int[][] mAdjacencyMatrix; // 邻接矩阵
  6.     private Deque<Integer> mZeroDegreeDeque; // 入度数为0的顶点
  7.  
  8.     public TopologicalSort_AdjacencyMatrix_Kahn(int vertexNum) {
  9.         this.mVertexNum = vertexNum;
  10.         this.mInDegree = new int[vertexNum];
  11.         this.mAdjacencyMatrix = new int[vertexNum][vertexNum];
  12.         for (int i = 0; i < vertexNum; i++) {
  13.             for (int j = 0; j < vertexNum; j++) {
  14.                 mAdjacencyMatrix[i][j] = 0;
  15.             }
  16.         }
  17.         this.mZeroDegreeDeque = new ArrayDeque<>();
  18.     }
  19.  
  20.     /**
  21.      * 添加图的边，累计终止顶点入度
  22.      *
  23.      * @param s 起始顶点
  24.      * @param t 终止顶点
  25.      */
  26.     public void addEdge(int s, int t) {
  27.         mAdjacencyMatrix[s][t] = 1;
  28.         mInDegree[t]++;
  29.     }
  30.  
  31.     /**
  32.      * 拓扑排序
  33.      */
  34.     public void sort() {
  35.         for (int i = 0; i < mVertexNum; i++) {
  36.             if (mInDegree[i] == 0) {
  37.                 mZeroDegreeDeque.offer(i);
  38.             }
  39.         }
  40.  
  41.         List<Integer> result = new ArrayList<>();
  42.  
  43.         while (!mZeroDegreeDeque.isEmpty()) {
  44.             int s = mZeroDegreeDeque.poll();
  45.             for (int j = 0; j < mVertexNum; j++) {
  46.                 if (mAdjacencyMatrix[s][j] != 1) {
  47.                     continue;
  48.                 }
  49.  
  50.                 mInDegree[j]--;
  51.                 if (mInDegree[j] == 0) {
  52.                     mZeroDegreeDeque.offer(j);
  53.                 }
  54.             }
  55.             result.add(s);
  56.         }
  57.  
  58.         System.out.println(result);
  59.     }
  60.  
  61.     public static void main(String[] args) {
  62.         TopologicalSort_AdjacencyMatrix_Kahn graph = new TopologicalSort_AdjacencyMatrix_Kahn(8);
  63.         graph.addEdge(0, 1);
  64.         graph.addEdge(0, 3);
  65.         graph.addEdge(1, 2);
  66.         graph.addEdge(1, 4);
  67.         graph.addEdge(2, 5);
  68.         graph.addEdge(4, 5);
  69.         graph.addEdge(4, 6);
  70.         graph.addEdge(5, 7);
  71.         graph.addEdge(6, 7);
  72.         graph.sort();
  73.     }
  74. }

 

声明：本文内容由网友自发贡献，不代表【wpsshop博客】立场，版权归原作者所有，本站不承担相应法律责任。如您发现有侵权的内容，请联系我们。转载请注明出处：https://www.wpsshop.cn/w/人工智能uu/article/detail/870789
推荐阅读
相关标签

Copyright © 2003-2013 www.wpsshop.cn 版权所有，并保留所有权利。

  

闽ICP备14008679号