C++实现图的拓扑排序

拓扑排序DFS实现拓扑排序，必须是有向⽆环图。

在任⼀有向⽆环图中，必然存在出度为0的顶点。

否则，每个顶点都⾄少有⼀条出边，这意味着包含环路。

在对有向⽆环图的DFS搜索中，⾸先因访问完成⽽转换⾄VISITED状态的顶点m，其出度必然为0。

基于上述两条特性，我们可以得出结论：DFS搜索过程中各顶点被标记为VISITED的次序，恰好（按逆序）给出了原图的⼀个拓扑排序。

代码：#include <iostream>#include <string>#include <cstdlib>#include <sstream>#include <cstring>#include <cstdio>#include <algorithm>#include <map>#include <math.h>#include <stack>using namespace std;stack<int> s; ///⽤来保存逆序int graph[100][100]; ///邻接矩阵存储，节点从0开始int visited[100];int n; ///节点个数int e; ///⽤来存边的条数void dfs(int v){visited[v] = 1;for(int i=0;i<n;i++){if(graph[v][i]==1&&visited[i]==0){dfs(i);if(visited[i]==1)s.push(i);}}}void solve(){///初始化scanf("%d",&n);scanf("%d",&e);for(int i=0;i<e;i++){int v1,v2;scanf("%d%d",&v1,&v2);graph[v1][v2]=1;}///dfs过程for(int i=0;i<n;i++){if(visited[i]==0){dfs(i);if(visited[i]==1)s.push(i);}}///输出⼊while(!s.empty()){printf("%d ",s.top());s.pop();}}int main() {solve();return0;}。

拓扑排序的原理及其实现取材自以下材料：/wiki/Topological_sorting/wiki/Hamiltonian_path定义和前置条件：定义：将有向图中的顶点以线性方式进行排序。

即对于任何连接自顶点u到顶点v的有向边uv，在最后的排序结果中，顶点u总是在顶点v的前面。

如果这个概念还略显抽象的话，那么不妨考虑一个非常非常经典的例子——选课。

我想任何看过数据结构相关书籍的同学都知道它吧。

假设我非常想学习一门“机器学习”的课程，但是在修这么课程之前，我们必须要学习一些基础课程，比如：计算机科学概论，C语言程序设计，数据结构，算法等等。

那么这个制定选修课程顺序的过程，实际上就是一个拓扑排序的过程，每门课程相当于有向图中的一个顶点，而连接顶点之间的有向边就是课程学习的先后关系。

只不过这个过程不是那么复杂，从而很自然的在我们的大脑中完成了。

将这个过程以算法的形式描述出来的结果，就是拓扑排序。

那么是不是所有的有向图都能够被拓扑排序呢？显然不是。

继续考虑上面的例子，如果告诉你在选修“计算机科学概论”这门课之前需要你先学习“机器学习”，你是不是会被弄糊涂？在这种情况下，就无法进行拓扑排序，因为它中间存在互相依赖的关系，从而无法确定谁先谁后。

在有向图中，这种情况被描述为存在环路。

因此，一个有向图能被拓扑排序的充要条件就是它是一个有向无环图(DAG：Directed Acyclic Graph)。

偏序/全序关系：偏序和全序实际上是离散数学中的概念。

这里不打算说太多形式化的定义，形式化的定义教科书上或者上面给的链接中就说的很详细。

还是以上面选课的例子来描述这两个概念。

假设我们在学习完了算法这门课后，可以选修“机器学习”或者“计算机图形学”。

这个“或者”表示，学习“机器学习”和“计算机图形学”这两门课之间没有特定的先后顺序。

因此，在我们所有可以选择的课程中，任意两门课程之间的关系要么是确定的(即拥有先后关系)，要么是不确定的(即没有先后关系)，绝对不存在互相矛盾的关系(即环路)。

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

例如，任务调度。

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

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

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

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

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

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

【洛⾕⽇报#157】快速⼊⼿拓扑排序⽬录1. 前⾔2. 基本思路3. 模拟思路4.代码实现5. 例题6. 参考⽂献与鸣谢1.前⾔在正式讲拓扑排序之前，我们来引⼊⼀下，以便各位更好理解。

