拓扑排序实现思路分析 |
您所在的位置：网站首页 › 室内设计的思路和方法是什么样的 › 拓扑排序实现思路分析 |
拓扑排序实现思路分析
|
了解拓扑排序
看到这篇文章的博友可能已经对拓扑排序有了一定的了解，但是在这里我们还是需要明确一下什么是拓扑排序。 拓扑排序的严谨定义网上一搜一大堆，我就不copy了，我总结几点拓扑排序的特点： 1. 拓扑排序是建立在有向无环图（DAG）的基础上的。 2.拓扑排序就是将DAG以线性方式进行排序。即对任何顶点U到顶点V的有向边U->V，在最后的排序结果中，顶点U总是在顶点V的前面。这样的排序结果成为拓扑排序。 3.拓扑排序的结果不一定唯一。 咱们举个栗子： 我们先给定一个有向无环图：
拓扑排序的效果是这样的：看上去就像是把图拍扁了一样。
A->B->C->D->E 或 B->A->C->D->E（这里就体现了拓扑排序的结果可能不止一个） 思路分析看了上面的栗子，我相信大家对拓扑排序肯定都有了一定的印象，那我们就来说说用程序如何来实现拓扑排序。 思路其实非常简单，就是不断取出图中入度为零的节点，取出的节点从图中删除。 具体的演示一下过程：
注：如果发现：有向图不为空（结点数不为零），但无法找到入度为零的节点，这就说明图中有环，也就违背了拓扑排序的前提条件。下图中C、D、E节点就形成了环。
还有另一种思路：不断取出图中出度为零的节点，
上面两种方式可以用不同的代码形式来实现，第一种很简单，我们只需要通过循环实现即可，第二种方式就需要用到DFS（深度优先搜索）。 具体实现第一种思路：每次取出入度为零的节点 public class Topo { static int[][] graph = { {0, 1, 0, 0}, {0, 0, 0, 0}, {0, 1, 0, 0}, {0, 0, 1, 0}, }; static int n = 4;//图中的节点数 static int current = 0;// static int[] visited = new int[n];//判断某个节点是否已经被取出，取出的节点置为1 static int[] sortArray = new int[n];//拓扑排序结果 public static void main(String[] args) { while (!isEmpty()) { for (int i = 0; i < n; i++) {//寻找入度为0的节点 if (visited[i] == 0 && inDegreeIsZero(i)) { visited[i] = 1;//将这个点标记为“已取出”状态 deleteOutEdge(i); sortArray[current++] = i; } } } System.out.println(Arrays.toString(sortArray)); } /** * 判断给定的标记数组是否全为一，也就是判断图中是否为空 * * @return */ public static boolean isEmpty() { for (int i = 0; i < visited.length; i++) { if (visited[i] != 1) { return false; } } return true; } /** * 判断指定节点的入度是否为零 * * @param i * @return */ public static boolean inDegreeIsZero(int i) { for (int j = 0; j < n; j++) { if (graph[j][i] > 0) { return false; } } return true; } /** * 删除指定节点的出去的边 * * @param i */ public static void deleteOutEdge(int i) { for (int j = 0; j < n; j++) { graph[i][j] = 0; } } }运行结果：
第二种思路：每次取出出度为零的节点 代码中我们的有向图是这个效果：在代码中采用邻接矩阵的方式表示。 public class Topo { static int[][] graph = { {0, 1, 0, 0}, {0, 0, 0, 0}, {0, 1, 0, 0}, {0, 0, 1, 0}, }; static int n = 4;//图中的节点数 static int current = n - 1;//当前排序结果数组的下标 static int[] visited = new int[n];//判断某个节点是否已经被访问过 static int[] sortArray = new int[n];//拓扑排序结果 public static void main(String[] args) { for (int i = 0; i < n; i++) { dfs(i); } System.out.println(Arrays.toString(sortArray)); } public static void dfs(int i) { if (visited[i] == 0) {//节点未被访问过 for (int j = 0; j < n; j++) { if (graph[i][j] > 0 && visited[j] == 0) { dfs(j); } } sortArray[current--] = i; visited[i] = 1; } } }运行结果：
|
。。。。。。。。省略后面的步骤了。
【本文地址】
今日新闻 |
推荐新闻 |