数据结构之图论算法(四)—— 拓扑算法

数据结构之图论算法(四)—— 拓扑算法一 有向无环图 DAG 图 无环的有向图 应用示例 1 描述含公共子式的表达式的工具 实现对相同子式的共享 从而节省存储空间 应用示例 2 描述工程项目或系统过程的工具 工程可分为若干个成为活动 的子工程 子工程间存在一定约束

大家好,我是讯享网,很高兴认识大家。

一、有向无环图(DAG图):无环的有向图

应用示例1:

  • 描述含公共子式的表达式的工具——实现对相同子式的共享,从而节省存储空间;
    在这里插入图片描述
    讯享网

应用示例2:

  • 描述工程项目或系统过程的工具
  • 工程可分为若干个成为活动的子工程;
  • 子工程间存在一定约束,如某些子工程的开始必须在另一些子工程完成之后
  • 主要关心的问题
  • 1.工程是否能顺利进行;
  • 2.整个工程完成所必须的最短时间。

二、AOV网和拓扑排序

AOV网:

结点为活动,弧的指向表示活动执行的次序
在这里插入图片描述

AOE网:

结点为事件,弧表示活动,权表示活动持续时间在这里插入图片描述

1. AOV网:

代表的一项工程中活动的集合,是个偏序集合

  • 偏序: 若集合X上的关系R是传递的、自反的、反对称的,则称R是集合X上的偏序关系
  • 全序:若关系R是集合X上的偏序关系,如果对于每个x,y∈X,必有x R y 或 y R x,则称R是集合X上的全序关系
2. 拓扑排序(Topological Sort):

由某个集合上的一个偏序得到该集合上的一个全序

AOV网表示流程:

  • 流程图——表示偏序的有向图:
  • 用 ai–>aj表示(ai,aj)∈R,i < j;
  • 为了表示方便,令ai为前驱,二aj为后继,表明两者之间的次序关系(领先/优先关系)
  • 用途:描述工程项目或系统进行的次序
用AOV网进行拓扑排序:
方法1:

(1)在有向图中选取一个没有前驱的顶点输出之;
(2)从图中山区该顶点和所有以它为尾的弧。
重复(1)、(2)直至全部顶点都已输出,或者当前图中不存在无前驱的顶点为止,或一种情况说明图中存在环。

  • 不存在环时:在这里插入图片描述
  • 存在环时:在这里插入图片描述
    最后还会留下边!!

方法2:

当有向图中无环时,可利用深度优先遍历进行拓扑排序,即顶点退出DFS函数的先后次序的逆序

拓扑排序的算法思想:

【数组表示法】:

  1. 找到全为0的第j列,输出j;
  2. 将第j行的全部元素置为0;
    ···
    反复执行1、2直至所有元素输出完毕。
    在这里插入图片描述
时间复杂度:O(n³)

由上述的数组表示法可知,只要创建一个数组来表示每个结点的入度为多少即可。

若某一个点入度为0,那么就可以输出该点,同时将该点相连的各个点的入度-1,然后再在该数组中寻找下一个入度为0的点。

整理一下思路:(对于邻接矩阵)

在这里插入图片描述
在这里插入图片描述

所以拓扑序列为:1,3,2,6,5,4,7

算法实现:(前期准备部分,包括图的定义和栈的定义以及相关调用函数)

#include <stdio.h> #include <string.h> #include <stdlib.h> #define MAX_VERTEX_NUM 20 typedef int InfoType //边的定义 typedef struct ArcNode{ 
    int adjvex; //表示该边指向的顶点的位置 InfoType *info; //和边相关的信息 struct ArcNode *nextarc; //指向下一条边 }ArcNode; //顶点的定义 typedef int VertexType; typedef struct VNode{ 
    VertexType data; //顶点信息 ArcNode *firstarc; //指向第一条依附该顶点的边的指针,所以指针类型应为边的类型 }VNode,AdjList[MAX_VERTEX_NUM]; //AdjList表示邻接表类型 //图的定义 typedef struct{ 
    AdjList vertices; //vertices是vertex的复数 int vexnum, arcnum; //图的当前顶点数和边数 }ALGraph; //栈的定义 typedef struct{ 
    int *base, *top; int stacksize; }Stack; typedef enum{ 
   ERROR, OK, TRUE, FALSE} Status; //初始化栈 Status InitStack(Stack &S, int vexnum){ 
    S.base = (int *)malloc((vexnum+1) * sizeof(int)); if(!S.base) exit(-1); S.top = S.base; S.stacksize = vexnum; return OK; } //进栈: Status Push(Stack &S, int elmt){ 
    if(S.top-S.base == S.stacksize) return ERROR; *S.top++ = elmt; return OK; } //入度数组的初始赋值 void findinDegree(ALGraph G,int indegree[]){ 
    int i; for(i = 0; i < G.vexnum; i++){ 
    ArcNode *p = G.vertices[i].firstarc; while(p){ 
    indegree[p->adjvex]++; p = p->nextarc; } } } //栈是否为空的判断 Status StackEmpty(Stack &S){ 
    if(S.base == S.top) return TRUE; else return FALSE; } //出栈 Status Pop(Stack &S, int &i){ 
    i = *--S.top; //先下移,然后把栈顶元素存到i中,即先出栈的顶点的地址 //注意,Stack中存放的是顶点表的下标信息,所有vertices[i]是表示一个顶点元素; } 

讯享网

拓扑排序:(正片部分)

讯享网Status Topological(ALGraph G){ 
    //创建栈和indegree数组并将它们初始化: int indegree[MAX_VERTEX_NUM] = { 
   0}; Stack S; int i; InitStack(S, G.vexnum); findinDegree(G,indegree); for(i = 0; i < G.vexnum; i++) if(!indegree[i]) Push(S, i); //如果indegree[i]为空,则进栈 int count = 0; while(!StackEmpty (S)){ 
    //若栈非空,假设由n个进栈,那么就出栈n个 Pop(S,i);count++; //栈顶元素(某一结点)出栈,并且该结点所对应的下标信息传递给i,因此该点为vertices[i] //将所有相关连接点的入度-1 for(ArcNode *p = G.vertices[i].firstarc; p; p = p->nextarc){ 
    int k = p->adjvex; //把与vertices[i]连接的所有结点的下标信息放到k中 if(!(--indegree[k])) Push(S,k); //若点vertices[k]的入度在-1之后为0,那么入栈。 } } if(count < G.vexnum) return ERROR; //如果入栈的结点少于图的结点数,那么图中含有环,返回ERROR else return OK; } 

结合代码在分析整个过程:
在这里插入图片描述

小讯
上一篇 2025-03-09 21:05
下一篇 2025-03-06 19:46

相关推荐

版权声明:本文内容由互联网用户自发贡献,该文观点仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容,请联系我们,一经查实,本站将立刻删除。
如需转载请保留出处:https://51itzy.com/kjqy/80329.html