先上一波图看看效果
image
DAG与AOV?
DAG(Directed Acyclic Grap)指的是“有向无环图”,通常也称为“流程图”。
当我们要完成一个工程的时候,我们可以先将大的工程分成几个独立的子工程,将子工程d当作“活动”,每个活动之间有先决条件的关系(时间上有着相互制约的关系),就是说活动的执行有一定的顺序。将“活动”看成顶点,以弧表示活动之间的优先关系,这样的图称为“AOV”网(Activity On Vertex NetWork)。
拓扑排序是什么,有什么用?
如果要执行活动A,必须执行活动B,执行B就要执行C,要执行C就要执行A,这样形成一个环的话,就陷入了死循环,那我们怎么知道到底有没有环呢?这时候就出现了拓扑排序,也就是说拓扑排序将检测AOV图中是否有环,求一个有向图拓扑排序序列的过程就是拓扑排序。
实现拓扑排序实例。
先来看看用到的结构体吧
#include <stdlib.h>
#include<stdio.h>
#define MAXVEX 20
#define NON -1
typedef char VexType;
typedef float AdjType;
/* 边表中的结点 */
typedef struct EdgeNode {
int endvex; // 相邻顶点字段 ,一条边的另一个顶点
AdjType weight; //边的权,非带权图可以省略
struct EdgeNode *nextedge; // 链字段 ,连接到下一条边
}*PEdgeNode, *EdgeList;
/*顶点中的信息*/
typedef struct {
VexType vertex; // 顶点信息
EdgeList edgelist; //后面所有的边和组成的边
} VexNode; // 顶点表中的结点
/*点的集合和边表中链接信息构成了图*/
typedef struct {
int n; // 图的顶点个数
VexNode vexs[MAXVEX];
} GraphList;
拓扑排序只需3步:
- 输出顶点入度为0的值
- 让这个点消失(删除点及由它发出的边)
- 重复执行1和2直到输出无连接边的顶点
当然执行这些之前,你得有个图啊(摊手),已经有图的童鞋请跳过这一步。(下面是插入方法的主要代码)
/*插入顶点及连接的信息*/
void insert(GraphList* p, int a, int b) {//a,b是将要连接的两个顶点
EdgeList pp;//链接边
//给顶点赋值
p->vexs[a].vertex = a;
//如果指向NON,则说明是最后一个节点
if (b == NON)
{
p->vexs[a].edgelist = NULL;
return;
}
PEdgeNode temp;//边的节点
temp = (PEdgeNode)malloc(sizeof(EdgeNode));
temp->endvex = b;
temp->nextedge = NULL;
pp = p->vexs[a].edgelist;//将连接边复制给pp
if (pp == NULL)//连接两个顶点
p->vexs[a].edgelist = temp;
else {//将新边连接到后边
while (pp->nextedge != NULL)
pp = pp->nextedge;
pp->nextedge = temp;
}
}
咳咳,现在开始拓扑排序了。
- 输出顶点入度为0的值
首先你得找到哪些点入度为0(统计入度)
/*统计入度*/
Indegree = (int *)malloc(GL->n * sizeof(int));//存储入度
for (i = 0; i<GL->n; i++)
Indegree[i] = 0;
for (i = 0; i < GL->n; i++)
{
EdgeList p = GL->vexs[i].edgelist;
while (p != NULL)
{
Indegree[p->endvex]++;
p = p->nextedge;
}
}//所有点的入度已经存储完毕
```
然后就把入度为0的顶点揪出来吧**(入度为0的揪出来放到stack里面)**
for (j = 0; j < GL->n; j++)//初始化stack栈
{
stack[j] = -1;
}
/*
*将入度为0的节点入栈
*/
for (i = 0; i < GL->n; i++)
{
if (Indegree[i] == 0)
{
stack[top] = i;
top++;
}
}
top--;//top在执行完之后多加了一个
终于可以输出入度为0的点了吧。
printf("%d ", GL->vexs[gettop].vertex);//输出顶点自身
只有一句话吗?
2. 让已经输出的顶点就消失吧。
//输出顶点信息以后减少相应链接点的入度,标志着这个点从此消失
Indegree[GL->vexs[gettop].edgelist->endvex]--;
e = GL->vexs[gettop].edgelist->nextedge;
while (e != NULL)
{
Indegree[e->endvex]--;
e = e->nextedge;
}
当看到这里的时候,就应该想如果最后一个顶点也这样输出的话,就会出现内存泄露了,所以当到最后一个顶点的时候,就特殊处理吧。
####然后通过循环就可以进行拓扑排序啦,别忘了用一个计数器来记录输出的个数,最后通过输出的个数来判断是否能进行拓扑排序。
网友评论