（所有有向图出品于Xmind）⾸先，你想学习计算机的原理怎么办？（⽩⼿起家）肯定有很多前置知识啊！流程图就像下⾯：很明显，此时你需要按⼀定顺序（这个顺序叫 “拓扑序列”）学习才能彻底了解计算机原理。

那么这个顺序怎么求呢？拓扑排序帮你忙！前置知识：图的基本概念以及建图编程能⼒。

2.基本思路 & 实现⾸先，对于点的关系，⼤致分为2种关系：1. 先后关系，如上图的 “数学” 与 “物理学” 的关系。

2. 并列关系（应该叫做“没有关系”），如上图的 ”物理学“ 和 “计算机发展史” 的关系。

不难发现，因为有了并列关系，拓扑序列不⼀定是唯⼀的。

如上图，可以得到很多个拓扑序列，这⾥只举⼀个例⼦，其他的相信⼤家都会看。

上图的⼀个拓扑序列：12345678那么⼤家不难发现，拓扑排序的时候，⼤家总会找⼊度为0的点，因为这是你不⽤学习的点，可以直接解锁。

找到了之后，你就可以把这个点放到序列⾥，那么随之就有新的点的⼊度为0，然后重复上述知道图空。

以上就是拓扑排序的基本思路！我们可以简述为：1. 从图中，选择⼀个⼊度为0的点，并输出该顶点；2. 从图中，删除该顶点，以及相关联的边；3. 重复上述步骤，知道输出所有点。

（原来如此简单！）下⾯带⼤家模拟⼀遍拓扑排序的过程（⼤家觉得烦可以跳过）。

3. 模拟思路⾸先，可以轻易发现，只有点1是⼊度为0，因此，把它输出，删除点1和边A、B。

如下图：糟了，有4个点的⼊度为0怎么办？不着急，由于拓扑序列不⽌⼀个的原因，怎样都⾏，我就按照从⼩到⼤来。

但是为了加快进度，我们直接删掉4个点，并从⼩到⼤⼊拓扑序列，同时删除H、C、E、F、D、G六条边！现在就很明了啦，把点6、7和相关的边删掉，⼊队，再把点8删掉就完⼯！最终拓扑序列：12345678关键来了，怎么⽤代码实现呢？（其实也不考码⼒(>_<)啦）4. 代码实现拓扑排序⼀般有三种实现⽅法（建图是必不可少的）：1. 算法设置⼀个队列（⽅便使⽤优先队列，从⼩到⼤输出）,将所有⼊度为0的顶点⼊队。

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

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

按照惯例，先上代码，注释超详细：#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. 任务调度：在一个任务依赖关系图中，拓扑排序可以确定任务的执行顺序，保证所有任务按照依赖关系正确执行。

拓扑排序与判断有向图是否有回路拓扑排序与判断有向图是否有环⽅式1：基于BFS：采⽤⼊度的⽅式判断是否有回路定义队列Q，将所有⼊度为0的结点加⼊队列取出队列的⾸节点，输出，然后删去从它出发的所有边，并令边的另⼀端结点的⼊度减1，如果减到了0，就将其加⼊队列重复上⾯⼀个操作，直到队列为空。

