数据结构拓扑排序

拓扑排序，判断有向图中是否有环【原创】今天我们来聊聊有向图中环的判断，在数据结构中我们知道，通过拓扑排序可以判断有向图中是否存在环，对于有向图的存储我们采⽤邻接表的形势，这⾥为了简化链表的操作，我们省略了链表，避免了指针的⿇烦，直接采⽤了c++中的vector来模拟链表，操作更加的⽅便；具体详细的使⽤，建议百度⼀下，这⾥不多说，⾄于拓扑排序的具体思想，相信⼤家应该都了解，那么直接上代码，如果有不理解的，建议查阅数据结构书籍，搞懂思想，结合这份代码，很好理解1 #include <stdio.h>2 #include <queue>3 #include<vector>4 #include<stdlib.h>5using namespace std;6//拓扑排序中使⽤的对列和模拟链表的向量7 vector<int> edge[501];//邻接链表8 queue<int> Q;//保存⼊股为0的节点9int main(){10//拓扑排序，判断⼀个有向图中是否存在环11int inDegree[501];//统计每⼀个节点的⼊度；12int n,m;13while (scanf("%d%d",&n,&m)!=EOF) {//多组数据的测试14if (m==0&&n==0) break;15for (int i = 0; i<n; i++) {16 inDegree[i] = 0;//刚开始的节点⼊度均为017 edge[i].clear();//清除前⼀组数据的残留18 }19while(m--!=0){20int a,b;//输⼊m组节点关系21 scanf("%d%d",&a,&b);22 inDegree[b]++;//出现了⼀条边指向b，所以⼊度增加123 edge[a].push_back(b);//24 }25while (Q.empty()==false) {26 Q.pop();//清除之前的数据27 }28for(int i = 0;i<n;i++){29if (inDegree[i]==0) {30 Q.push(i);31 }32 }33int cnt = 0;34while (Q.empty()==false) {//当队列中还有⼊度为0的点35int newP = Q.front();36 Q.pop();//这⾥不需要保留拓扑排序的路径，因⽽不需要保存弹出来的值37 cnt++;38for (int i = 0; i<edge[newP].size(); i++) {39 inDegree[edge[newP][i]]--;//去除⼀条边后，将所指向的后继节点的如度减140if (inDegree[edge[newP][i]]==0) {41 Q.push(edge[newP][i]);42 }43 }44 }45if (cnt==n) {46 puts("YES");47 }else{48 puts("NO");49 }50 }51return0;52 }53/**************************************************************54 Problem: 144855 User: Numen_fan56 Language: C++57 Result: Accepted58 Time:10 ms59 Memory:1064 kb60****************************************************************/注意：这份代码，输⼊两个数字n、m,n表⽰有n个节点，m表⽰有m对关系，即接下来有m⾏，每⼀⾏两个数字a、b，表⽰a到b有边，；同时这⾥可以测试多组数据，这种编程思想是很好的，不⽤测试⼀组数据酒run⼀次，⿇烦，同时，看到代码35-37⾏中，这⾥只计算cnt总数，并没有保存拓扑排序的序列，如果需要求出序列，也很容易吧，将newP节点保存即可，本例⼦中采⽤queue队列来保存⼊度为0 的节点，那么其实也可以⽤stack来保存，原因很简单，因为拓扑排序不唯⼀；。

树的拓扑序列概述树是一种常见的数据结构，它由节点和边组成，具有层次结构。

在树中，每个节点可以有零个或多个子节点，而且每个节点都只有一个父节点（除了根节点）。

树的拓扑序列是根据节点之间的父子关系确定的一种序列，它描述了树中节点的相对位置。

拓扑排序拓扑排序是一种对有向无环图（DAG）的节点进行排序的算法，它可以用来解决一些实际问题，比如任务调度、依赖关系的处理等。

在树中，由于不存在环，所以拓扑排序的结果是唯一的。

树的拓扑序列定义树的拓扑序列定义为树中节点的一种排序方式，满足以下条件： 1. 根节点是序列的第一个节点。

2. 对于任意非叶子节点，它的子节点在序列中出现在它之后。

