数据结构之图论算法（四） |
您所在的位置：网站首页 › 拓扑数据结构分为 › 数据结构之图论算法（四） |
数据结构之图论算法（四）
|
一、有向无环图（DAG图）：无环的有向图
应用示例1： 描述含公共子式的表达式的工具——实现对相同子式的共享，从而节省存储空间；
应用示例2： 描述工程项目或系统过程的工具工程可分为若干个成为活动的子工程；子工程间存在一定约束，如某些子工程的开始必须在另一些子工程完成之后主要关心的问题1.工程是否能顺利进行；2.整个工程完成所必须的最短时间。 二、AOV网和拓扑排序 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）直至全部顶点都已输出，或者当前图中不存在无前驱的顶点为止，或一种情况说明图中存在环。 不存在环时： 存在环时： 当有向图中无环时，可利用深度优先遍历进行拓扑排序，即顶点退出DFS函数的先后次序的逆序 拓扑排序的算法思想：【数组表示法】： 找到全为0的第j列，输出j；将第j行的全部元素置为0； ··· 反复执行1、2直至所有元素输出完毕。
时间复杂度：O（n³）
由上述的数组表示法可知，只要创建一个数组来表示每个结点的入度为多少即可。 若某一个点入度为0，那么就可以输出该点，同时将该点相连的各个点的入度-1，然后再在该数组中寻找下一个入度为0的点。 整理一下思路：（对于邻接矩阵）
所以拓扑序列为：1，3，2，6，5，4，7 算法实现：（前期准备部分，包括图的定义和栈的定义以及相关调用函数） #include #include #include #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 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 nextarc){ int k = p->adjvex; //把与vertices[i]连接的所有结点的下标信息放到k中 if(!(--indegree[k])) Push(S,k); //若点vertices[k]的入度在-1之后为0，那么入栈。 } } if(count |
最后还会留下边！！
【本文地址】