精华内容
下载资源
问答
  • 拓扑排序算法适用范围:要求①有向图②有入度为0的节点③没有环 2.分析 在程序编译时,往往会有头文件互相依赖的情况,在图中箭头被指向的节点可以看做依赖指向它的节点。如下图a依赖b,c,d,而b又依赖c,k;d依赖k...

    1.题目:拓扑排序

    拓扑排序算法适用范围:要求①有向图②有入度为0的节点③没有环

    2.分析

    在程序编译时,往往会有头文件互相依赖的情况,在图中箭头被指向的节点可以看做依赖于指向它的节点。如下图a依赖于b,c,d,而b又依赖c,k;d依赖k
    在这里插入图片描述
    那么拓扑排序的输出顺序是不依赖别的点的先输出。先输出k,c,删去k,c这时没有别的节点指向b,d了,输出b,d,最后,节点只剩下a再输出。
    在图中可以用入度表示依赖情况,入度为零就是没有别的点指向它,可以先输出。输出后其指向的节点入度减一视为删去输出的点。
    过程如下:
    ①为了方便查找,使用map存储节点与入度方便查找与修改入度(不能反过来),使用queue存储入度为零的节点用于暂存需要输出的点。
    ②遍历图中的所有节点,把所有入度为零的节点放入队列
    ③输出入度为零的节点
    ④把入度为零的节点所指向的节点的入度减一(相当于删去当前节点)若减一后入度为零加入队列
    ⑤在入度为0的队列不空的情况下重复③④

    3.核心代码

    list<Node*> sortedTopology(Graph graph)
    {
    	unordered_map<Node*,int> inMap;			//存储节点与入度 
    	queue<Node*> zeroInQueue;				//存储入度为零的节点 
    	unordered_map<int,Node*>::iterator ite = graph.nodes.begin();
    	//遍历图中的所有节点,把所有入度为零的节点放入队列 
    	while(ite != graph.nodes.end())								
    	{
    		inMap.insert(pair<Node*,int>(ite->second,ite->second->in));
    		if(ite->second->in == 0)
    			zeroInQueue.push(ite->second);
    		ite++;
    	}
    	//输出入度为零的节点
    	//把入度为零的节点所指向的节点的入度减一(相当于删去当前节点)
    	//若又有入度为零的节点加入队列
    	list<Node*> result;
    	while(!zeroInQueue.empty())
    	{
    		Node* help = zeroInQueue.front();
    		zeroInQueue.pop();
    		result.push_back(help);
    		cout<<help->value<<" ";
    		for(Node* t : help->nexts)			 
    		{
    			if(--inMap.find(t)->second == 0)
    				zeroInQueue.push(t);
    		}
    	}
    	return result;
    }
    

    4.完整代码

    #include <iostream>
    #include "GraphGenerator.h"
    #include "Node.h"
    #include "Edge.h"
    #include "Graph.h"
    #include <unordered_map>
    #include <queue>
    #include <list>
    using namespace std;
    /* run this program using the console pauser or add your own getch, system("pause") or input loop */
    //拓扑排序 
    list<Node*> sortedTopology(Graph graph)
    {
    	unordered_map<Node*,int> inMap;								//存储节点与入度 
    	queue<Node*> zeroInQueue;									//存储入度为零的节点 
    	unordered_map<int,Node*>::iterator ite = graph.nodes.begin();
    	//遍历图中的所有节点,把所有入度为零的节点放入队列 
    	while(ite != graph.nodes.end())								
    	{
    		inMap.insert(pair<Node*,int>(ite->second,ite->second->in));
    		if(ite->second->in == 0)
    			zeroInQueue.push(ite->second);
    		ite++;
    	}
    	//输出入度为零的节点
    	//把入度为零的节点所指向的节点的入度减一(相当于删去当前节点)
    	//若又有入度为零的节点加入队列
    	list<Node*> result;
    	while(!zeroInQueue.empty())
    	{
    		Node* help = zeroInQueue.front();
    		zeroInQueue.pop();
    		result.push_back(help);
    		cout<<help->value<<" ";
    		for(Node* t : help->nexts)			 
    		{
    			if(--inMap.find(t)->second == 0)
    				zeroInQueue.push(t);
    		}
    	}
    	return result;
    }
    int main(int argc, char** argv) {
    	
    	vector<vector<int> > matrix= {{12,1,2},
    								  {13,1,3},
    								  {14,1,4},
    								  {9,2,7},
    								  {10,7,3},
    								  {8,3,5},
    								  {10,4,6}};
    	GraphGenerator g;
    	Graph graph = g.createGraph(matrix);
    	sortedTopology(graph);
    	return 0;
    }
    

    注:图的存储请见图的存储与表达中。

    5.输出结果

    在这里插入图片描述
    应该打印:1,2,4,7,6,3,5
    在这里插入图片描述

    展开全文
  • 拓扑排序学习前提须知 拓扑排序是对于一个图的所有节点进行...1、拓扑排序适用于有向无环图,当然也可以判定是否图为无环图 2、能够得到从一个点能到多少个其他的点,如果n在万以上,处理得当甚至能够过千万 拓扑...

    拓扑排序学习前提须知

    拓扑排序是对于一个图的所有节点进行排序,要求排序完后没有一个节点指向它前面的节点,那么这样我们就会得到一个拓扑排序后的数组,我们从后往前扫通过某种计算就能够得到从某一个点开始最多能到多少个点。

    算法内容

    竞赛需要用到的点

    1、拓扑排序仅适用于有向无环图,当然也可以判定是否图为无环图

    2、能够得到从一个点能到多少个其他的点,如果n在万以上,处理得当甚至能够过千万

    拓扑排序略讲

    拓扑排序需要满足一个很重要的条件就是,每次进入答案的点的入度一定为0,那么根据这个条件,我们就能得到我们的拓扑排序后的数组

    void toposort() {
        std::queue<int> q; //存储到目前为止入度为0的点
        std::vector<int> ans; //储存答案
        for (int i = 1; i <= n; i++) {
            if(!in[i]) q.push(i); //如果入度为0则加入队列中
        }
        
        while(!q.empty()) { //简单的搜索
            int t = q.front(); q.pop();
            ans.push_back(t);
            for (int i = head[t]; ~i; i = to[i]) {
                int v = ver[i];
                if(!in[v]) q.push(v);
            }
        }
        
        for (int i = 0; i < n; i++) { //查看拓扑排序后的数组
            printf("%d\n", ans[i]);
        } return ;
    }

    转载于:https://www.cnblogs.com/Nicoppa/p/11549836.html

    展开全文
  • 拓扑排序

    2016-05-20 15:55:00
    拓扑排序适用于有向无环图(AOV网)。 把 AOV 网中所有的活动排成一个序列,使每个活动的所有前驱活动都排在该活动之前,这个过程就是“拓扑排序”,所得到的序列就是拓扑序列。 【算法思想】 (1)选择一个...
    【定义】
            拓扑排序,适用于有向无环图(AOV网)。
            把 AOV 网中所有的活动排成一个序列,使每个活动的所有前驱活动都排在该活动之前,这个过程就是“拓扑排序”,所得到的序列就是拓扑序列。
       
    拓扑排序 - 区庆亮 - 区庆亮的博客
     【算法思想】
    (1)选择一个入度为0的定点输出。
    (2)然后把删除以此节点为起点的所有关联边。转(1),直到不存在入度为0的节点。
    (3)假如输出的顶点数小于AOV网的顶点,则有回路。
     我们可以用邻接矩阵来删除所有的关联边,用栈来控制拓扑序列。
     


    【程序】
    # include <cstdio>
    using namespace std;
    int n,j,i,tot=0,tmp=0,num=0;
    int r[101]; //入度
    int c[101]; //出度
    int a[101][101]; //邻接矩阵
    int ans[101]; //栈
    int main()
    {
        scanf("%d",&n);
        for(i=1;i<=n;i++)
        {
            do{
                scanf("%d",&j);
                if(j!=0)
                {
                    c[i]++; //点 i 的出度
                    a[i][c[i]]=j;
                    r[j]++; // 点 i 的入度 
                }
            }while(j!=0);
        }
        for(i=1;i<=n;i++)
            if(r[i]==0) ans[++tot]=i;//把AOV网中所有度为 0 的节点入栈
        do{
            tmp=ans[tot];
            printf("%d ",tmp);
            tot--; num++;//出栈并输出
            for(i=1;i<=c[tmp];i++)
            {
                r[a[tmp][i]]--;//删除所有关联边
                if(r[a[tmp][i]]==0) ans[++tot]=a[tmp][i];//如果入度减1为0,则入栈
            }
        }while(num!=n);//如果输出的点的数目等于AOV网的顶点数,就结束
        return 0;
    }

    转载于:https://www.cnblogs.com/ouqingliang/p/9245337.html

    展开全文
  • 拓扑排序(Topological...拓扑排序算法适用于AOV网,它是一种有向无环图,那么到底什么是AOV网呢? 在日常生活中,一项大工程可以看作是由若干个小工程组成的,但这些小工程之间必定存在一些先后顺序,也就是说,有些

    拓扑排序(Topological Sorting)

    这篇文章我们来讲一下拓扑排序,这可是一个很重要也很实用的算法,面试中常考,工作中常用,无论是互联网公司还是金融公司,考算法的时候都贼喜欢问这个。
    拓扑排序其实并不是一个传统意义上的排序算法,它是针对AOV网线性输出的过程,所以我们先来了解一下AOV网是什么东西。

    AOV网

    拓扑排序算法只适用于AOV网,它是一种有向无环图,那么到底什么是AOV网呢?
    在日常生活中,一项大工程可以看作是由若干个小工程组成的,但这些小工程之间必定存在一些先后顺序,也就是说,有些工程必须在其它一些工程完成之后才能开始。我们可以用有向图来形象地表示这些工程之间的先后关系,小工程为顶点,之间的先后关系为有向边,绘制成的有向图就是AOV网。一个AOV网必定是一个有向无环图,也就是不应该带有回路,否则就会出现先后关系的自相矛盾。
    例如,假定一个计算机专业的学生必须完成下图所列出的全部课程。
    在这里插入图片描述

    在这里,每个课程就代表一个小工程,学习一门课程就表示进行一项工程,学习每门课程的先决条件是学完它的全部先修课程。如学习《高等数学》课程则可以随时安排,因为它是基础课程,没有先修课。学习《数据结构》课程就必须安排在学完它的两门先修课程《离散数学》和《算法语言》之后。
    在这里插入图片描述

    若用AOV网来表示这种课程安排的先后关系,则如上图所示。图中的每个顶点代表一门课程,每条有向边代表起点对应的课程是终点对应课程的先修课。从图中可以清楚地看出各课程之间的先修和后续的关系。如课程C5的先修课为C2,后续课程为C4和C6。
    在这里插入图片描述

    拓扑排序

    那么拓扑排序到底是干什么的呢?如果我们要安排课表,那么不可能直接把AOV图给学生看,而是需要把它排成一个序列,使得每个课程的先修课都排在该课程的前面,这个过程就称为“拓扑排序”。拓扑排序得到的序列并不是唯一的,就好像你早上穿衣服可以先穿内衣再穿外套,然后再穿裤子,也可以先穿裤子再穿内衣,最后再穿外套,只要内衣在外套之前穿就行。
    拓扑排序得到的序列可以帮助我们合理安排一个工程的进度,所以,由AOV网构造拓扑序列具有很高的实际应用价值。

    算法思想

    构造拓扑序列的拓扑排序算法思想很简单:
    (1)选择一个入度为0的顶点;
    (2)从AOV网中删除此顶点及以此顶点为起点的关联边;
    (3)重复上述两步直到不存在入度为0的顶点为止;
    (4)若AOV网中还有顶点,则说明有向图存在回路。

    算法实现

    class Graph {
    	int V;				// 顶点个数 
    	int* indegree;		// 顶点入度 
    	list<int> *adj;		// 邻接表 
    	
    	public:
    	Graph(int v) {
    		this->V = v;
    		this->adj = new list<int>[v];
    		this->indegree = new int[v];
    		for(int i = 0; i < v; i++) {
    			this->indegree[i] = 0;
    		}
    	}
    	~Graph() {
    		delete [] this->adj;
    		delete [] this->indegree;
    	}
    	void addEdge(int v, int w) {
    		this->adj[v].push_back(w);
    		this->indegree[w]++;
    	}
    	vector<int> topologicalSort() {
    		vector<int> res;	// 拓扑序列 
    		queue<int> que;		// 入度为0顶点集合 
    		
    		for(int i = 0; i < this->V; i++) {
    			if (this->indegree[i] == 0) {
    				que.push(i);
    			}
    		}
    		while(!que.empty()) {
    			int front = que.front();
    			que.pop();
    			res.push_back(front);
    			for(int item:this->adj[front]) {
    				if (!(--this->indegree[item])) {
    					que.push(item);
    				}
    			}
    		}
    		return res.size() == this->V ? res : vector<int> ();
    	}
    };
    

    测试

    在这里插入图片描述

    int main(){
        Graph graph(8);
        graph.addEdge(0,1);
        graph.addEdge(0,2);
        graph.addEdge(2,4);
        graph.addEdge(1,4);
        graph.addEdge(1,3);
        graph.addEdge(4,3);
        graph.addEdge(4,5);
        graph.addEdge(4,6);
        graph.addEdge(3,5);
        graph.addEdge(6,7);
        graph.addEdge(5,7);
        graph.addEdge(3,7);
        for (int item:graph.topologicalSort()) {
        	cout << item << " ";
    	}
        return 0;
    }
    

    ![image.png](https://img-blog.csdnimg.cn/img_convert/29f28d731b4cfe0a2af3b36fead1c0b1.png#align=left&display=inline&height=99&margin=[object Object]&name=image.png&originHeight=99&originWidth=513&size=4507&status=done&style=none&width=513)

    练习题

    LeetCode 1203.项目管理

    展开全文
  • 拓扑排序与关键路径

    2020-07-15 22:15:05
    拓扑排序(只适用于AOV网(有向无环图)) 运用 : 事务先后(非唯一) 拓扑排序思路: 1.选择一个入度为 0 的点 并输出 2.从AOV网中删除此顶点以及此顶点为起点的所有关联边 3.重复上述两步,直到不存在入度为0的...
  • 复习--拓扑排序

    2018-02-01 21:36:00
    拓扑排序算法,只适用于AOV网(有向无环图)。  把AOV网中的所有活动排成一个序列, 使得每个活动的所有前驱活动都排在该活动的前面,这个过程称为“拓扑排序”,所得到的活动序列称为“拓扑序列”。 一个AOV网的...
  • 适用于 AOV网 (有向无环图) 算法流程: 用队列来执行 ,初始化讲所有入度为0的顶点入队。 主要由以下两步循环执行,直到不存在入度为 0 的顶点为止 选择一个入度为 0 的顶点,并将它输出; 删除图中从顶点连出的...
  • 适用于有向无环图 有向图无环图一定有拓扑排序 核心算法: 把入度为0的点存放在队列里面 删除该顶点连接的所有边 解题步骤: 记录每个点的入度大小 把入度为0的点放入队列中去 用一个dist[]数组存放路径的...
  • 拓扑排序适用于有向无环图 拓扑排序规则如下: (1) 从有向无环图中选择一个没有前驱(入度为0)的顶点vertex,并将顶点输出 (2)从图中删除这个顶点,同时删除从该顶点出发的所有边 本文算法复杂度为 O(n+e); ...
  • 拓扑排序--容易看懂

    2009-12-18 22:18:49
    拓扑排序,检验是否有圈,只用到数组,适用于初学者,仔细看一遍便知道算法
  • 一:算法描述 求单源最短路的SPFA算法...当然,我们可以在执行该算法前做一次拓扑排序,以判断是否存在负权回路。二:算法基本步骤 几乎所有的最短路径算法都是以下两个步骤: ①初始化 ②松弛操作初始化: dis数组
  • 图——常见算法

    2018-04-28 16:07:00
    1.拓扑排序算法 适用范围: 要求有向图, 且有入度为0的节点, 且没有环 2.最小生成树算法: (1).kruskal算法 适用范围: 要求无向图 (2).prim算法 适用范围: 要求无向图 3.Dijkstra算法 适用范围: 没有...
  • kruskal 算法复杂度为mlogm,适用于稀疏图 prim算法复杂度为nlogm ,适用于稠密图 拓扑排序:有向无环图
  • 2 广度优先算法适用于没有加权边的情况 3 拓扑排序,一个节点依赖于另一个节点,这种有顺序的行为成为拓扑排序 4 有加权边的时候要用狄克斯特拉算法,狄克斯特拉算法不能算有负加权边的情况 5 有负加权边的时候要用...
  • 算法总结

    2020-08-14 19:19:55
    算法总结 第三讲 搜索与图论 DFS ...适用于:无负环的有向图 方法: ① 所有的结点均有入度 ② 入度为0时,加入队列中 ③枚举所有结点获取入度为0的结点,加入队列中(初始化) ④ 队列不为空时  
  • Dijkstra算法及优化

    2021-03-11 21:48:03
    2.朴素Dijkstra算法,,适用于稠密图,n^2<m时,注意这时邻接矩阵不能越界,当然可以用邻接表存 #include<iostream> #include<cstring> using namespace std; const int N=1e5+10; const int INF=0x3...
  • 1、Bellman-Ford算法:解决的是一般情况下的单源最短路径问题,可适用于边的权重为负值,且有环路的情况,算法返回一个bool值,表明是否存在一个从源结点可以到达的权重为负值的环路。如果存在,则返回false,否则,...
  • 图的两种表示方法邻接矩阵和邻接表的方法适用于稠密图和稀疏图; 拓扑排序不是唯一的,任意合理的排序都是可以的; 简单的求拓扑的算法是:先找出任意一个没有入边的顶点,然后显示出该顶点,并将它和它的边一起从...
  • 本笔记适用于目标在于掌握基础算法的工程师 There are problems in leetcode, most of code are C++ and Javascript, and I will keep updating every day, just for learning how to improve coding skill. And I ...
  • 各种应用中的信息通常表示为有限字母上的字符序列(例如,DNA或蛋白质序列)。 在大数据时代,这些序列的长度和大小呈爆炸性增长,这给经典的NP-hard问题带来了巨大挑战,即...算法适用于更长和更大规模的序列比对。
  • 算法导论第24章 单源最短路径

    千次阅读 2014-01-06 22:07:26
    1、Bellman-Ford算法:解决的是一班情况下的单源最短路径问题,可适用于边的权重为负值,且有环路的情况,算法返回一个bool值,表明是否存在一个从源结点可以到达的权重为负值的环路。如果存在,则返回false,否则,...
  • 多边形区域三角化的基本思想是 :首先将简单多边形分解为多个单调多边形 ,然后对每个单调多边形进行...该算法充分利用多边形的顶点、边的拓扑关系 ,计算量少、实现简单 ,适用于带有洞、岛的任意简单多边形 ,速度较快。
  • 算法导论(part1)

    热门讨论 2010-09-09 22:51:05
    8.1 排序算法时间的下界 8.2 计数排序 8.3 基数排序 8.4 桶排序 第9章 中位数和顺序统计学 9.1 最小值和最大值 9.2 以期望线性时间做选择 9.3 最坏情况线性时间的选择 第三部分 数据结构 引言 第10...
  • 算法导论(part2)

    2010-09-09 22:54:12
    8.1 排序算法时间的下界 8.2 计数排序 8.3 基数排序 8.4 桶排序 第9章 中位数和顺序统计学 9.1 最小值和最大值 9.2 以期望线性时间做选择 9.3 最坏情况线性时间的选择 第三部分 数据结构 引言 第10...
  • 本丛书适用于参加ACM国际大学生程序设计竞赛的本科生和研究生,对参加青少年信息学奥林匹克竞赛的中学生也很有指导价值。同时,作为程序设计、数据结构、算法等相关课程的拓展与提升,本丛书也是难得的教学辅助读物...
  • 2.4.4 用N-S 流程图表示算法 29 2.4.5 用伪代码表示算法 30 2.4.6 用计算机语言表示算法 31 2.5 结构化程序设计方法 31 3 数据类型、运算符与表达式 3.1 C语言的数据类型 32 3.2 常量与变量 33 23.2.1 常量和符号...

空空如也

空空如也

1 2 3
收藏数 52
精华内容 20
关键字:

拓扑排序算法适用于