队列为空时，如果⼊过队列的结点数为N，则拓扑排序成功，图为有向⽆环图；否则图中有环//create on 20210216//拓扑排序；判断图中是否有环//基于判断结点⼊度//邻接表存储；模板#include<iostream>#include<vector>#include<queue>#define maxn 501using namespace std;vector<int> edge[maxn]; //存储每个结点的下⼀个结点（有向图），忽略权重queue<int> q; //保存⼊度为0的结点int indegree[maxn]; //存储每个结点的⼊度int main(){int n,m; //n为结点个数；m为边的个数cin>>n>>m;for(int i=0;i<m;i++){int a,b;cin>>a>>b;edge[a].push_back(b);indegree[b]++;}int cnt = 0;for(int i=1;i<=n;i++){if(indegree[i]==0){q.push(i); //所有⼊度为0的结点进⼊队列cnt++; //统计每个如果队列的结点个数}}while(!q.empty()){int node = q.front();q.pop();for(int i=0;i<edge[node].size();i++){indegree[ edge[node][i] ]--;if(indegree[ edge[node][i] ]==0){q.push(edge[node][i]);cnt++;}}}if(cnt == n) cout<<"NO LOOP"<<endl;else cout<<"LOOP EXISTS"<<endl;return0;}⽅式⼆：基于DFS⼀、基于dfs的拓扑排序（不能处理有环的情况）代码实现：（20191205）/*状态0是还没有被访问状态 1是此次dfs结束，也就是说是最⼩元，后⾯没有结点了，才能被标记为1，然后⼊栈*/#include<iostream>#include<stack>#define inf 9999999using namespace std;int book[101],sum,n,e[101][101];stack<int> s;void dfs (int cur){for(int i=1;i<=n;i++)if(e[cur][i]==1&&book[i]==0)dfs(i);book[cur] = 1;//与DFS的区别在于标记当前节点的时间（在递归结束才加⼊）s.push(cur);return;}int main(){int i,j,m,a,b;cin>>n>>m;for(i=1;i<=n;i++){for(j=1;j<=n;j++){if(i==j) e[i][j]=0;else e[i][j]=inf;}}for(i=1;i<=m;i++){cin>>a>>b;e[a][b]=1;}dfs(2);while(!s.empty()){cout<<s.top()<<"";s.pop();}return0;}View Code测试数据：//左图99242521133638585789//右图781213243426254557View Code⼆、判断有向图是否有环（基于dfs拓扑排序）算法描述：每个结点有三个状态：状态0是还没有被访问；状态-1是在这次dfs过程中被标记；状态 1是此次dfs结束，也就是说是最⼩元（后⾯没有结点了）才能被标记为1；如果与在此次dfs过程中已访问过的结点（状态为-1）有边相连，说明有环（回路）；如果与在此次dfs过程中未访问的结点（状态为0）有边相连，则继续dfs；此次dfs结束后（到最⼩元的结点），将最⼩元的状态标记为1，并且return true（因为此次dfs过程中未出现环）代码实现：（20200129）/*状态0是还没有被访问状态-1是在这次dfs过程中被标记状态 1是此次dfs结束，也就是说是最⼩元，后⾯没有结点了，才能被标记为1*/#include<iostream>#define inf 999999using namespace std;int book[110];int e[110][110];int n;bool dfs (int cur){book[cur] = -1;for(int i=1;i<=n;i++){if(e[cur][i]!=0&&e[cur][i]!=inf&&book[i]==-1)return false;//如果与在此次dfs过程中已访问过的结点（状态为-1）有边相连，说明有环if(e[cur][i]!=0&&e[cur][i]!=inf&&book[i]==0&&!dfs(i))return false;// 如果与在此次dfs过程中未访问的结点（状态为0）有边相连，则继续dfs}book[cur] = 1;//与DFS的区别在于标记当前节点的时间（在递归结束才加⼊）return true;}int main(){cin>>n;for(int i=1;i<=n;i++){for(int j=1;j<=n;j++){if(i==j) e[i][j] = 0;else e[i][j] = inf;}}int m;cin>>m;int a,b,c;for(int i=0;i<m;i++){cin>>a>>b>>c;e[a][b] = c; // directed}bool state = dfs(1);if(state) cout<<"none";else cout<<"exist";return0;}View Code测试数据：//none左图77121131271343453576672//exist右图77211131721343453576672View Code三、基于dfs的拓扑排序（可处理有回路的情况）代码实现：（20191205）/*状态0是还没有被访问状态-1是在这次dfs过程中被标记状态 1是此次dfs结束，也就是说是最⼩元，后⾯没有结点了，才能被标记为1，然后⼊栈*/#include<stdio.h>#include<iostream>#include<stack>#define inf 9999999using namespace std;int book[101],sum,n,e[101][101];stack<int> s;bool dfs (int cur){book[cur] = -1;for(int i=1;i<=n;i++){if(e[cur][i]==1&&book[i]==-1) return false;//如果在这个dfs过程中边相连，说明有环if(e[cur][i]==1&&book[i]==0&&!dfs(i)) return false;}book[cur] = 1;//与DFS的区别在于标记当前节点的时间（在递归结束才加⼊）s.push(cur);return true;}int main(){int i,j,m,a,b;scanf("%d %d",&n,&m);for(i=1;i<=n;i++){for(j=1;j<=n;j++){if(i==j) e[i][j]=0;else e[i][j]=inf;}}for(i=1;i<=m;i++){scanf("%d %d",&a,&b);e[a][b]=1;}bool ans = dfs(2);if(ans == false) cout<<"Loop exists!"<<endl; else{while(!s.empty()){cout<<s.top()<<"";s.pop();}}return0;}View Code测试数据：91024252113363858578981View Code。