3. 对于任意节点，它的兄弟节点在序列中相邻。

拓扑排序算法拓扑排序算法可以通过深度优先搜索（DFS）或广度优先搜索（BFS）实现。

下面以DFS为例介绍树的拓扑序列的生成过程。

1. 选择根节点从树中选择一个节点作为根节点，可以根据实际需求选择任意一个节点作为根节点。

2. 遍历子节点从根节点开始，先遍历它的所有子节点。

对于每个子节点，递归地进行步骤3和步骤4。

3. 生成子树的拓扑序列对于每个子节点，按照步骤2的方式生成它的子树的拓扑序列。

4. 合并拓扑序列将当前节点和它的子树的拓扑序列合并，得到当前节点及其子节点的拓扑序列。

5. 返回结果返回根节点及其子节点的拓扑序列作为最终结果。

示例为了更好地理解树的拓扑序列，下面以一个简单的树为例进行说明。

A/ | \B C D/ \ / \E F G H按照上述算法，树的拓扑序列为E, F, B, G, C, H, D, A。

应用树的拓扑序列在实际应用中有很多用途，下面介绍两个常见的应用场景。

1. 任务调度在任务调度中，存在一些任务之间的依赖关系。

比如，任务A依赖任务B和任务C 完成后才能开始。

这时，可以将任务之间的依赖关系表示为一棵树，树的拓扑序列就是任务的执行顺序。

2. 依赖关系处理在处理依赖关系的场景中，需要根据依赖关系确定一组操作的执行顺序。

图的拓扑排序算法图是计算机科学中常用的数据结构之一，它由一些节点（点）和连接这些节点的边（线）组成。

在计算机科学中，图经常被用来解决很多问题，例如计算机网络路由、调度、自然语言处理等等。

其中，图的拓扑排序算法是一个十分重要且广泛应用的算法。

在本文中，我们将详细介绍图的拓扑排序算法的原理及应用。

一、拓扑排序算法简介首先，我们来了解一下什么是拓扑排序算法。

拓扑排序是指将有向无环图(Directed Acyclic Graph, DAG)中节点按照拓扑序列排列的过程。

拓扑序列是指，在排列中，如果存在一条从节点A到节点B的路径，那么在拓扑序列中节点A必须出现在节点B之前。

如果存在环路，则不存在拓扑序列。

拓扑排序算法通常用于任务调度等场景中。

在计算机科学中，拓扑排序算法可以使用两种方法进行实现：基于搜索的算法和基于入度的算法。

二、基于搜索的算法基于搜索的算法是一种比较直接的实现思路，我们可以使用深度优先搜索或者广度优先搜索来实现。

深度优先搜索的方法是，先访问图中入度为0的节点，将其加入拓扑序列中，并将其后继节点的入度减1，直到遍历完整幅图。

基于入度的算法基于入度的算法是另一种有用的实现思路。

首先，我们可以记录每个节点的入度值。

入度是指图中所有指向该节点的边的个数。

对于一个拓扑序列中的节点，它的入度必定为0。

因此，我们可以将入度为0的节点放入队列中，然后对该节点的后继节点的入度减1。

如果减去入度后某个节点的入度为0，则也将其加入队列中。

不断循环这一过程，直到遍历完整幅图。

三、应用场景拓扑排序算法可以在很多场景中应用。

例如，任务调度。

在计算机中，任务调度是指将一些任务分配给不同的处理器进行处理的过程。

我们可以将每个任务看作一个节点，处理器看作边。

拓扑排序算法可以帮助我们找到一个最优的任务调度方案。

另一个应用场景是编译器和依赖管理器。

在编译一个程序时，我们需要按指定顺序编译不同的模块。

如果模块之间存在依赖关系，则需要使用拓扑排序算法来进行模块的编译顺序优化。

图基本算法拓扑排序（基于dfs） 拓扑排序，是对有向⽆回路图进⾏排序，以期找到⼀个线性序列，这个线性序列在⽣活正可以表⽰某些事情完成的相应顺序。

如果说所求的图有回路的话，则不可能找到这个序列。

在⼤学数据结构课上，我们知道求拓扑排序的⼀种⽅法。

