【大话数据结构C语言】49 拓扑排序
【摘要】
欢迎关注我的公众号是【CodeAllen】，关注回复【1024】获取精品学习资源 程序员技术交流①群：736386324 ，程序员技术交流②群：371394777
拓扑排序概念
一个无环的有向图称为无环图（Directed Acyclic Graph），简称DAG图
...
欢迎关注我的公众号是【CodeAllen】，关注回复【1024】获取精品学习资源
程序员技术交流①群：736386324 ，程序员技术交流②群：371394777
拓扑排序概念
一个无环的有向图称为无环图（Directed Acyclic Graph），简称DAG图
工程或者某种流程都可以分为若干个小的工程或者阶段，我们称这些小的工程或阶段为“活动”
在一个表示工程的有向图中，用顶点表示活动，用弧表示活动之间的优先关系，这样的有向图为顶点表示活动的网，我们称之为AOV网（Active On Vertex Network）
拓扑排序
AOV网中的弧表示活动之间存在的某种制约关系， AOV网不能存在回路
-
拓扑序列：设G=(V,E)是一个具有n个顶点的有向图，V中的顶点序列V1,V2,……,Vn满足若从顶点Vi到Vj有一条路径，则在顶点序列中顶点Vi必在顶点Vj之前。则我们称这样的顶点序列为一个拓扑序列。
-
拓扑排序：所谓的拓扑排序，其实就是对一个有向图构造拓扑序列的过程。
-
为了说清楚刚才几个概念，我们不妨从另外一个例子出发：
对AOV网进行拓扑排序的方法和步骤如下：
从AOV网中选择一个没有前趋的顶点（该顶点的入度为0）并且输出它；
从网中删去该顶点，并且删去从该顶点发出的全部有向边；
重复上述两步，直到剩余网中不再存在没有前趋的顶点为止。
由刚才我们那幅AOV网图，我们可以用邻接表（因为需要删除顶点，所以我们选择邻接表会更加方便）数据结构表示：
编程实践
算法时间复杂度：
对一个具有n个顶点，e条边的网来说，初始建立入度为零的顶点栈，要检查所有顶点一次，执行时间为O(n)。
排序中，若AOV网无回路，则每个顶点入、出栈各一次，每个表结点被检查一次，因而执行时间是 O(n+e)。
所以，整个算法的时间复杂度是 O(n+e)。
TopologicalSort.c
// 边表结点声明
typedef struct EdgeNode
{
int adjvex;
struct EdgeNode *next;
}EdgeNode;
// 顶点表结点声明
typedef struct VertexNode
{
int in; // 顶点入度
int data;
EdgeNode *firstedge;
}VertexNode, AdjList[MAXVEX];
typedef struct
{
AdjList adjList;
int numVertexes, numEdges;
}graphAdjList, *GraphAdjList;
// 拓扑排序算法
// 若GL无回路，则输出拓扑排序序列并返回OK，否则返回ERROR
Status TopologicalSort(GraphAdjList GL)
{
EdgeNode *e;
int i, k, gettop;
int top = 0; // 用于栈指针下标索引
int count = 0; // 用于统计输出顶点的个数
int *stack; // 用于存储入度为0的顶点
stack = (int *)malloc(GL->numVertexes * sizeof(int));
for( i=0; i < GL->numVertexes; i++ )
{
if( 0 == GL->adjList[i].in )
{
stack[++top] = i; // 将度为0的顶点下标入栈
}
}
while( 0 != top )
{
gettop = stack[top--]; // 出栈
printf("%d -> ", GL->adjList[gettop].data);
count++;
for( e=GL->adjList[gettop].firstedge; e; e=e->next )
{
k = e->adjvex;
// 注意：下边这个if条件是分析整个程序的要点！
// 将k号顶点邻接点的入度-1，因为他的前驱已经消除
// 接着判断-1后入度是否为0，如果为0则也入栈
if( !(--GL->adjList[k].in) )
{
stack[++top] = k;
}
}
}
if( count < GL->numVertexes ) // 如果count小于顶点数，说明存在环
{
return ERROR;
}
else
{
return OK;
}
}
文章来源: allen5g.blog.csdn.net，作者：CodeAllen的博客，版权归原作者所有，如需转载，请联系作者。
原文链接：allen5g.blog.csdn.net/article/details/116854826
【版权声明】本文为华为云社区用户转载文章，如果您发现本社区中有涉嫌抄袭的内容，欢迎发送邮件进行举报，并提供相关证据，一经查实，本社区将立刻删除涉嫌侵权内容，举报邮箱：
cloudbbs@huaweicloud.com
- 点赞
- 收藏
- 关注作者
评论（0）