数据结构拓扑排序实验报告正文：一、实验目的本实验旨在通过实现拓扑排序算法来加深对数据结构中图的相关概念的理解，掌握拓扑排序的具体步骤与实现方法。

二、实验原理拓扑排序是一种对有向无环图进行排序的算法，它可以将有向无环图的顶点按照线性的顺序排列出来，使得对于任何一个有向边(u, v)，都有顶点 u 在排列中出现在顶点 v 之前。

拓扑排序常用于表示图中的依赖关系，如任务调度、编译顺序等场景。

三、实验步骤1. 构建有向图根据实际需求构建有向图，可以使用邻接表或邻接矩阵等数据结构来表示有向图。

2. 执行拓扑排序算法利用拓扑排序算法对构建的有向图进行排序，可选择使用深度优先搜索（DFS）或广度优先搜索（BFS）等算法实现。

3. 输出排序结果将排序后的顶点按照线性的顺序输出，得到拓扑排序的结果。

四、实验结果与分析1. 实验数据以图 G = (V, E) 的顶点集合 V 和边集合 E，构建了如下的有向图：V = {A, B, C, D, E, F}E = {(A, C), (B, C), (C, D), (D, E), (E, F)}2. 拓扑排序结果经过拓扑排序算法的处理，得到的拓扑排序结果如下： A, B, C, D, E, F3. 结果分析可以看出，根据有向图的依赖关系，拓扑排序算法能够将顶点按照合理的顺序进行排序。

拓扑排序的结果可以作为图中顶点的执行顺序，具有重要的应用价值。

五、实验总结通过本次实验，我们深入学习了拓扑排序算法，并成功实现了拓扑排序的过程。

拓扑排序在图论和数据结构中具有广泛的应用，对于理解和解决与图相关的问题具有重要意义。

六、附件本文档没有涉及附件内容。

七、法律名词及注释本文档没有涉及法律名词及注释。

数据结构与算法课程设计报告课程设计题目：图的算法实现专业班级：信息与计算科学1002班目录摘要 (1)1、引言 (1)2、需求分析 (1)3、概要设计 (2)4、详细设计 (4)5、程序设计 (10)6、运行结果 (18)7、总结体会 (19)摘要(题目): 图的算法实现实验内容图的算法实现问题描述：（1）将图的信息建立文件；（2）从文件读入图的信息，建立邻接矩阵和邻接表；（3）实现Prim、Kruskal、Dijkstra和拓扑排序算法。

关键字:邻接矩阵、Dijkstra和拓扑排序算法1.引言本次数据结构课程设计共完成图的存储结构的建立、Prim、Kruskal、Dijkstra 和拓扑排序算法等问题。

通过本次课程设计，可以巩固和加深对数据结构的理解，通过上机和程序调试，加深对课本知识的理解和熟练实践操作。

（1）通过本课程的学习，能够熟练掌握数据结构中图的几种基本操作；（2）能针对给定题目，选择相应的数据结构，分析并设计算法，进而给出问题的正确求解过程并编写代码实现。

使用语言：CPrim算法思想：从连通网N={V,E}中的某一顶点v0出发，选择与它关联的具有最小权值的边(v0,v)，将其顶点加入到生成树的顶点集合V中。

以后每一步从一个顶点在V中，而另一个顶点不在V中的各条边中选择权值最小的边(u,v),把它的顶点加入到集合V中。

如此继续下去，直到网中的所有顶点都加入到生成树顶点集合V中为止。

拓扑排序算法思想：1、从有向图中选取一个没有前驱的顶点，并输出之；2、从有向图中删去此顶点以及所有以它为尾的弧；重复上述两步，直至图空，或者图不空但找不到无前驱的顶点为止。

