拓扑是什么意思，拓扑结构是什么意思（揭开的神秘面纱）

关于【拓扑是什么意思】，拓扑结构是什么意思，今天小编给您分享一下，如果对您有所帮助别忘了关注本站哦。

• 内容导航：
• 1、拓扑是什么意思：揭开「拓扑排序」的神秘面纱
• 2、拓扑是什么意思，拓扑结构是什么意思

1、拓扑是什么意思：揭开「拓扑排序」的神秘面纱

作者 | 小齐本齐

责编 | Carol

来源 | 码农田小齐

Topological sort 又称 Topological order，这个名字有点迷惑性，因为拓扑排序并不是一个纯粹的排序算法，它只是针对某一类图，找到一个可以执行的线性顺序。

这个算法听起来高大上，如今的面试也很爱考，比如当时我在面我司时有整整一轮是基于拓扑排序的设计。

但它其实是一个很好理解的算法，跟着我的思路，让你再也不会忘记她。

有向无环图

刚刚我们提到，拓扑排序只是针对特定的一类图，那么是针对哪类图的呢？

答：Directed acyclic graph (DAG)，有向无环图。即：

1. 这个图的边必须是有方向的；

2. 图内无环。

那么什么是方向呢？

比如微信好友就是有向的，你加了他好友他可能把你删了你却不知道。。。那这个朋友关系就是单向的。。

什么是环？环是和方向有关的，从一个点出发能回到自己，这是环。

所以下图左边不是环，右边是。

那么如果一个图里有环，比如右图，想执行1就要先执行3，想执行3就要先执行2，想执行2就要先执行1，这成了个死循环，无法找到正确的打开方式，所以找不到它的一个拓扑序。

总结：

• 如果这个图不是 DAG，那么它是没有拓扑序的；

• 如果是 DAG，那么它至少有一个拓扑序；

• 反之，如果它存在一个拓扑序，那么这个图必定是 DGA.

所以这是一个充分必要条件。

拓扑排序

那么这么一个图的「拓扑序」是什么意思呢？

我们借用百度百科[1]的这个课程表来说明。

这里有 9 门课程，有些课程是有先修课程的要求的，就是你要先学了「最右侧这一栏要求的这个课」才能再去选「高阶」的课程。

那么这个例子中拓扑排序的意思就是：

就是求解一种可行的顺序，能够让我把所有课都学了。

那怎么做呢？

首先我们可以用图来描述它，图的两个要素是顶点和边，那么在这里：

顶点：每门课

边：起点的课程是终点的课程的先修课

画出来长这个样：

