拓扑排序 代码 C语言.doc

精品文档/* 用邻接表表示图的拓扑排序算法*/#include#include#define MAXVEX 100#define TRUE 1#define FALSE 0typedef struct EdgeNode EdgeNode;typedef struct EdgeNode * PEdgeNode;typedef struct EdgeNode * EdgeList;struct EdgeNode int endvex;/* 相邻顶点字段 */ PEdgeNode nextedge;/* 链字段 */;/* 边表中的结点 */typedef struct /*VexType vertex;*/* 顶点信息 */ EdgeList edgelist;/* 边表头指针 */ VexNode;/* 顶点表中的结点 */typedef struct int n;/* 图的顶点个数 */ VexNode vexsMAXVEX; GraphList;typedef struct int vexsnoMAXVEX;/* 顶点在顶点表中的下标值 */ /*VexType vexsMAXVEX;*/* 顶点信息 */ Topo;/* 求出图中所有顶点的入度 */* 方法是搜索整个邻接表 */void findInDegree(GraphList* g, int *inDegree) int i; PEdgeNode p; for (i = 0; i n; i+) inDegreei = 0; for (i = 0; i n; i+) p = g-vexsi.edgelist; while (p) +inDegreep-endvex; p = p-nextedge; int topoSort(GraphList * paov, Topo * ptopo) EdgeList p; int i, j,k, nodeno = 0, top = -1; int indegreeMAXVEX; findInDegree(paov, indegree); /* 求出图中所有顶点的入度 */ for (i = 0; i n; i+) if (indegreei = 0) /* 将入度为零的顶点入栈 */ indegreei = top;top = i; while (top != -1) /* 栈不为空 */ j = top; top = indegreetop; /* 取出当前栈顶元素 */ ptopo-vexsnonodeno+ = j; p = paov-vexsj.edgelist; /* 取该元素边表中的第一个边结点 */while (p) /* 删除以该顶点为起点的边 */k = p-endvex; indegreek-;if (indegreek = 0) /* 将新的入度为零的边入栈 */indegreek = top;top = k; p = p-nextedge; if (nodeno n) /* AOV网中存在回路 */ printf(The aov network has a cyclen); return FALSE; return TRUE;/* 边的插入算法*/void insert(GraphList* p,int a,int b) EdgeList pp; PEdgeNode temp; temp = (PEdgeNode)malloc(sizeof(EdgeNode); temp-endvex = b; temp-nextedge = NULL; pp = p-vexsa.edgelist; if (pp = NULL) p-vexsa.edgelist = temp; else while (pp-nextedge != NULL) pp = pp-nextedge; pp-nextedge = temp; /* 实例邻接表的构造 */GraphList * makeList() GraphList* p; int i; p = (GraphList*)malloc(sizeof(GraphList); p-n = 9; for (i = 0; i n; i+) p-vexsi.edgelist = NULL; insert(p, 0, 2); insert(p, 0, 7); insert(p, 1, 2); insert(p, 1, 3); insert(p, 1, 4); insert(p, 2, 3); insert(p, 3, 5); insert(p, 3, 6); insert(p, 4, 5); insert(p, 7, 8); insert(p, 8, 6); return p;void main() GraphList *p;Topo topo; int i; p = makeList(); if (topoSort(p, &topo) = TRUE)printf(邻接表表示图的拓扑排序结果如下：n); for