没有前驱-- 入度为零，删除顶点及以它为尾的弧-- 弧头顶点的入度减1。

2.需求分析1、通过键盘输入建立一个新的有向带权图，建立相应的文件；2、对建立的有向带权图进行处理，要求具有如下功能：（1）用邻接矩阵和邻接表的存储结构输出该有向带权图，并生成相应的输出结果；（2）用Prim、Kruskal算法实现对图的最小生成树的求解，并输出相应的输出结果；（3）用Dijkstra算法实现对图中从某个源点到其余各顶点的最短路径的求解，并输出相应的输出结果；（4）实现该图的拓扑排序算法。

详解C++实现拓扑排序算法⽬录⼀、拓扑排序的介绍⼆、拓扑排序的实现步骤三、拓扑排序⽰例⼿动实现四、拓扑排序的代码实现五、完整的代码和输出展⽰⼀、拓扑排序的介绍拓扑排序对应施⼯的流程图具有特别重要的作⽤，它可以决定哪些⼦⼯程必须要先执⾏，哪些⼦⼯程要在某些⼯程执⾏后才可以执⾏。

为了形象地反映出整个⼯程中各个⼦⼯程(活动)之间的先后关系，可⽤⼀个有向图来表⽰，图中的顶点代表活动(⼦⼯程)，图中的有向边代表活动的先后关系，即有向边的起点的活动是终点活动的前序活动，只有当起点活动完成之后，其终点活动才能进⾏。

通常，我们把这种顶点表⽰活动、边表⽰活动间先后关系的有向图称做顶点活动⽹(Activity On Vertex network)，简称AOV⽹。

⼀个AOV⽹应该是⼀个有向⽆环图，即不应该带有回路，因为若带有回路，则回路上的所有活动都⽆法进⾏（对于数据流来说就是死循环）。

在AOV⽹中，若不存在回路，则所有活动可排列成⼀个线性序列，使得每个活动的所有前驱活动都排在该活动的前⾯，我们把此序列叫做拓扑序列(Topological order)，由AOV⽹构造拓扑序列的过程叫做拓扑排序(Topological sort)。

AOV⽹的拓扑序列不是唯⼀的，满⾜上述定义的任⼀线性序列都称作它的拓扑序列。

⼆、拓扑排序的实现步骤1.在有向图中选⼀个没有前驱的顶点并且输出2.从图中删除该顶点和所有以它为尾的弧（⽩话就是：删除所有和它有关的边）3.重复上述两步，直⾄所有顶点输出，或者当前图中不存在⽆前驱的顶点为⽌，后者代表我们的有向图是有环的，因此，也可以通过拓扑排序来判断⼀个图是否有环。

三、拓扑排序⽰例⼿动实现如果我们有如下的⼀个有向⽆环图，我们需要对这个图的顶点进⾏拓扑排序，过程如下：⾸先，我们发现V6和v1是没有前驱的，所以我们就随机选去⼀个输出，我们先输出V6，删除和V6有关的边，得到如下图结果：然后，我们继续寻找没有前驱的顶点，发现V1没有前驱，所以输出V1，删除和V1有关的边，得到下图的结果：然后，我们⼜发现V4和V3都是没有前驱的，那么我们就随机选取⼀个顶点输出（具体看你实现的算法和图存储结构），我们输出V4，得到如下图结果：然后，我们输出没有前驱的顶点V3，得到如下结果：然后，我们分别输出V5和V2，最后全部顶点输出完成，该图的⼀个拓扑序列为：v6–>v1—->v4—>v3—>v5—>v2四、拓扑排序的代码实现下⾯，我们将⽤两种⽅法来实现我么的拓扑排序：1.Kahn算法2.基于DFS的拓扑排序算法⾸先我们先介绍第⼀个算法的思路：Kahn的算法的思路其实就是我们之前那个⼿动展⽰的拓扑排序的实现，我们先使⽤⼀个栈保存⼊度为0 的顶点，然后输出栈顶元素并且将和栈顶元素有关的边删除，减少和栈顶元素有关的顶点的⼊度数量并且把⼊度减少到0的顶点也⼊栈。

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

二、实训内容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. 通过本次实训，我们掌握了拓扑排序的基本原理和算法实现方法，提高了自己在数据结构和算法方面的应用能力。