⾸先⽤⼀个⼊度数组保存每个顶点的⼊度。

在进⾏拓扑排序时，我们需要找到⼊度为0的点，将其存⼊线性序列中，再将其从图中删除（与它相关的边都删除，相邻的顶点的⼊度均减1），再重复上⾯的操作，直⾄所有的顶点都被找到为⽌。

如果不对每次找⼊度为0的顶点的⽅法进⾏处理，⽽直接去遍历⼊度数组，则该算法的时间复杂度为O(|V|2)，如果使⽤⼀个队列来保存⼊度为0的顶点，则可以将这个算法的复杂度降为O(V+E)。

今天在算法导论上看了⽤dfs来求拓扑排序的算法，才发现其⾼深之处，膜拜之Orz…下⾯是算法导论的叙述： 本节说明了如何运⽤深度优先搜索，对⼀个有向⽆回路图（dag）进⾏拓扑排序。

对有向⽆回路图G=(V,E)进⾏拓扑排序后，结果为该图顶点的⼀个线性序列，满⾜如果G包含边（u, v），则在该序列中，u就出现在v的前⾯（如果图是有回路的，就不可能存在这样的线性序列）。

⼀个图的拓扑排序可以看成是图中所有顶点沿⽔平线排列⽽成的⼀个序列。

使得所有的有向边均从左指向右。

因此，拓扑排序不同于通常意义上的排序。

在很多应⽤中，有向⽆回路图⽤于说明时间发⽣的先后次序，下图1即给出⼀个实例，说明Bumstead教授早晨穿⾐的过程。

他必须先穿好某些⾐服，才能再穿其他⾐服（如先穿袜⼦后穿鞋），其他⼀些⾐服则可以按任意次序穿戴（如袜⼦和裤⼦），在图1中，有向边<u，v>表⽰⾐服u必须先于⾐服v穿戴。

因此，该图的拓扑排序给出了⼀个穿⾐的顺序。

图2说明了对该图进⾏拓扑排序后，将沿⽔平线⽅向形成⼀个顶点序列，使得图中所有有向边均从左指向右。

拓扑排序算法具体步骤如下：1、调⽤dfs_travel()；2、在dfs_travel()每次调⽤dfs()的过程中，都记录了顶点s的完成时间，将顶点s按完成顺序保存在存放拓扑排序顺序的数组topoSort[]中。

数据结构课设——有向图的深度、⼴度优先遍历及拓扑排序任务：给定⼀个有向图，实现图的深度优先, ⼴度优先遍历算法，拓扑有序序列，并输出相关结果。

功能要求：输⼊图的基本信息，并建⽴图存储结构（有相应提⽰），输出遍历序列，然后进⾏拓扑排序，并测试该图是否为有向⽆环图，并输出拓扑序列。

