C/C++浅析邻接表拓扑排序算法的实现

目录
  • 前言
  • 一、拓扑排序算法的思路
  • 二、实现步骤
    • 1.求个顶点的入度
    • 2.拓扑排序的实现
  • 三、测试结果
  • 总结

前言

在软件开发、施工过程、教学安排等等的一系列活动中，往往需要一个有向无环图来表示其是否成成功进行下去。

在一个有向图为顶点表示活动的网中，我们称为AOV网（Activity On Vertex Network）。设G={V,E}是一个具有n个顶点的有向图，V中的顶点序列v1,v2,…,vn,满足若从顶点vi到vj有一条路径，则在顶点序列中顶点vi必在vj之前。则我们称这样的顶点为一个拓扑序列。

所谓拓扑排序，其实就是对一个有向图构造拓扑序列的过程。如果所有的顶点被输出，则说明有向图中不存在回路，反之则是有回路。

一、拓扑排序算法的思路

拓扑排序往往用在有向邻接表中，这里也就只用有向邻接表来实现。

先找出所有节点的入度。

再在AOV网中选择一个入度为0的顶点输出，然后删除此顶点，将其连接的节点的入度减一直至输出所有顶点或者AOV网中不存在入度为0的顶点为止。

二、实现步骤

1.求个顶点的入度

设置一个indegree数组来存放各个顶点的入度。

int* indegree = (int*)malloc(sizeof(int) * G.vexnum);
//对单个节点p求入度
void CountIndegree(AdjList g, int* indegree, ArcNode* p) {
	while (p != NULL) {
		indegree[p->adjvex]++;
		p = p->nextarc;
	}
	return;
}

2.拓扑排序的实现

这里对栈的使用还是调用stl中的stack，比较方便。

bool TopoSort(AdjList g, int* indegree) {
	//先清空申请的indegree数组，或者也可以在初始化时采用calloc，就不用在这里置为0了
	for (int i = 0; i < g.vexnum; i++) {
		indegree[i] = 0;
	}
	//遍历边表中的每一个顶点，用CountIndegree()遍历单个节点
	for (int i = 0; i < g.vexnum; i++) {
		ArcNode* p = g.vertexlist[i].firstarc;
		CountIndegree(g, indegree, p);
	}
	stack<int>S;
	//如果该顶点的入度为0，则入栈。
	for (int i = 0; i < g.vexnum; i++) {
		if (indegree[i] == 0) {
			S.push(i);
		}
	}
	//count用来表示已经输出的节点个数
	//如果所有的顶点被输出，则count==g.vexnum，无回路，反之count<g.vexnum,则是有回路。
	int count = 0;
	while (!S.empty()) {
		int top = S.top();
		printf("%c ", g.vertexlist[top].data);
		S.pop();
		count++;
		ArcNode* p = g.vertexlist[top].firstarc;
		for (p; p != NULL; p = p->nextarc) {
			int i = p->adjvex;
			if (--indegree[i] == 0) {
				S.push(i);
			}
		}
	}
	if (count == g.vexnum) {
		return true;
	}
	return false;
}

三、测试结果

自己花了一个看起来挺复杂的图，一下也看不出来有没有环

首先算一算入度，顺带打印一下。

接下来是拓扑排序的结果

完美！

总结

每个顶点进栈一次出战一次，度减一的操作执行了e次，所以整个算法的时间复杂度为O(n+e)。

到此这篇关于C/C++浅析邻接表拓扑排序算法的实现的文章就介绍到这了,更多相关C++拓扑排序内容请搜索我们以前的文章或继续浏览下面的相关文章希望大家以后多多支持我们！

赞 (0)