图的遍历数据结构实验报告正文：1·引言本实验报告旨在介绍图的遍历数据结构实验的设计、实现和结果分析。

图是一种常见的数据结构，用于表示对象之间的关系。

图的遍历是指系统地访问图的每个节点或边的过程，以便获取所需的信息。

在本次实验中，我们将学习并实现图的遍历算法，并分析算法的效率和性能。

2·实验目标本实验的主要目标是实现以下几种图的遍历算法：●深度优先搜索（DFS）●广度优先搜索（BFS）●拓扑排序3·实验环境本实验使用以下环境进行开发和测试：●操作系统：Windows 10●编程语言：C++●开发工具：Visual Studio 20194·实验设计与实现4·1 图的表示我们采用邻接矩阵的方式来表示图。

邻接矩阵是一个二维数组，用于表示图中节点之间的关系。

具体实现时，我们定义了一个图类，其中包含了节点个数、边的个数和邻接矩阵等属性和方法。

4·2 深度优先搜索算法（DFS）深度优先搜索是一种经典的图遍历算法，它通过递归或栈的方式实现。

DFS的核心思想是从起始节点开始，尽可能深地访问节点，直到达到最深的节点或无法继续访问为止。

我们实现了一个递归版本的DFS算法，具体步骤如下：●从起始节点开始进行递归遍历，标记当前节点为已访问。

●访问当前节点的所有未访问过的邻接节点，对每个邻接节点递归调用DFS函数。

4·3 广度优先搜索算法（BFS）广度优先搜索是另一种常用的图遍历算法，它通过队列的方式实现。

BFS的核心思想是从起始节点开始，逐层地遍历节点，先访问离起始节点最近的节点。

我们实现了一个使用队列的BFS算法，具体步骤如下：●将起始节点放入队列，并标记为已访问。

●从队列中取出一个节点，访问该节点并将其所有未访问的邻接节点放入队列。

●重复上述步骤，直到队列为空。

4·4 拓扑排序算法拓扑排序是一种将有向无环图（DAG）的所有节点线性排序的算法。

c语言经典算法解析C语言作为一种广泛使用的编程语言，拥有许多经典算法，这些算法不仅在解决实际问题上非常高效，而且对于理解计算机科学的基本原理也至关重要。

本文将介绍一些C语言中常见的经典算法，并解析其实现原理。

1. 排序算法：排序是计算机科学中最基本的问题之一，C语言提供了多种排序算法的实现，例如冒泡排序、选择排序、插入排序、快速排序等。

这些算法以不同的方式对元素进行比较和交换，最终将数据按照一定的顺序排列。

2. 查找算法：查找算法用于在给定数据集中寻找特定的值。

C语言中常见的查找算法包括线性查找、二分查找、哈希查找等。

这些算法的实现原理各不相同，但都能在不同的数据规模下高效地找到目标值。

3. 图算法：图是由节点和边组成的一种数据结构，图算法用于解决与图相关的问题，例如最短路径查找、拓扑排序、最小生成树等。

C语言中可以使用邻接矩阵或邻接表等数据结构来表示图，并通过深度优先搜索或广度优先搜索等算法来进行相应的操作。

4. 字符串匹配算法：字符串匹配算法用于在一个长字符串中查找某个子串出现的位置。

常见的算法包括朴素字符串匹配算法、KMP算法、Boyer-Moore算法等。

这些算法通过不同的方式在给定的字符串中寻找匹配，从而提高查找的效率。

5. 动态规划算法：动态规划算法用于解决有重叠子问题和最优子结构特征的问题。

C语言中常用的动态规划算法有背包问题、最长公共子序列问题、最短路径问题等。

这些算法通过将大问题分解为小问题，并使用查表或记忆化搜索等技术来避免重复计算，从而提高算法的效率。

以上仅是C语言中一些经典算法的简要介绍和解析。

随着计算机科学的不断发展，还有许多其他算法可以探索和应用。

掌握这些经典算法的原理和实现有助于提高编程技能，同时也能够帮助理解计算机科学的核心概念。

通过不断学习和实践，我们可以在编程中灵活运用这些算法，解决实际问题。