按照惯例，先上代码，注释超详细：#include<stdio.h>#include<stdlib.h>#include<malloc.h>#pragma warning(disable:4996)#define Max 20//定义数组元素最⼤个数（顶点最⼤个数）typedef struct node//边表结点{int adjvex;//该边所指向结点对应的下标struct node* next;//该边所指向下⼀个结点的指针}eNode;typedef struct headnode//顶点表结点{int in;//顶点⼊度char vertex;//顶点数据eNode* firstedge;//指向第⼀条边的指针，边表头指针}hNode;typedef struct//邻接表（图）{hNode adjlist[Max];//以数组的形式存储int n, e;//顶点数，边数}linkG;//以邻接表的存储结构创建图linkG* creat(linkG* g){int i, k;eNode* s;//边表结点int n1, e1;char ch;g = (linkG*)malloc(sizeof(linkG));//申请结点空间printf("请输⼊顶点数和边数：");scanf("%d%d", &n1, &e1);g->n = n1;g->e = e1;printf("顶点数：%d 边数：%d\n", g->n, g->e);printf("请输⼊顶点信息（字母）：");getchar();//因为接下来要输⼊字符串，所以getchar⽤于承接上⼀条命令的结束符for (i = 0; i < n1; i++){scanf("%c", &ch);g->adjlist[i].vertex = ch;//获得该顶点数据g->adjlist[i].firstedge = NULL;//第⼀条边设为空}printf("\n打印顶点下标及顶点数据：\n");for (i = 0; i < g->n; i++)//循环打印顶点下标及顶点数据{printf("顶点下标：%d 顶点数据：%c\n", i, g->adjlist[i].vertex);}getchar();int i1, j1;//相连接的两个顶点序号for (k = 0; k < e1; k++)//建⽴边表{printf("请输⼊对<i,j>（空格分隔）：");scanf("%d%d", &i1, &j1);s = (eNode*)malloc(sizeof(eNode));//申请边结点空间s->adjvex = j1;//边所指向结点的位置，下标为j1s->next = g->adjlist[i1].firstedge;//将当前s的指针指向当前顶点上指向的结点g->adjlist[i1].firstedge = s;//将当前顶点的指针指向s}return g;//返回指针g}int visited[Max];//标记是否访问void DFS(linkG* g, int i)//深度优先遍历{eNode* p;printf("%c ", g->adjlist[i].vertex);visited[i] = 1;//将已访问过的顶点visited值改为1p = g->adjlist[i].firstedge;//p指向顶点i的第⼀条边while (p)//p不为NULL时（边存在）{if (visited[p->adjvex] != 1)//如果没有被访问DFS(g, p->adjvex);//递归}p = p->next;//p指向下⼀个结点}}void DFSTravel(linkG* g)//遍历⾮连通图{int i;printf("深度优先遍历;\n");//printf("%d\n",g->n);for (i = 0; i < g->n; i++)//初始化为0{visited[i] = 0;}for (i = 0; i < g->n; i++)//对每个顶点做循环{if (!visited[i])//如果没有被访问{DFS(g, i);//调⽤DFS函数}}}void BFS(linkG* g, int i)//⼴度优先遍历{int j;eNode* p;int q[Max], front = 0, rear = 0;//建⽴顺序队列⽤来存储，并初始化printf("%c ", g->adjlist[i].vertex);visited[i] = 1;//将已经访问过的改成1rear = (rear + 1) % Max;//普通顺序队列的话，这⾥是rear++q[rear] = i;//当前顶点（下标）队尾进队while (front != rear)//队列⾮空{front = (front + 1) % Max;//循环队列，顶点出队j = q[front];p = g->adjlist[j].firstedge;//p指向出队顶点j的第⼀条边while (p != NULL){if (visited[p->adjvex] == 0)//如果未被访问{printf("%c ", g->adjlist[p->adjvex].vertex);visited[p->adjvex] = 1;//将该顶点标记数组值改为1rear = (rear + 1) % Max;//循环队列q[rear] = p->adjvex;//该顶点进队}p = p->next;//指向下⼀个结点}}}void BFSTravel(linkG* g)//遍历⾮连通图{int i;printf("⼴度优先遍历：\n");for (i = 0; i < g->n; i++)//初始化为0{visited[i] = 0;}for (i = 0; i < g->n; i++)//对每个顶点做循环{if (!visited[i])//如果没有被访问过{BFS(g, i);//调⽤BFS函数}}}//因为拓扑排序要求⼊度为0，所以需要先求出每个顶点的⼊度void inDegree(linkG* g)//求图顶点⼊度{eNode* p;int i;for (i = 0; i < g->n; i++)//循环将顶点⼊度初始化为0{g->adjlist[i].in = 0;}for (i = 0; i < g->n; i++)//循环每个顶点{p = g->adjlist[i].firstedge;//获取第i个链表第1个边结点指针while (p != NULL)///当p不为空（边存在）{g->adjlist[p->adjvex].in++;//该边终点结点⼊度+1p = p->next;//p指向下⼀个边结点}printf("顶点%c的⼊度为：%d\n", g->adjlist[i].vertex, g->adjlist[i].in);}void topo_sort(linkG *g)//拓扑排序{eNode* p;int i, k, gettop;int top = 0;//⽤于栈指针的下标索引int count = 0;//⽤于统计输出顶点的个数int* stack=(int *)malloc(g->n*sizeof(int));//⽤于存储⼊度为0的顶点for (i=0;i<g->n;i++)//第⼀次搜索⼊度为0的顶点{if (g->adjlist[i].in==0){stack[++top] = i;//将⼊度为0的顶点进栈}}while (top!=0)//当栈不为空时{gettop = stack[top--];//出栈,并保存栈顶元素（下标）printf("%c ",g->adjlist[gettop].vertex);count++;//统计顶点//接下来是将邻接点的⼊度减⼀，并判断该点⼊度是否为0p = g->adjlist[gettop].firstedge;//p指向该顶点的第⼀条边的指针while (p)//当p不为空时{k = p->adjvex;//相连接的顶点（下标）g->adjlist[k].in--;//该顶点⼊度减⼀if (g->adjlist[k].in==0){stack[++top] = k;//如果⼊度为0，则进栈}p = p->next;//指向下⼀条边}}if (count<g->n)//如果输出的顶点数少于总顶点数，则表⽰有环{printf("\n有回路！\n");}free(stack);//释放空间}void menu()//菜单{system("cls");//清屏函数printf("************************************************\n");printf("* 1.建⽴图 *\n");printf("* 2.深度优先遍历 *\n");printf("* 3.⼴度优先遍历 *\n");printf("* 4.求出顶点⼊度 *\n");printf("* 5.拓扑排序 *\n");printf("* 6.退出 *\n");printf("************************************************\n");}int main(){linkG* g = NULL;int c;while (1){menu();printf("请选择：");scanf("%d", &c);switch (c){case1:g = creat(g); system("pause");break;case2:DFSTravel(g); system("pause");break;case3:BFSTravel(g); system("pause");break;case4:inDegree(g); system("pause");break;case5:topo_sort(g); system("pause");break;case6:exit(0);break;}}return0;}实验⽤图:运⾏结果：关于深度优先遍历 a.从图中某个顶点v 出发，访问v 。

