数据结构之图论算法(四)—— 拓扑算法
一、有向无环图(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函数的先后次序的逆序
拓扑排序的算法思想:
【数组表示法】:
- 找到全为0的第j列,输出j;
- 将第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;
}
结合代码在分析整个过程:
ThReE_73: 表述太不严谨了,一个ip数据报才四字节,你一个首部就20字节了,6!
燃烧的心: 那个标识为啥是12345啊
ctotalk: 加油,不错。
不吃西红柿丶: 非常有用,谢谢大佬整理~