数据结构拓扑排序实验报告数据结构拓扑排序实验报告一、引言本实验旨在通过实现拓扑排序算法，对给定的有向图进行排序操作。

拓扑排序是一种对有向图进行排序的算法，根据有向边的方向，将图中的节点排列成线性序列，并满足任意一条边的起点在序列中位于终点之前的要求。

二、实验目的1.理解拓扑排序的概念及原理；2.掌握拓扑排序的具体实现方法；3.实现拓扑排序算法，并对给定的有向图进行排序实验。

三、理论知识1.有向图：由一组顶点和一组有向边组成的图结构，每条有向边连接两个顶点，有方向性。

2.有向边：连接有向图中两个顶点的边，表明了两个顶点之间的关系，有起点和终点之分。

3.入度：指向某一顶点的有向边的数量。

4.拓扑排序：一种对有向图进行排序的算法，要求在排序结果中，任意一条边的起点在序列中位于终点之前。

四、实验步骤1.创建图的数据结构，包括顶点和有向边的表示；2.读入有向图的顶点和边的信息，并构建图的结构；3.计算每个顶点的入度，并初始化拓扑排序结果序列；4.选择一个入度为0的顶点，将其加入拓扑排序结果序列，并将其所连接的顶点的入度减1；5.重复步骤4，直到所有顶点被加入拓扑排序结果序列；6.输出最终的拓扑排序结果。

五、实验结果- 给定的有向图：- 图片附件1：有向图示意图- 通过拓扑排序算法得到的排序结果：- 顶点A →顶点B →顶点C →顶点D →顶点E六、实验分析与总结在本次实验中，我们成功实现了拓扑排序算法，并对给定的有向图进行了排序。

通过实验结果可以看出，拓扑排序可以将有向图中的节点按照依赖关系进行排序。

通过拓扑排序，我们可以找到一个满足依赖关系的节点序列，用于解决诸如任务调度、依赖关系分析等问题。

七、附件- 图片附件1：有向图示意图八、法律名词及注释1.有向图：在图论中，有向图是由一组顶点和一组有向边组成的图结构，每条边连接两个顶点，并有方向性。

2.拓扑排序：一种对有向图进行排序的算法，要求在排序结果中，任意一条边的起点在序列中位于终点之前。

c语言必做100题1. 编写一个C程序，输出“Hello, World!”。

2. 编写一个C程序，计算并输出1到100的和。

3. 编写一个C程序，判断一个数是否为素数。

4. 编写一个C程序，将一个字符串反转。

5. 编写一个C程序，实现二分查找算法。

6. 编写一个C程序，实现插入排序算法。

7. 编写一个C程序，实现选择排序算法。

8. 编写一个C程序，实现冒泡排序算法。

9. 编写一个C程序，实现快速排序算法。

10. 编写一个C程序，实现希尔排序算法。

11. 编写一个C程序，将一个二维数组转置。

12. 编写一个C程序，计算一个数的阶乘。

13. 编写一个C程序，实现斐波那契数列。

14. 编写一个C程序，计算两个数的最大公约数。

15. 编写一个C程序，计算两个数的最小公倍数。

16. 编写一个C程序，计算一个数的平方根。

17. 编写一个C程序，计算一个数的立方根。

18. 编写一个C程序，实现矩阵乘法运算。

19. 编写一个C程序，实现字符串的查找和替换。

20. 编写一个C程序，实现栈的基本操作（入栈、出栈、查看栈顶元素）。

21. 编写一个C程序，实现队列的基本操作（入队、出队、查看队首元素）。

22. 编写一个C程序，实现链表的基本操作（插入、删除、倒置）。

23. 编写一个C程序，实现二叉树的前序、中序和后序遍历。

24. 编写一个C程序，实现图的深度优先搜索算法。

25. 编写一个C程序，实现图的广度优先搜索算法。

26. 编写一个C程序，实现最短路径算法（Dijkstra算法或Floyd算法）。

27. 编写一个C程序，实现最小生成树算法（Prim算法或Kruskal算法）。

28. 编写一个C程序，实现拓扑排序算法。

29. 编写一个C程序，实现优先队列。

30. 编写一个C程序，实现哈希表的基本操作（插入、查找、删除）。

