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

前言

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

在一个有向图为顶点表示活动的网中，我们称为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++拓扑排序内容请搜索以前的文章或继续浏览下面的相关文章希望大家以后多多支持！