莞城区仿做网站/seo网页优化工具

拓扑排序是一个无环图的应用，如一个“电影制作”的工程图，不可能在人员到位进驻场地时，导演还没有找到，也不可能在拍摄过程中，场地都没有，因此，这样的工程图，一定是无环的有向图。
在一个表示工程的有向图中，用顶点表示活动，用弧表示活动之间的优先关系，这样的有向图为顶点表示活动的网，称为AOV网。
设G={V,E}是一个具有n个顶点的有向图，V中的顶点序列v1,v2,……,vn,满足若从顶点vi到vj有一条路径，则在顶点序列中顶点vi必在顶点vj之前。这样的顶点序列为一个拓扑序列。
所谓拓扑排序，即为对一个有向图构造拓扑序列的过程。构造时有两个结果，如果此网的所有顶点都被输出，则说明它是不存在环的AOV网；如果输出顶点少了，哪怕只少一个，也说明这个网存在环，不是AOV网。

拓扑排序算法

对AOV网进行拓扑排序的基本思路：从AOV网中选择一个入度为零的顶点输出，然后删除该顶点，并删除以此顶点为尾的弧，继续重复此步骤，直到输出所有顶点或AOV网中不存在入度为0的顶点为止。
所用的数据结构：存储图的邻接表（便于删除顶点）<增加一个入度域in>，栈（存储入度为0的顶点）。
涉及结构的代码：

#include <iostream>
#include <stack> //拓扑排序需要用到 数据结构~栈 
using namespace std;
const int MAXVEX = 105;
struct EdgeNode{int adjvex;EdgeNode *next;int weight;
};
typedef struct VertexNode{int in;//入度，以空间换取时间int data;EdgeNode *FirstEdge; 
}VertexNode,AdjList[MAXVEX];
typedef struct{AdjList adjList;int numVertexes,numEdges;
}graphAdjList,*GraphAdjList;

拓扑排序代码：

//拓扑排序TopologicalSort
bool TopologicalSort(GraphAdjList GL){//由于typedef,GraphAdjList类型是指针 int cnt=0;//用于计数，若输出则自增。若最后cnt的值小于总顶点数，则说明该图存在回路 EdgeNode *e;stack<int> s;for(int i=0;i<GL->numVertexes;i++){if(GL->adjList[i].in==0){s.push(i);}}while(!s.empty()){int tmp = s.top();s.pop();cnt++;cout<<GL->adjList[tmp].data;//打印当前顶点信息for(e = GL->adjList[tmp].FirstEdge;e!=NULL;e=e->next){if(--GL->adjList[e->adjvex].in==0){s.push(e->adjvex);}} }if(cnt<GL->numVertexes){return false;}return true;
}