数据结构之拓扑排序算法详解拓扑排序算法是一种常用于有向无环图（DAG）的排序算法，它可以将图中的顶点按照一定的顺序进行排序，使得图中任意一条有向边的起点在排序结果中都排在终点的前面。

在实际应用中，拓扑排序算法常用于解决任务调度、依赖关系分析等问题。

本文将详细介绍拓扑排序算法的原理、实现方法以及应用场景。

### 一、拓扑排序算法原理拓扑排序算法的原理比较简单，主要包括以下几个步骤：1. 从DAG图中选择一个入度为0的顶点并输出。

2. 从图中删除该顶点以及以该顶点为起点的所有有向边。

3. 重复步骤1和步骤2，直到图中所有顶点都被输出。

### 二、拓扑排序算法实现下面以Python语言为例，给出拓扑排序算法的实现代码：```pythondef topological_sort(graph):in_degree = {v: 0 for v in graph}for u in graph:for v in graph[u]:in_degree[v] += 1queue = [v for v in graph if in_degree[v] == 0] result = []while queue:u = queue.pop(0)result.append(u)for v in graph[u]:in_degree[v] -= 1if in_degree[v] == 0:queue.append(v)if len(result) == len(graph):return resultelse:return []# 测试代码graph = {'A': ['B', 'C'],'B': ['D'],'C': ['D'],'D': []}print(topological_sort(graph))```### 三、拓扑排序算法应用场景拓扑排序算法在实际应用中有着广泛的应用场景，其中包括但不限于以下几个方面：1. 任务调度：在一个任务依赖关系图中，拓扑排序可以确定任务的执行顺序，保证所有任务按照依赖关系正确执行。

拓扑数据结构的名词解释随着科技的快速发展，数据的规模和复杂度急剧增加，大数据和人工智能成为了当今世界的热点话题。

在处理如此庞大和复杂的数据时，拓扑数据结构扮演着重要的角色。

本文将对拓扑数据结构的相关术语进行解释，帮助读者更好地理解这一概念。

一、图 (Graph)图是拓扑数据结构的基础。

它由节点集合和边集合组成。

节点代表实体，边则表示节点之间的关系。

图可以用来描述各种各样的关系网络，如社交网络、交通网络等。

