图的应用——拓扑排序算法

推荐原创

Laccoliths 2022-09-20 09:02:36 博主文章分类：数据结构 ©著作权

文章标签 拓扑排序入栈有向图 文章分类 C/C++ 编程语言 yyds干货盘点 阅读数191

在一个表示工程的有向图中，用顶点表示活动，用弧表示活动之间的有限关系，这样的有向图为顶点表示活动的网，我们成为AOV网（Activity On Vertex Network）。AOV网中的弧表示活动之间存在的某种制约关系，且不能存在回路。

设G=(V,E)是一个具有n个顶点的有向图，V中的顶点序列，满足若从顶点到有一条路径，则在顶点序列中顶点必在顶点之前，则我们称这样的顶点序列为一个拓扑序列。

拓扑排序就是对一个有向图构造拓扑序列的过程。如果此网的全部顶点都被输出，则说明它是不存在环的AOV网。

拓扑排序算法

对AOV网进行拓扑排序的基本思路是：从AOV网中选择一个入度为0的顶点输出，然后删去此顶点，并删除以此顶点为尾的弧，继续重复此步骤，直到输出全部顶点或者AOV网中不存在入度为0的顶点为止。

拓扑排序算法需要增加一个入度域in，顶点表的数据结构如下：

图的应用——拓扑排序算法_有向图_06

对AOV网，可以得到邻接表数据结构如下：

拓扑排序算法的结构代码如下：

/* 邻接矩阵结构 */
typedef struct
{
int vexs[MAXVEX];
int arc[MAXVEX][MAXVEX];
int numVertexes, numEdges;
}MGraph;

/* 邻接表结构****************** */
typedef struct EdgeNode /* 边表结点 */
{
int adjvex; /* 邻接点域，存储该顶点对应的下标 */
int weight; /* 用于存储权值，对于非网图可以不需要 */
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;

在该算法中，我们用栈来存储处理过程中入度为0的顶点，目的是为了避免每次查找时都要去遍历顶点表找有没有入度为0的顶点，拓扑排序算法代码如下：

/* 拓扑排序，若GL无回路，则输出拓扑排序序列并返回1，若有回路返回0。 */
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) /* 将入度为0的顶点入栈 */
stack[++top]=i;
while(top!=0)
{
gettop=stack[top--];
printf("%d -> ",GL->adjList[gettop].data);
count++; /* 输出i号顶点，并计数 */
for(e = GL->adjList[gettop].firstedge; e; e = e->next)
{
k=e->adjvex;
if( !(--GL->adjList[k].in) ) /* 将i号顶点的邻接点的入度减1，如果减1后为0，则入栈 */
stack[++top]=k;
}
}
printf("\n");
if(count < GL->numVertexes)
return ERROR;
else
return OK;
}

第4-8行是变量的定义，其中stack是一个栈，用来存储整型的数字。
第9-11行，做循环判断，把入度为0的顶点下标都入栈，从邻接表克制，此时stack应该为{0,1,3}，即的顶点入度为0，如图所示。

第13-14行，while循环，当栈中有数据元素时，始终循环。第15-17行，出栈得到，并打印此顶点，然后count+1。第18-23行，循环其实就是对顶点对应的弧链表进行遍历，即下图中的灰色部分，找到连接的两个顶点和，并将它们的入度减少一位，此时和的in值都为1，它们的目的是为了将顶点上的弧删除。