数据结构与算法笔记:高级篇 - 拓扑排序:如何确定代码源文件的编译依赖关系?

本文主要是介绍数据结构与算法笔记:高级篇 - 拓扑排序:如何确定代码源文件的编译依赖关系?,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

概述

从本章开始,就开始进入高级篇。相对基础篇,高级篇涉及的知识比较零散,不是太系统。所以,我会围绕一个实际软件开发的问题,在阐述具体解决方法的过程中,将涉及的知识点给你详细讲解出来。

所以,相较于基础篇 “开篇问题 - 知识讲解-总结” 这样的文章结构,高级篇稍作了改变,大致分为这样几个部分:“问题阐述 - 算法解析 - 总结引申”。

现在,我们进入高级篇的第一节,如何确定代码源文件的编译依赖关系。

我们知道,一个完整的项目往往会包含很多代码源文件。编译器在编译整个项目时,需要按照依赖关系,依次编译每个源文件。比如, A.cpp 依赖 B.cpp,那在编译的时候,编译器需要先编译 B.cpp,才能编译 A.cpp。

编译器通过分析源文件或者程序员事先写好的编译配置文件(比如 Makefile 文件),来获取这种局部的依赖关系。那编译器又该如何通过源文件两两之间的局部依赖关系,确定一个全局的编译顺序呢?

在这里插入图片描述


算法解析

这个问题的解决思路与 “图” 这种数据结构的一个经典算法 “拓扑排序算法” 有关。那什么事拓扑排序呢?这个概念很好理解,我们先来看一个生活中的拓扑排序的例子。

我们在穿衣服的时候都有一定的顺序,我们可以把这种顺序想成,衣服与衣服之间有一定的依赖关系。比如说,你必须先穿袜子才能穿鞋,先穿内裤才能穿秋裤。假设我们现在有八件衣服要穿,它们之间的两两依赖关系我们已经很清楚了,那如何安排一个穿衣序列,能够满足所有的两两之间的依赖关系?

这就是一个拓扑排序问题。从这个例子中,你应该能想到,在很多时候,拓扑排序的序列并不是唯一的。你可以看下图,它里面有好几种满足这些局部先后关系的穿衣序列。

在这里插入图片描述

弄懂了生活中的例子,开篇关于编译顺序的问题,你应该也有思路了。开篇问题跟这个问题的模型是一样的,也可以抽象成一个拓扑排序问题。

拓扑排序的原理非常简单,我们的重点应该放到拓扑排序的实现上面。

前面多次讲过,算法是构建在数据结构之上的。针对这个问题,我们先来看下,如何将问题背景抽象成具体的数据结构?

我们可以把源文件与源文件之间的依赖关系,抽象成一个有向图。每个源文件对应图中的一个顶点,源文件之间的依赖关系就是顶点之间的边。

如果 a 先与 b 执行,也就是说 b 依赖 a,那么就在顶点 a 和顶点 b 之间,构建一条从 a 指向 b 的边。而且,这个图不仅要是有向图,还要是一个有向无环图,也就是不能存在像 a->b->c->a 这样的循环依赖关系。因为图中一旦出现环,拓扑排序就无法工作了。实际上,拓扑排序本身就是基于有向无环图的一个算法。

public class Graph {private int v; // 顶点个数private LinkedList<Integer> adj[]; // 邻接表public Graph(int v) {this.v = v;adj = new LinkedList[v];for (int i = 0; i < adj.length; i++) {adj[i] = new LinkedList<>();}}public void addEdge(int s, int t) { // s先与t,边s->tadj[s].add(t);}
}

数据结构定义好了,现在,我们来看,如何在这个有向无环图上,实现拓扑排序?

拓扑排序有两种实现方式,都不难理解。它们分别是 Kahn 算法DFS 深度优先算法。我们依次来看下它们是怎么工作的。

1. Kahn 算法

Kahn 算法实际上用的是贪心算法思想,思路非常简单。

定义数据结构的时候,如果 s 需要先于 t 执行,那就添加一条 s 指向 t 的边。所以,如果某个顶点入度为 0,也就表示,没有任何顶点必须先于这个顶点执行,那么这个顶点就可以执行了。

我们先从图中,找出一个入度为 0 的顶点,将其输出到拓扑排序的结果列中(对应地代码就是把它打印出来),并且把这个顶点从图中删除(也就是把这个顶点可达的顶点的入度都减一)。我们循环执行上面的过程,直到所有的顶点都被输出。最后输出序列,就是满足局部依赖关系的拓扑排序。

