首页
学习
活动
专区
圈层
工具
发布
首页
学习
活动
专区
圈层
工具
MCP广场
社区首页 >专栏 >图Graph--拓扑排序(Topological Sorting)

图Graph--拓扑排序(Topological Sorting)

作者头像
Michael阿明
发布于 2021-02-20 02:54:04
发布于 2021-02-20 02:54:04
61700
代码可运行
举报
运行总次数:0
代码可运行

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

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

1. 拓扑排序

  • 可以把源文件与源文件之间的依赖关系,抽象成一个有向图。每个源文件对应图中的一个顶点,源文件之间的依赖关系就是顶点之间的边。
  • 如果a先于b执行,也就是说b依赖于a,那么就在顶点a和顶点b之间,构建一条从a指向b的边。而且,这个图不仅要是有向图,还要是一个有向无环图,也就是不能存在像a->b->c->a这样的循环依赖关系。

数据结构如下:

代码语言:javascript
代码运行次数:0
运行
AI代码解释
复制
#include <list>
using namespace std;
class Graph
{
    int v;//顶点个数
    list<int> *adj;//邻接表
public:
    Graph(int vn)
    {
        v = vn;
        adj = new list<int> [v];
    }
    ~Graph()
    {
        delete [] adj;
    }
    void addEdge(int s, int t)//s先于t,边s->t
    {
        adj[s].push_back(t);
    }
};

2. 算法实现

2.1 Kahn算法

  • Kahn 算法是贪心思想
  • 如果 s 需要先于 t 执行,就添加一条 s 指向 t 的边。如果某个顶点入度为0,也就表示,没有任何顶点必须先于这个顶点执行,那么这个顶点就可以执行了。
  • 先从图中,找出一个入度为0的顶点,将其输出,并删除这个顶点(也就是把这个顶点可达的顶点的入度都减1)。我们循环执行上面的过程,直到所有的顶点都被输出。最后输出的序列,就是满足局部依赖关系的拓扑排序。
代码语言:javascript
代码运行次数:0
运行
AI代码解释
复制
/**
 * @description: 拓扑排序,有向无环图
 * @author: michael ming
 * @date: 2019/7/29 0:36
 * @modified by: 
 */
#include <list>
#include <iostream>
#include <queue>

using namespace std;
class G_Node    //节点类
{
public:
    char info;//节点存储信息
    int indegree;//节点入度
    G_Node(char ch = '/'):info(ch),indegree(0){};
};
class Graph //图类
{
    int v;  //顶点个数
    list<G_Node*> *adj;  //邻接表
    G_Node *pGNode;//节点
public:
    Graph(int vn)
    {
        v = vn;
        adj = new list<G_Node*> [v];
        pGNode = new G_Node [v];
        cout << "请顺序输入节点的信息:" << endl;
        char ch;
        for(int i = 0; i < v; ++i)
            cin >> pGNode[i].info;
    }
    ~Graph()
    {
        delete [] pGNode;
        delete [] adj;
    }
    int findIdx(char ch)
    {
        for(int i = 0; i < v; ++i)
        {
            if(pGNode[i].info == ch)
                return i;
        }
        return -1;
    }
    void addEdge(char s, char t)//s先于t,边s->t
    {
        int i = findIdx(s), j = findIdx(t);
        if(i != -1 && j != -1)
        {
            adj[i].push_back(&pGNode[j]);
            pGNode[j].indegree++;
        }
    }
    void topoSortByKahn()
    {
        int i, j, k;
        queue<G_Node*> nodeQueue;
        //坑,要存指针在里面,后面才能修改入度,否则修改的是副本
        G_Node *frontNode;
        list<G_Node*>::iterator it;
        for(i = 0; i < v; ++i)
        {
            if(pGNode[i].indegree == 0)
                nodeQueue.push(&pGNode[i]);//找到所有入度为0的入队
        }
        while(!nodeQueue.empty())
        {
            frontNode = nodeQueue.front();
            i = findIdx(frontNode->info);
            nodeQueue.pop();
            cout << frontNode->info << "->";//输出入度为0的,出队
            for(it = adj[i].begin(); it != adj[i].end(); ++it)
            {
                (*it)->indegree--;//该节点后面跟着的所有节点入度-1
                if((*it)->indegree == 0)//入度如果等于0
                    nodeQueue.push(*it);//入队,一会可以打印了
            }
        }
    }
};
int main()
{
    Graph grp(6);
    grp.addEdge('a','b');
    grp.addEdge('b','e');
    grp.addEdge('b','d');
    grp.addEdge('d','c');
    grp.addEdge('d','f');
    grp.topoSortByKahn();
    return 0;
}