这种图叫AOV(Activity alt="拓扑是什么意思，拓扑结构是什么意思（揭开的神秘面纱）" src="https://p3.toutiaoimg.com/pgc-image/RqMqMYY7LcGio6~tplv-tt-large.image" />

算法详解

在上面的图里，大家很容易就看出来了它的拓扑序，但当工程越来越庞大时，依赖关系也会变得错综复杂，那就需要用一种系统性的方式方法来求解了。

那么我们回想一下刚刚自己找拓扑序的过程，为什么我们先看上了 C1, C2?

因为它们没有依赖别人啊，也就是它的入度为 0.

入度：顶点的入度是指「指向该顶点的边」的数量；

出度：顶点的出度是指该顶点指向其他点的边的数量。

所以我们先执行入度为 0 的那些点，

那也就是要记录每个顶点的入度。

因为只有当它的入度为 0的时候，我们才能执行它。

在刚才的例子里，最开始 C1, C2 的入度就是 0，所以我们可以先执行这两个。

那在这个算法里第一步就是得到每个顶点的入度。

Step0: 预处理得到每个点的入度

我们可以用一个 HashMap 来存放这个信息，或者用一个数组会更精巧。

在文中为了方便展示，我就用表格了：

Step1

拿到了这个之后，就可以执行入度为 0 的这些点了，也就是 C1, C2.

那我们把可以被执行的这些点，放入一个待执行的容器里，这样之后我们一个个的从这个容器里取顶点就好了。

至于这个容器究竟选哪种数据结构，这取决于我们需要做哪些操作，再看哪种数据结构可以为之服务。

那么首先可以把[C1, C2]放入容器中，

然后想想我们需要哪些操作吧！

我们最常做的操作无非就是把点放进来，把点拿出去执行了，也就是需要一个offer和poll操作比较高效的数据结构，那么 queue 就够用了。

（其他的也行，放进来这个容器里的顶点的地位都是一样的，都是可以执行的，和进来的顺序无关，但何必非得给自己找麻烦呢？一个常规顺序的简简单单的 queue 就够用了。）

然后就需要把某些点拿出去执行了。

【划重点】当我们把 C1 拿出来执行，那这意味这什么？

答：意味着「以 C1 为顶点」的「指向其他点」的「边」都消失了，也就是 C1 的出度变成了 0.

如下图，也就是这两条边可以消失了。

那么此时我们就可以更新 C1 所指向的那些点也就是 C3 和 C8 的 入度 了，更新后的数组如下：

那我们这里看到很关键的一步，C8 的入度变成了 0！

也就意味着 C8 此时没有了任何依赖，可以放到我们的 queue 里等待执行了。

此时我们的 queue 里就是：[C2, C8].

Step2

下一个我们再执行 C2，

那么 C2 所指向的 C3, C5 的 入度-1，

更新表格：

也就是 C3 和 C5 都没有了任何束缚，可以放进 queue 里执行了。

queue 此时变成：[C8, C3, C5]

Step3

那么下一步我们执行 C8，

相应的 C8 所指的 C9 的入度-1.更新表格：

那么 C9 没有了任何要求，可以放进 queue 里执行了。

queue 此时变成：[C3, C5, C9]

Step4

接下来执行 C3，

相应的 C3 所指的 C4 的入度-1.更新表格：

但是 C4 的入度并没有变成 0，所以这一步没有任何点可以加入 queue。

queue 此时变成 [C5, C9]

Step5

再执行 C5，

那么 C5 所指的 C4 和 C6 的入度- 1.更新表格：

这里 C4 的依赖全都消失啦，那么可以把 C4 放进 queue 里了：

queue = [C9, C4]

Step6

然后执行 C9，

那么 C9 所指的 C7 的入度- 1.

这里 C7 的入度并不为 0，还不能加入 queue，

此时 queue = [C4]

Step7

接着执行 C4，

所以 C4 所指向的 C6 和 C7 的入度-1，更新表格：

C6 和 C7 的入度都变成 0 啦！！把它们放入 queue，继续执行到直到 queue 为空即可。

总结

好了，那我们梳理一下这个算法：

数据结构这里我们的入度表格可以用 map 来存放

Map:

但实际代码中，我们用一个 int array 来存储也就够了，数组的 index 表示每个顶点，数组里的数值来表示每个顶点的入度，这样比 Map 更精巧。

然后用了一个普通的 queue，用来存放可以被执行的那些 node.

过程

我们把入度为 0 的那些顶点放入 queue 中，然后通过每次执行 queue 中的顶点，就可以让依赖这个被执行的顶点的那些点的 入度-1，如果有顶点的入度变成了 0，就可以放入 queue 了，直到 queue 为空。

细节

这里有几点实现上的细节：

当我们 check 是否有新的顶点的 入度 == 0 时，没必要过一遍整个 map 或者数组，只需要 check 刚刚改动过的就好了。

另一个是如果题目没有给这个图是 DAG 的条件的话，那么有可能是不存在可行解的，那怎么判断呢？很简单的一个方法就是比较一下最后结果中的顶点的个数和图中所有顶点的个数是否相等，或者加个计数器，如果不相等，说明就不存在有效解。所以这个算法也可以用来判断一个图是不是有向无环图。

很多题目给的条件可能是给这个图的 edge list，也是表示图的一种常用的方式。那么给的这个 list 就是表示图中的边。这里要注意审题哦，看清楚是谁 depends alt="拓扑是什么意思，拓扑结构是什么意思（揭开的神秘面纱）" src="https://p3.toutiaoimg.com/pgc-image/RxSG3X8JDqC1WG~tplv-tt-large.image" />

Example 3.

Input: 2, [[1,0],[0,1]]

Output:

Explanation: 这课没法上了

class Solution {

public int findOrder(int numCourses, int[][] prerequisites) {

int res = new int[numCourses];

int indegree = new int[numCourses];

// get the indegree for each course

for(int[] pre : prerequisites) {

indegree[pre[0]] ++;

}

// put courses with indegree == 0 to queue

Queue queue = new ArrayDeque<>;

for(int i = 0; i < numCourses; i++) {

if(indegree[i] == 0) {

queue.offer(i);

}

}

// execute the course

int i = 0;

while(!queue.isEmpty) {

Integer curr = queue.poll;

res[i++] = curr;

// remove the pre = curr

for(int[] pre : prerequisites) {

if(pre[1] == curr) {

indegree[pre[0]] --;

if(indegree[pre[0]] == 0) {

queue.offer(pre[0]);

}

}

}

}

return i == numCourses ? res : new int{};

}

}

还是附上题目吧，just in case, if you want to see the details.

另外，拓扑排序还可以用 DFS - 深度优先搜索 来实现，限于篇幅就不在这里展开了，大家可以参考GeeksforGeeks[2]的这个资料。

实际应用

我们上文已经提到了它的一个 use case，就是选课系统，这也是最常考的题目。

而拓扑排序最重要的应用就是关键路径问题，这个问题对应的是 AOE (Activity alt="拓扑是什么意思，拓扑结构是什么意思（揭开的神秘面纱）" src="https://p3.toutiaoimg.com/pgc-image/RxSG3YZA6Qxin8~tplv-tt-large.image" />

今日福利

遇见大咖

由 CSDN 全新专为技术人打造的高端对话栏目《大咖来了》来啦！

CSDN 创始人&董事长、极客帮创投创始合伙人蒋涛携手京东集团技术副总裁、IEEE Fellow、京东人工智能研究院常务副院长、深度学习及语音和语言实验室负责人何晓冬，来也科技 CTO 胡一川，共话中国 AI 应用元年来了，开发者及企业的路径及发展方向！

2、拓扑是什么意思，拓扑结构是什么意思

拓扑结构是什么意思?网络拓扑结构就是指用传输媒体把计算机等各种设备互相连接起来的物理布局，是指互连过程中构成的几何形状，它能表示出网络服务器、工作站的网络配置和互相之间的连接网络拓扑结构可按形状分类，分别有：星型、环型、总线型、树型、总线/星型和网状型拓扑结构，我来为大家讲解一下关于拓扑结构是什么意思?跟着小编一起来看一看吧!

拓扑结构是什么意思

网络拓扑结构就是指用传输媒体把计算机等各种设备互相连接起来的物理布局，是指互连过程中构成的几何形状，它能表示出网络服务器、工作站的网络配置和互相之间的连接。网络拓扑结构可按形状分类，分别有：星型、环型、总线型、树型、总线/星型和网状型拓扑结构。

星型拓扑结构将各个节点与中心节点连接，呈现出放射状排列，通过中心节点对全网的通信进行控制。总线型计算机网络拓扑结构主要是通过一条高速主干电缆对周围节点进行连接。环型计算机网络拓扑结构可以对节点收尾的信息进行循环，形成闭合的环型线路，提高单项传输的完整性。树型计算机网络拓扑结构可以保证两节点之间的无回路传输，保证计算机网络拓扑结构扩充的方便性。网状型计算机网络拓扑结构将节点之间的线路进行网状连接，有效提高了线路之间信息传递的可靠性。

本文关键词：网络拓扑是什么意思，实验拓扑是什么意思，拓扑结构是什么意思，共享拓扑是什么意思，拓扑是什么意思。这就是关于《拓扑是什么意思，拓扑结构是什么意思（揭开的神秘面纱）》的所有内容，希望对您能有所帮助！

本文链接：https://bk.89qw.com/a-847470