图可以分为有向图和无向图，有向图的边是有方向的，而无向图的边是无方向的。

二、节点 (Node)节点是图的基本元素，也称为顶点。

每个节点可以具有零个或多个关联的边，用来表示节点之间的关系。

节点可以包含数据、属性和其他相关信息。

三、边 (Edge)边是图中节点之间的连接线。

边可以是有向的，表示从一个节点到另一个节点的单向关系；也可以是无向的，表示两个节点之间的双向关系。

边可以具有权重，用来表示节点之间的关联强度或距离。

四、路径 (Path)路径是图中的一条连接序列，由一系列的边组成。

路径可以是闭合的，即起点和终点相同，形成环；也可以是非闭合的，连接不同的节点。

五、连通性 (Connectivity)连通性是指图中节点之间的关联程度。

一个图可以是强连通的，即任意两个节点之间都存在路径；也可以是弱连通的，即只有部分节点之间存在路径。

六、拓扑排序 (Topological Sorting)拓扑排序是对有向无环图进行排序的一种算法。

在一个有向图中，如果存在一条路径从节点 A 到节点 B，那么在排序结果中，节点 A 应该在节点 B 的前面。

拓扑排序可以用来解决任务调度、依赖关系等问题。

七、最短路径 (Shortest Path)最短路径是指在图中找到两个节点之间路径长度最短的路径。

最短路径算法可以用来解决如最优路径规划、网络路由等问题。

常见的最短路径算法包括迪杰斯特拉算法和弗洛伊德算法。

八、网络流 (Network Flow)网络流是指在图中沿着边进行的一种资源分配。

一、实训目的通过本次拓扑排序实训，掌握拓扑排序的基本原理和算法实现方法，能够运用拓扑排序解决实际问题，提高自己在数据结构和算法方面的应用能力。

二、实训内容1. 拓扑排序原理及算法拓扑排序是一种针对有向无环图（DAG）的排序方法，它将图中的顶点按照某种顺序排列，使得图中所有的有向边都满足方向要求。

具体来说，拓扑排序要求在有向边(u,v)中，顶点u必须在顶点v之前。

拓扑排序的基本思想是：从入度为0的顶点开始，将其加入拓扑序列，然后删除该顶点及其所有出边，更新其他顶点的入度。

重复这个过程，直到所有顶点都被加入拓扑序列。

2. 拓扑排序算法实现本次实训中，我们将学习两种拓扑排序算法实现：（1）基于邻接矩阵的拓扑排序首先，我们使用邻接矩阵表示有向图。

然后，遍历邻接矩阵，找出所有入度为0的顶点，将其加入拓扑序列。

接着，删除该顶点及其所有出边，更新其他顶点的入度。

重复这个过程，直到所有顶点都被加入拓扑序列。

（2）基于邻接表的拓扑排序邻接表是一种链式存储结构，它将图中所有顶点存储在一个链表中，每个顶点对应一个链表，链表中存储与该顶点相连的所有顶点。

基于邻接表的拓扑排序算法如下：（1）初始化拓扑序列为空，入度数组为顶点数大小的数组，所有元素的值设为0。

（2）遍历邻接表，找出所有入度为0的顶点，将其加入拓扑序列，并将入度数组中相应元素的值减1。

（3）删除拓扑序列中的顶点及其所有出边，更新入度数组。

（4）重复步骤（2）和（3），直到拓扑序列不为空。

三、实训过程1. 阅读拓扑排序相关资料，了解其原理和算法实现方法。

2. 使用C++编写基于邻接矩阵的拓扑排序程序，实现图数据的构建、拓扑排序和输出拓扑序列。

3. 使用C++编写基于邻接表的拓扑排序程序，实现图数据的构建、拓扑排序和输出拓扑序列。

4. 对比两种算法的优缺点，分析其在实际应用中的适用场景。

5. 运行程序，测试不同图数据的拓扑排序结果，验证程序的正确性。

四、实训总结1. 通过本次实训，我们掌握了拓扑排序的基本原理和算法实现方法，提高了自己在数据结构和算法方面的应用能力。