2.2 DFS算法

  • 构造逆邻接表。邻接表中,边 s->t 表示 s 先于 t 执行,也就是 t 要依赖 s。在逆邻接表中,边 s->t 表示 s 依赖于 t,s 后于 t 执行。
  • 递归处理每个顶点。对顶点 i ,先输出它可达的所有顶点,也就是,先把它依赖的所有的顶点输出了,然后再输出自己

在上面程序代码中添加

代码语言:javascript
代码运行次数:0
运行
AI代码解释
复制
list<G_Node*> *reverseadj;  //逆邻接表
reverseadj = new list<G_Node*> [v];
代码语言:javascript
代码运行次数:0
运行
AI代码解释
复制
void addEdge(char s, char t)//s先于t,边s->t
{
      int i = findIdx(s), j = findIdx(t);
      if(i != -1 && j != -1)
      {
          adj[i].push_back(&pGNode[j]);//s->t,邻接表
          pGNode[j].indegree++;
          reverseadj[j].push_back(&pGNode[i]);//逆邻接表
      }
  }
代码语言:javascript
代码运行次数:0
运行
AI代码解释
复制
void topoSortByDFS()
{
    cout << "topoSortByDFS:" << endl;
    bool *visited = new bool [v];
    memset(visited,0,v*sizeof(bool));
    for(int i = 0; i < v; ++i)  //深度优先遍历
    {
        if(visited[i] == false)
        {
            visited[i] = true;
            dfs(i, reverseadj, visited);
        }
    }
    delete [] visited;
}
void dfs(int i, list<G_Node*> *reverseadj, bool *visited)
{
    int idx;
    for(auto it = reverseadj[i].begin(); it != reverseadj[i].end(); ++it)
    {
        idx = findIdx((*it)->info);
        if(visited[idx] == true)
            continue;
        visited[idx] = true;
        dfs(idx,reverseadj,visited);
    }
    cout << pGNode[i].info << "->";
}

2.3 时间复杂度

  • Kahn代码中,每个顶点被访问了一次,每个边也都被访问了一次,所以,Kahn算法的时间复杂度就是O(V+E)(V表示顶点个数,E表示边的个数)。
  • DFS算法中,每个顶点被访问两次,每条边都被访问一次,所以时间复杂度也是O(V+E)。
  • 注意,这里的图可能不是连通的,有可能是有好几个不连通的子图构成,所以,E并不一定大于V,V E的大小关系不定。所以,在表示时间复杂度的时候,V、E都要考虑在内。

3. 应用

  • 拓扑排序应用非常广泛。凡是需要通过局部顺序推导全局顺序的,一般都能用拓扑排序来解决。
  • 拓扑排序还能检测图中环的存在。对于Kahn算法来说,如果最后输出出来的顶点个数,少于图中顶点个数,图中还有入度不是0的顶点,那就说明,图中存在环。
  • 关于图中环的检测,递归那节讲过一个例子,在查找最终推荐人的时候,可能会因为脏数据,造成存在循环推荐,比如,用户A推荐了用户B,用户B推荐了用户C,用户C又推荐了用户A。如何避免这种脏数据导致的无限递归? 这就是环的检测问题。因为我们每次都只是查找一个用户的最终推荐人,所以,我们并不需要动用复杂的拓扑排序算法,而只需要记录已经访问过的用户ID,当用户ID第二次被访问的时候,就说明存在环。

4. 类似题目练习

LeetCode 207. 课程表(拓扑排序)

