拓扑排序(二)

作者：追风剑情发布于：2014-11-16 14:50 分类：Algorithms

拓扑排序是有向图的一种重要运算。设G=(V,E)是一个具有n个顶点的有向图，在图中顶点表示活动，用边表示活动间的优先关系，则这个有向图称为用顶点表示活动的网(Activity On Vertex Network)，简称为AOV网。在AOV网中，如果从顶点Vi到顶点Vj有一条有向路径，则Vi是Vj的前驱，Vj是Vi的后继；如果<Vi,Vj>是AOV网中的一条边，则Vi是Vj的直接前驱，Vj是Vi的直接后继。

对于一个AOV网，构造其所有顶点的线性序列，建立顶点之间的先后关系，而且使原来没有先后关系的顶点之间也建立起人为的先后关系，这样的线性序列称为拓扑有序序列。构造AOV网的拓扑有序序列的运算称为拓扑排序。

工发工具 Visual Studio 2010

工发语言 C++

StructInfo.h文件

#define MAXV 7 //最大顶点数

//顶点
typedef struct vertex
{
	int adjvex;		/*顶点编号*/
} Vertex;

//边
typedef struct edgenode
{
	int adjvex; //顶点序号
	int value;  //边的权值
	struct edgenode *next; //下一条边的顶点
} ArcNode;

//表头结点类型
typedef struct
{
	Vertex data; //顶点信息
	int count;   //存放顶点入度
	ArcNode *firstarc; //指向第一条边
} VNode;

MainApp.cpp文件

#include <stdlib.h>
#include <stdio.h>
#include <string.h>
#include "StructInfo.h"


/**
 * 拓扑排序
 * 任何无环路的有向图，其所有顶点都可以排在一个拓扑有序序列中。
 * 一个AOV网的拓扑有序序列并不是唯一的。
 * 排序方法:
 * (1)从有向图中选择一个没有前驱(即入度为0)的顶点并且输出它。
 * (2)从网中删去该顶点，并且删去从该顶点发出的全部有向边。
 * (3)重复上述两步，直到剩余的网中不再存在没有前驱的顶点为止。
 */
void TopSort(VNode adj[], int n){
	int i,j;
	int St[MAXV], top=-1;//栈St的指针为top
	ArcNode *p;
	for (i=0; i<n; i++){
		//入度为0的顶点入栈
		if (adj[i].count == 0){
			top++;
			St[top] = i;
		}

		//栈不为空时循环
		while(top > -1){
			i = St[top]; top--;//出栈
			printf("%d ", i);//输出顶点
			p = adj[i].firstarc;//找第1个相邻顶点
			while (p != NULL){
				j = p->adjvex;
				adj[j].count--;
				//入度为0的相邻顶点入栈
				if(adj[j].count == 0){
					top++;
					St[top] = j;
				}
				p=p->next;//找下一个相邻顶点
			}
		}
	}
}

void main()
{

}

标签: Algorithms