拓撲排序代碼C語言

1、/* 用鄰接表表示圖的拓撲排序算法 */#include#include#define MAXVEX 100#define TRUE 1#define FALSE 0typedef struct EdgeNode EdgeNode;typedef struct EdgeNode * PEdgeNode;typedef struct EdgeNode * EdgeList;struct EdgeNodeint endvex; /* 相鄰頂點字段 */ PEdgeNode nextedge; /* 鏈字段 */; /* 邊表中的結(jié)點 */typedef struct/*VexType vertex

2、;*/ EdgeList edgelist; VexNode;typedef structint n;/*/*/* 頂點信息 */ 邊表頭指針 */ 頂點表中的結(jié)點 */*VexNode vexsMAXVEX;圖的頂點個數(shù) */ GraphList;typedef struct/* 頂點在頂點表中的下標值 */int vexsnoMAXVEX;/*VexType vexsMAXVEX;*/ /* 頂點信息 */ Topo;/* 求出圖中所有頂點的入度 */ /* 方法是搜索整個鄰接表 */ void findInDegree(GraphList* g, int *inDegree) int i

3、; 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

4、 n; i+)if (indegreei = 0) /* 將入度為零的頂點入棧 */ indegreei = top;top = i;while (top != -1) /* 棧不為空 */j = top;top = indegreetop;/* 取出當前棧頂元素 */ptopo-vexsnonodeno+ = j;p = paov-vexsj.edgelist;/* 取該元素邊表中的第一個邊結(jié)點 */while (p) /* 刪除以該頂點為起點的邊 */ k = p-endvex;indegreek-;if (indegreek = 0) /* 將新的入度為零的邊入棧 */ indegree

5、k = top; top = k;p = p-nextedge;if (nodeno n) /* AOV 網(wǎng)中存在回路 */ 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.edg

6、elist;if (pp = NULL)p-vexsa.edgelist = temp;elsewhile (pp-nextedge != NULL)pp = pp-nextedge; pp-nextedge = temp;/* 實例鄰接表的構(gòu)造 */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 (topoSor