LeetCode 210. 课程表 II(拓扑排序)

LeetCode 269. 火星词典(拓扑排序)

LeetCode 851. 喧闹和富有(拓扑排序)

LeetCode 1136. 平行课程(拓扑排序)

LeetCode 1203. 项目管理(两次拓扑排序)

LeetCode 5665. 从相邻元素对还原数组(拓扑排序)

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

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

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

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

评论
登录后参与评论
暂无评论
推荐阅读
编辑精选文章
换一批
文心一言 VS 讯飞星火 VS chatgpt (358)-- 算法导论24.2 4题
要计算一个有向无环图(DAG)中的路径总数,我们可以使用动态规划(Dynamic Programming, DP)的方法。具体来说,我们可以使用拓扑排序确保我们总是先处理那些没有依赖的节点,然后再计算那些依赖于前面节点的路径总数。
福大大架构师每日一题
2024/10/08
1490
文心一言 VS 讯飞星火 VS chatgpt (358)-- 算法导论24.2 4题
算法细节系列(17):有向环检测&&拓扑排序
版权声明:本文为博主原创文章,未经博主允许不得转载。 https://blog.csdn.net/u014688145/article/details/71719530
用户1147447
2019/05/26
7550
【JavaScript 算法】拓扑排序:有向无环图的应用
DFS方法通过递归遍历图,将访问过的节点存入栈中,最终从栈顶依次取出节点构建拓扑序列。
空白诗
2024/07/20
4510
【JavaScript 算法】拓扑排序:有向无环图的应用
leetcode 207. 课程表---拓扑排序篇一
本题涉及到了拓扑排序相关的概念,如果对拓扑排序不了解的,建议看这篇文章AOV网与拓扑排序
大忽悠爱学习
2021/11/15
6710
如何去理解 拓扑排序算法
查看Castle的代码,在Castle.Core中内部的数据结构采用图,排序使用的拓扑排序算法:        对于一条有向边(u,v),定义u < v;满足所有这样条件的结点序列称为拓扑序列。拓扑排序就是求一个有向图的拓扑序列的算法。 一个有向图顶点的拓扑序列不是惟一的。并不是任何有向图的顶点都可以排成拓扑序列,有环图是不能排的。 例子:比如排课问题,比如士兵排队问题等。        拓扑排序在实际生活中和算法中都有很大的应用。比如要排一下几门课程的先后次序,我们可以把课程抽象成结点,把什么课是什么课的
张善友
2018/01/19
1.1K0
如何去理解 拓扑排序算法
文心一言 VS 讯飞星火 VS chatgpt (323)-- 算法导论22.4 4题
四、证明或反证下述论断:如果有向图G包含环路,则在算法TOPOLOGICAL-SORT(G)所生成的结点序列里,图G中与所生成序列不一致的“坏”边的条数最少。如果要写代码,请用go语言。
福大大架构师每日一题
2024/08/16
1410
文心一言 VS 讯飞星火 VS chatgpt (323)-- 算法导论22.4 4题
文心一言 VS 讯飞星火 VS chatgpt (324)-- 算法导论22.4 5题
五、在有向无环图$G=(V,E)$上执行拓扑排序还有一种办法,就是重复寻找入度为 0 的结点,输出该结点,将该结点及从其发出的边从图中删除。请解释如何在$O(V+E)$的时间内实现这种思想。如果图$G$包含环路,将会发生什么情况?如果要写代码,请用go语言。
福大大架构师每日一题
2024/08/16
1280
文心一言 VS 讯飞星火 VS chatgpt (324)-- 算法导论22.4 5题
数据结构算法整理-06-图
V0与V1、V2、V3都有边,因此第0行的1、2、3位置处置1。 Vi与Vj有边,则第i行的第j位置处置1。
devi
2021/08/18
2460
环检测算法及拓扑排序(修订版)
首先,我说将后序遍历结果进行反转就是拓扑排序的结果,有的读者说他看到的很多解法直接使用后序遍历,并没有进行反转,本文新增了对此的解释。
labuladong
2022/03/30
1.4K0
环检测算法及拓扑排序(修订版)
5.4.3拓扑排序
AOV网:如果用DAG图表示一个工程,其顶点表示活动,用有向边<Vi,Vj>表示活动Vi必须先于活动Vj进行的这样一种关系,则将这种有向图称为顶点表示活动的网络,记为AOV网。在AOV网中,活动Vj是活动Vi的直接后继,这种前驱和后继关系具有传递性,且任何活动Vi不能以它自己作为自己的前驱或后继。
week
2018/08/24
3990
AOV网与拓扑排序
图解演示拓扑排序的过程 不是AOV网的情况 由下可知,当前图中存在回路,不是AOV网 拓扑排序的数据结构 编程流程 拓扑排序算法伪代码 完整代码 #include<iostream> using namespace std; #include<stack> #define MAX 10//最大顶点数为10 //边表结构体 typedef struct EdgeNode { int agjvex;//邻接点域,存储顶点对应的下标 //int weight;//用来存储权值,对于非网图这
大忽悠爱学习
2021/04/01
4030
AOV网与拓扑排序
有向无环图(DAG)的温故知新
当我们学习数据结构的时候,总是觉得很枯燥,而当我们解决实际问题的时候,又往往因为对数据结构了解的匮乏而束手无策。从问题中来,到问题中去,在某一点上的深入思考并且不断的实践积累,或许是个笨办法,但笨办法总是比没办法好一些。本文是老码农对DAG的随手笔记,积累成文。
半吊子全栈工匠
2021/08/06
10.2K1
(Graph)图,挑着看看
这个数据结构很繁琐,说实话我不喜欢。但是不学吧,总觉得我在数据结构这一块有个大漏洞。 在网上各处搜罗,看了大家对于面试会问到的有关图的内容,想了想,就先整理那部分吧。
看、未来
2020/08/26
4710
(Graph)图,挑着看看
iOS算法——图的拓扑排序
一个 无环的有向图称为有向无环图(Directed Acycline Graph),简称DAG图,所以直接看图。
CC老师
2022/01/14
6890
iOS算法——图的拓扑排序
【拓扑排序】有向无环图、定点活动图、拓扑排序简介
​ DAG 图全称为 Directed Acyclic Graph,就是一个有向 + 无环的图。
利刃大大
2025/03/12
1940
【拓扑排序】有向无环图、定点活动图、拓扑排序简介
数据结构小记【Python/C++版】——图结构篇
权重(Weight):边上可以附带的权重大小,用来表示从一个顶点到另一个顶点的成本。
Coder-ZZ
2023/02/23
5830
数据结构小记【Python/C++版】——图结构篇
无回路有向图的拓扑排序
因公司业务需要,在表单中每个字段都会配置自动计算,但自动计算公式中会引用到其他字段中的值。所以希望可以根据计算公式,优先计算引用的公式。所以最终使用了无回路有向图的扩扑排序来实现。
兜兜毛毛
2019/10/23
1K0
无回路有向图的拓扑排序
Android 启动优化(二) - 拓扑排序的原理以及解题思路
春节之前,更新了一篇博客 Android 启动优化(一) - 有向无环图,反响还不错,今天,让我们一起来看一下,怎样用代码实现有向无环图。
程序员徐公
2021/03/15
6690
BFS:解决拓扑排序问题
要知道什么拓扑排序我们首先要知道什么是有向无环图,有向无环图我们看名字其实就很容易理解,有向就是有方向,无环就是没有环形结构,这里我们展示一下有向无环图和有向有环图:
用户11305458
2024/10/09
2000
BFS:解决拓扑排序问题
揭开「拓扑排序」的神秘面纱
上篇文章 的投票让我有点无奈,大家是不是都商量好了?那就。。anyway 这篇先来拓扑排序~
JavaFish
2020/08/24
5320
揭开「拓扑排序」的神秘面纱
推荐阅读
相关推荐
文心一言 VS 讯飞星火 VS chatgpt (358)-- 算法导论24.2 4题
更多 >
领券
问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档
本文部分代码块支持一键运行,欢迎体验
本文部分代码块支持一键运行,欢迎体验