31. 编写一个C程序，实现堆的基本操作（插入、删除、查找最大值）。

32. 编写一个C程序，实现最大堆排序算法。

什么是拓扑排序拓扑排序是对一个有向图构造拓扑序列的过程，使得该序列满足：每个顶点出现且只出现一次；若存在一条从顶点A到顶点B的路径，那么在序列中顶点A出现在顶点B的前面。

拓扑排序可以用来判断一个有向图是否为DAG （有向无环图）。

如果一个有向图可以被拓扑排序，那么这个有向图就是DAG。

拓扑排序的应用场景是什么？拓扑排序通常用来“排序”具有依赖关系的任务。

比如，如果用一个DAG图来表示一个工程，其中每个顶点表示工程中的一个任务，用有向边A→B表示在做任务B之前必须先完成任务A。

那么这个DAG图就是一个合法的任务安排，而且它的拓扑序列就是合法的任务执行顺序。

拓扑排序还可以用来检测一个有向图是否有环。

如果有环，则该有向图不可能拓扑排序，反之，可以拓扑排序。

另外，拓扑排序还可以用于解决一些实际问题，如编译器的依赖关系分析、工程项目的任务调度等。

拓扑排序时间复杂度对于有n个顶点和e条边的图来说，拓扑排序的时间复杂度为O(n+e)拓扑排序C++代码实现#include<bits/stdc++.h>using namespace std;const int N=100010;int n,m;int h[N],e[N],ne[N],idx;int d[N];void add(int a,int b){e[idx]=b,ne[idx]=h[a],h[a]=idx++;d[b]++;}void topsort(){queue<int>q;for(int i=1;i<=n;i++)if(!d[i])q.push(i);while(q.size()){int t=q.front();q.pop();cout<<t<<'';for(int i=h[t];~i;i=ne[i]){int j=e[i];if(--d[j]==0)q.push(j);}}}int main(){memset(h,-1,sizeof h);cin>>n>>m;while(m--){int a,b;cin>>a>>b;add(a,b);}topsort();return0;}拓扑排序Python代码实现from collections import dequedef topo_sort(graph):in_degree=dict((u,0)for u in graph) for u in graph:for v in graph[u]:in_degree[v]+=1q=deque()for u in in_degree:if in_degree[u]==0:q.appendleft(u)l=[]while q:u=q.pop()l.append(u)for v in graph[u]:in_degree[v]-=1if in_degree[v]==0:q.appendleft(v)return l。

C#实现图（Graph)简介图表示点之间的关系，在C#中通过节点对象的集合来表示点(Vertex)，用邻接矩阵(adjacency matrix)来表示点之间的关系。

下面来看C#实现。

PS:本片文章是我复习的笔记，代码注释很全。

勿吐槽。

表示点的对象下面实现代码: class Vertex{public string Data;public bool IsVisited;public Vertex(string Vertexdata){Data = Vertexdata;}}每个节点包含两个字段，分别为节点数据以及表示是否被访问过的一个布尔类型。

表示图的对象图中除了需要点的集合和邻接矩阵之外，还需要一些基本的向图中添加或删除元素的方法，以及一个构造方法来对图进行初始化。

public class Graph{//图中所能包含的点上限private const int Number = 10;//顶点数组private Vertex[] vertiexes;//邻接矩阵public int[,] adjmatrix;//统计当前图中有几个点int numVerts = 0;//初始化图public Graph(){//初始化邻接矩阵和顶点数组adjmatrix = new Int32[Number, Number];vertiexes = new Vertex[Number];//将代表邻接矩阵的表全初始化为0for (int i = 0; i &lt; Number; i++){for (int j = 0; j &lt; Number; j++){adjmatrix[i, j] = 0;}}}//向图中添加节点public void AddVertex(String v){vertiexes[numVerts] = new Vertex(v);numVerts++;}//向图中添加有向边public void AddEdge(int vertex1, int vertex2){adjmatrix[vertex1, vertex2] = 1;//adjmatrix[vertex2, vertex1] = 1;}//显示点public void DisplayVert(int vertexPosition){Console.WriteLine(vertiexes[vertexPosition]+" ");}}拓扑排序(TopSort)拓扑排序是对一个有向的，并且不是环路的图中所有的顶点线性化。