相关推荐

  • C++实现有向图邻接表的构建

    本文实例为大家分享了C++实现有向图邻接表的构建代码,供大家参考,具体内容如下 数据结构里面的一道基础题,分享下自己的写法,验证可跑. #include<iostream> #include<string> const int MAX = 20; using namespace std; struct ArcNode { //弧结点 int adjvex = -1; //所指顶点位置 ArcNode *nextarc = nullptr; //下一条狐指针 size_t info

  • C++实现图的邻接表存储和广度优先遍历实例分析

    C++实现图的邻接表存储和广度优先遍历实例分析

    本文实例讲述了C++实现图的邻接表存储和广度优先遍历方法.分享给大家供大家参考.具体如下: 示例:建立如图所示的无向图 由上图知,该图有5个顶点,分别为a,b,c,d,e,有6条边. 示例输入(按照这个格式输入): 5 6 abcde 0 1 0 2 0 3 2 3 2 4 1 4 输入结束(此行不必输入) 注:0 1表示该图的第0个顶点和第1个定点有边相连,如上图中的a->b所示       0 2表示该图的第0个顶点和第2个定点有边相连,如上图中的a->c所示       2 3表示该图的

  • C++详细讲解图的拓扑排序

    目录 一.前言 二.算法流程 三.有向图的拓扑排序 一.前言 且该序列必须满足下面两个条件: 每个顶点出现且只出现一次. 若存在一条从顶点 x到顶点 y的路径,那么在序列中顶点 x 出现在顶点 y的前面. 拓扑排序只适用于 AOV网 (有向无环图) 若图中有环,则一定不存在拓扑序. 可以证明,一个有向无环图,一定存在一个拓扑序列.有向无环图,又被称为拓扑图. 入度: 即有多少条边指向自己这个节点. 出度: 即有多少条边从自己这个节点指出去. 二.算法流程 算法流程: 用队列来执行 ,初始化所有入

  • C++实现邻接表顶点的删除

    本文实例为大家分享了C++实现邻接表顶点的删除代码,供大家参考,具体内容如下 这里的边是无向边 删除顶点v时,要找到顶点v的邻接顶点w,把w中指向v的边删除掉,再删除边(v,w).循环这个过程,直到把和顶点v有关的边都删除掉为止. 再接着需要删除顶点v. 不可以直接像数组那样直接把顶点v之后的顶点位置像前移动一位,因为这样其他顶点的位置将会发生变化,顶点边中的顶点位置将会出错. 边和顶点的定义如下: struct Edge{//边节点的定义 int dest;//边的另一顶点位置 E cost;

  • 详解C++实现拓扑排序算法

    详解C++实现拓扑排序算法

    一.拓扑排序的介绍 拓扑排序对应施工的流程图具有特别重要的作用,它可以决定哪些子工程必须要先执行,哪些子工程要在某些工程执行后才可以执行.为了形象地反映出整个工程中各个子工程(活动)之间的先后关系,可用一个有向图来表示,图中的顶点代表活动(子工程),图中的有向边代表活动的先后关系,即有向边的起点的活动是终点活动的前序活动,只有当起点活动完成之后,其终点活动才能进行.通常,我们把这种顶点表示活动.边表示活动间先后关系的有向图称做顶点活动网(Activity On Vertex network),简

  • C++实现有向图的邻接表表示

    本文实例为大家分享了C++有向图的邻接表表示,供大家参考,具体内容如下 一.思路: 有向图的插入有向边.删除边.删除顶点和无向图的有区别.其他的和无向图的类似. 1.插入有向边<e1, e2> 只需要插入<e1, e2>边就行,不需要插入对称边<e2, e1> 2.删除边<e1,e2>: 只需要删除<e1, e2>边就行,不需要仔找对称边<e2, e1>进行删除. 3.删除顶点v: 首先,要在邻接表中删除以v为头的边<v, w&

  • C++数据结构之实现邻接表

    本文实例为大家分享了C++数据结构之实现邻接表的具体代码,供大家参考,具体内容如下 一.图的邻接表实现 1.实现了以顶点顺序表.边链表为存储结构的邻接表: 2.实现了图的创建(有向/无向/图/网).边的增删操作.深度优先递归/非递归遍历.广度优先遍历的算法: 3.采用顶点对象列表.边(弧)对象列表的方式,对图的创建进行初始化:引用 "ObjArrayList.h"头文件,头文件可参看之前博文"数据结构之顺序列表(支持对象元素)"代码: 4.深度优先遍历分别采用递归/

  • C++实现拓扑排序（AOV网络）

    本文实例为大家分享了C++实现拓扑排序的具体代码,供大家参考,具体内容如下 一.思路 先扫描所有顶点,把入度为0的顶点(如C,E)进栈.然后,取栈顶元素,退栈,输出取得的栈顶元素v(即入度为0的顶点v).接着,把顶点v的邻接顶点w的入度减1,如果w的入度变为0,则进栈.接着,取顶点w的兄弟结点(即取顶点v的邻接顶点w的下一邻接顶点),做同样的操作.重复上面步骤,直到输出n个顶点. 如上图: (1)扫描所有顶点,把入度为0的顶点进栈:将顶点C,E进栈: (2)取栈顶元素,退栈,输出取得的栈顶元素E

  • C/C++浅析邻接表拓扑排序算法的实现

    C/C++浅析邻接表拓扑排序算法的实现

    目录 前言 一.拓扑排序算法的思路 二.实现步骤 1.求个顶点的入度 2.拓扑排序的实现 三.测试结果 总结 前言 在软件开发.施工过程.教学安排等等的一系列活动中,往往需要一个有向无环图来表示其是否成成功进行下去. 在一个有向图为顶点表示活动的网中,我们称为AOV网(Activity On Vertex Network).设G={V,E}是一个具有n个顶点的有向图,V中的顶点序列v1,v2,…,vn,满足若从顶点vi到vj有一条路径,则在顶点序列中顶点vi必在vj之前.则我们称这样的顶点为一个

  • Java十大经典排序算法的实现图解

    Java十大经典排序算法的实现图解

    目录 前言 一.排序算法 1.排序算法概述(百度百科) 2.<数据结构与算法>中的排序算法 3.算法分析 二.十大经典排序算法(Java开发版) 1.冒泡排序 2.快速排序 3.基数排序 4.插入排序 5.选择排序 6.希尔排序 7.归并排序 8.计数排序 9.堆排序 10.桶排序 前言 本文章主要是讲解我个人在学习Java开发环境的排序算法时做的一些准备,以及个人的心得体会,汇集成本篇文章,作为自己对排序算法理解的总结与笔记. 内容主要是关于十大经典排序算法的简介.原理.动静态图解和源码实现

  • java几种排序算法的实现及简单分析

    本文实例讲述了java几种排序算法的实现及简单分析.分享给大家供大家参考.具体如下: package test; public class first { /*普通的插入排序*/ public void insertSort(int[] list) { int i, j; list[0] = -999; //相当于设置一个监视哨兵,不用判断是否越界, //但要求数组从第二个数开始即i=1开始存储 for (i = 1; i < list.length; i++) { j = i; while (

  • python常用排序算法的实现代码

    这篇文章主要介绍了python常用排序算法的实现代码,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,需要的朋友可以参考下 排序是计算机语言需要实现的基本算法之一,有序的数据结构会带来效率上的极大提升. 1.插入排序 插入排序默认当前被插入的序列是有序的,新元素插入到应该插入的位置,使得新序列仍然有序. def insertion_sort(old_list): n=len(old_list) k=0 for i in range(1,n): temp=old_lis

  • php计数排序算法的实现代码(附四个实例代码)

    计数排序只适合使用在键的变化不大于元素总数的情况下.它通常用作另一种排序算法(基数排序)的子程序,这样可以有效地处理更大的键. 总之,计数排序是一种稳定的线性时间排序算法.计数排序使用一个额外的数组C ,其中第i个元素是待排序数组 A中值等于 i的元素的个数.然后根据数组C 来将A中的元素排到正确的位置. 通常计数排序算法的实现步骤思路是: 1.找出待排序的数组中最大和最小的元素: 2.统计数组中每个值为i的元素出现的次数,存入数组C的第i项: 3.对所有的计数累加(从C中的第一个元素开始,每一

  • 详解Python排序算法的实现(冒泡,选择,插入,快速)

    详解Python排序算法的实现(冒泡,选择,插入,快速)

    目录 1. 前言 2. 冒泡排序算法 2.1 摆擂台法 2.2 相邻两个数字相比较 3. 选择排序算法 4. 插入排序 5. 快速排序 6. 总结 1. 前言 所谓排序,就是把一个数据群体按个体数据的特征按从大到小或从小到大的顺序存放. 排序在应用开发中很常见,如对商品按价格.人气.购买数量……显示. 初学编程者,刚开始接触的第一个稍微有点难理解的算法应该是排序算法中的冒泡算法. 我初学时,“脑思维”差点绕在 2 个循环结构的世界里出不来了.当时,老师要求我们死记冒泡的口诀,虽然有点搞笑,但是当

  • C++深入浅出讲解希尔排序算法的实现

    C++深入浅出讲解希尔排序算法的实现

    目录 希尔排序 1.基本思想 预排序 2.算法实现 3.时间复杂度 插入排序分为两种:直接插入排序&希尔排序 希尔排序 1.基本思想 希尔排序是在直接插入排序基础上的优化,属于非常牛掰的一个排序. 核心思想: 先进行预排序,让数组接近有序: 直接插入排序 预排序 预排序步骤: 分组排,假设gap==3,间隔为gap的为一组,然后分别使用插入排序的思想对这gap组数据进行排序 多组间隔为gap的预排序,gap由大变小,gap越大,大的数可以越快的到后面,小的数可以越快得到前面,gap越大,预排完越

  • python选择排序算法的实现代码

    1.算法:对于一组关键字{K1,K2,-,Kn}, 首先从K1,K2,-,Kn中选择最小值,假如它是 Kz,则将Kz与 K1对换:然后从K2,K3,- ,Kn中选择最小值 Kz,再将Kz与K2对换.如此进行选择和调换n-2趟,第(n-1)趟,从Kn-1.Kn中选择最小值 Kz将Kz与Kn-1对换,最后剩下的就是该序列中的最大值,一个由小到大的有序序列就这样形成. 2.python 选择排序代码: 复制代码 代码如下: def selection_sort(list2):    for i in

  • 7种排序算法的实现示例

    复制代码 代码如下: #include <stdio.h>#include <stdlib.h>#include <time.h> void BubbleSort1 (int n, int *array) /*little > big*/{ int i, j; for (i=0; i<n-1; i++) {  for (j=n-1; j>i; j--)  {   if (array[j] < array[j-1])   {    int temp

  • JS中多层次排序算法的实现代码

    JS中多层次排序算法的实现代码

    引子 排序在编程中随处可见,从开始学习变成,到项目开发,基本上或多或少会遇到一些排序问题,接下来我要写的是我在实际开发终于到的一个排序问题,一开始卡了我很久,后面随着知识积累,实践变多才解决掉了,不知道是不是我搜索关键字不对,还是其他原因,百度也没有找到这方面的内容. 数据结构和需求 var arr = [ { "soNumber" : "52085848", "item" : "313281", "amount&q

随机推荐