我把 Kahn 算法用代码实现了一遍,你可以结合着文字描述一块看下。不过,你应该能发现,这段代码实现更有技巧一些,并没有真正删除顶点的操作。代码中有详细的注释,你自己看下。

    public void topoSortByKahn() {int[] inDegree = new int[v]; // 统计每个顶点的入度for (int i = 0; i < v; i++) {for (int j = 0; j < adj[i].size(); j++) {int w = adj[i].get(j); // i->winDegree[w]++;}}LinkedList<Integer> queue = new LinkedList<>();for (int i = 0; i < v; i++) { // 找出所有入度为0的顶点if (inDegree[i] == 0) {queue.add(i);}}while (!queue.isEmpty()) {int i = queue.remove(); // 取出入读为0的顶点System.out.print("->" + i);for (int j = 0; j < adj[i].size(); j++) { // 找出i指向的所有顶点,并将它们的入度减一int k = adj[i].get(j);inDegree[k]--;if (inDegree[k] == 0) { // 若k入度减一后,顶点的入度为0,则加入queuequeue.add(k);}}}}

DFS 算法

图上深度优先搜索前面已经讲过了,实际上拓扑排序也可以用深度优先搜索来实现。不过,这里的名字要稍微改下,更加准确的说应该是深度优先遍历,遍历图中的所有节点,而非只是搜索一个顶点到另一个顶点的路径。

关于这个算法的实现,代码如下。

    public void topoSortByDFS() {// 先构建逆邻表,边s->t表示,s依赖于t,t先于sLinkedList[] inverseAdj = new LinkedList[v];for (int i = 0; i < v; i++) { // 申请空间inverseAdj[i] = new LinkedList<>();}for (int i = 0; i < v; i++) { // 通过邻接表生成逆邻接表for (int j = 0; j < adj[i].size(); j++) {int w = adj[i].get(j); // i->winverseAdj[w].add(i); // w->i}}boolean[] visited = new boolean[v];for (int i = 0; i < v; i++) { // 深度优先遍历if (visited[i] == false) {visited[i] = true;dfs(i, inverseAdj, visited);}}}private void dfs(int vertex, LinkedList<Integer>[] inverseAdj, boolean[] visited) {for (int i = 0; i < inverseAdj[vertex].size(); i++) {int w = inverseAdj[vertex].get(i);if (visited[w] == true) continue;visited[w] = true;dfs(w, inverseAdj, visited);} // 先把vertex这个顶点可达的所有节点都打印出来,然后再打印它自己System.out.println("->" + vertex);}

这个算法包含两个关键部分。

第一部分是通过邻接表构造逆邻接表。邻接表中,边 s->t 表示 s 优先于 t 执行,也就是 t 要依赖 s。在逆邻接表中,边 s->t 表示 s 依赖于 t,s 后于 t 执行。为什么这么转化呢?这个跟这个算法的实现思想有关。

第二部分是这个算法的核心部分,也就是递归处理每个顶点。对于顶点 vertex 来说,我们先输出它可达的所有节点,也就是说把它依赖的所有顶点输出了,然后在输出自己。

到这里,用 Kahn 算法和 DFS 算法求拓扑排序的原理和代码实现都讲完了。我们来看下,这两个算法的时间复杂度分别是多少呢?

从 Kahn 代码中可以看出来,每个顶点被访问了一次,每个边也都被访问了一次,所以,Kahn 算法的时间复杂度就是 O ( V + E ) O(V+E) O(V+E) (V 表示顶点个数,E 表示边的个数)。

DFS 算法的时间复杂度我们之前分析过。每个顶点被访问两次,每条边都被访问一次,所以时间复杂度也是 O ( V + E ) O(V+E) O(V+E)

注意,这里的图可能是不连通的,有可能是有好几个不联通的子图构成,所以,E 并不一定大于 V,两者的大小关系不确定。所以,在表示时间复杂度的时候,V、E 都要考虑在内。

总结

在基础篇中,关于 “图”,我们讲了图的定义和存储、图的广度和深度优先搜索。本章,我们又讲了一个关于图的算法,拓扑排序。

拓扑排序应用非常广泛,解决的问题的模型也非常一直。凡是需要通过局部顺序来推导全局顺序的,一般都能用拓扑排序来解决。此外,拓扑排序还能检测图中环的存在。对于 Kahn 算法来说,如果最后输出出来的顶点个数,少于图中顶点个数,图中还有入度不是 0 的顶点,那就说明,图中存在环。

关于图中环的检测,我们在递归那一章节讲过一个例子,在查找最终推荐人的时候,可能会因为脏数据,造成存在循环推荐,比如用户 A 推荐了用户 B,用户 B 推荐了用户 C,用户 C 又推荐了用户 A。如何避免这种脏数据导致的无线递归呢?

实际上,这就是环的检测问题。因为我们每次都只是查找一个用户的最终推荐人,所以,我们并不需要动用复杂的拓扑排序,而只需要记录已经访问过的用户 ID,当用户 ID 第二次被访问的时候,就说明环存在,也就说明存在脏数据。

    HashSet<Long> hashSet = new HashSet<>(); // 保存已经访问过的actorIdlong findRootReferrerId(long actorId) {if (hashSet.contains(actorId)) {return; // 存在环}hashSet.add(actorId);long referrerId = select referrer_id from [table] where actor_id = actorId;if (referrerId == null) return actorId;findRootReferrerId(actorId);}

如果把这个问题改一下,我们想要知道,数据库中的所有用户之间的推荐关系了,有没有存在环的情况。这个问题,就需要用到拓扑排序算法了。我们把用户之间的推荐关系,从数据库中加载到内存中,然后构建本章讲的这种有向图数据结构,再利用拓扑排序,就可以快速检测出是否存在环了。

这篇关于数据结构与算法笔记:高级篇 - 拓扑排序:如何确定代码源文件的编译依赖关系?的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/1086273

相关文章

不懂推荐算法也能设计推荐系统

本文以商业化应用推荐为例,告诉我们不懂推荐算法的产品,也能从产品侧出发, 设计出一款不错的推荐系统。 相信很多新手产品,看到算法二字,多是懵圈的。 什么排序算法、最短路径等都是相对传统的算法(注:传统是指科班出身的产品都会接触过)。但对于推荐算法,多数产品对着网上搜到的资源,都会无从下手。特别当某些推荐算法 和 “AI”扯上关系后,更是加大了理解的难度。 但,不了解推荐算法,就无法做推荐系

每天认识几个maven依赖(ActiveMQ+activemq-jaxb+activesoap+activespace+adarwin)

八、ActiveMQ 1、是什么? ActiveMQ 是一个开源的消息中间件(Message Broker),由 Apache 软件基金会开发和维护。它实现了 Java 消息服务(Java Message Service, JMS)规范,并支持多种消息传递协议,包括 AMQP、MQTT 和 OpenWire 等。 2、有什么用? 可靠性:ActiveMQ 提供了消息持久性和事务支持,确保消

康拓展开(hash算法中会用到)

康拓展开是一个全排列到一个自然数的双射(也就是某个全排列与某个自然数一一对应) 公式: X=a[n]*(n-1)!+a[n-1]*(n-2)!+...+a[i]*(i-1)!+...+a[1]*0! 其中,a[i]为整数,并且0<=a[i]<i,1<=i<=n。(a[i]在不同应用中的含义不同); 典型应用: 计算当前排列在所有由小到大全排列中的顺序,也就是说求当前排列是第

csu 1446 Problem J Modified LCS (扩展欧几里得算法的简单应用)

这是一道扩展欧几里得算法的简单应用题,这题是在湖南多校训练赛中队友ac的一道题,在比赛之后请教了队友,然后自己把它a掉 这也是自己独自做扩展欧几里得算法的题目 题意:把题意转变下就变成了:求d1*x - d2*y = f2 - f1的解,很明显用exgcd来解 下面介绍一下exgcd的一些知识点:求ax + by = c的解 一、首先求ax + by = gcd(a,b)的解 这个

综合安防管理平台LntonAIServer视频监控汇聚抖动检测算法优势

LntonAIServer视频质量诊断功能中的抖动检测是一个专门针对视频稳定性进行分析的功能。抖动通常是指视频帧之间的不必要运动,这种运动可能是由于摄像机的移动、传输中的错误或编解码问题导致的。抖动检测对于确保视频内容的平滑性和观看体验至关重要。 优势 1. 提高图像质量 - 清晰度提升:减少抖动,提高图像的清晰度和细节表现力,使得监控画面更加真实可信。 - 细节增强:在低光条件下,抖

【数据结构】——原来排序算法搞懂这些就行,轻松拿捏

前言:快速排序的实现最重要的是找基准值,下面让我们来了解如何实现找基准值 基准值的注释:在快排的过程中,每一次我们要取一个元素作为枢纽值,以这个数字来将序列划分为两部分。 在此我们采用三数取中法,也就是取左端、中间、右端三个数,然后进行排序,将中间数作为枢纽值。 快速排序实现主框架: //快速排序 void QuickSort(int* arr, int left, int rig

活用c4d官方开发文档查询代码

当你问AI助手比如豆包,如何用python禁止掉xpresso标签时候,它会提示到 这时候要用到两个东西。https://developers.maxon.net/论坛搜索和开发文档 比如这里我就在官方找到正确的id描述 然后我就把参数标签换过来

usaco 1.3 Mixing Milk (结构体排序 qsort) and hdu 2020(sort)

到了这题学会了结构体排序 于是回去修改了 1.2 milking cows 的算法~ 结构体排序核心: 1.结构体定义 struct Milk{int price;int milks;}milk[5000]; 2.自定义的比较函数,若返回值为正,qsort 函数判定a>b ;为负,a<b;为0,a==b; int milkcmp(const void *va,c

poj 3974 and hdu 3068 最长回文串的O(n)解法(Manacher算法)

求一段字符串中的最长回文串。 因为数据量比较大,用原来的O(n^2)会爆。 小白上的O(n^2)解法代码:TLE啦~ #include<stdio.h>#include<string.h>const int Maxn = 1000000;char s[Maxn];int main(){char e[] = {"END"};while(scanf("%s", s) != EO

poj 1258 Agri-Net(最小生成树模板代码)

感觉用这题来当模板更适合。 题意就是给你邻接矩阵求最小生成树啦。~ prim代码:效率很高。172k...0ms。 #include<stdio.h>#include<algorithm>using namespace std;const int MaxN = 101;const int INF = 0x3f3f3f3f;int g[MaxN][MaxN];int n