拓扑排序步骤：

1.在有向图中选一个没有前驱的顶点且输出之。

2.从图中删除该顶点和所有以它为尾的弧。

思考：

1.采用图的十字链表存储结构，可以方便的查找结点的出度和入度。

2.拓扑排序不唯一。

实现：

 1 void TopoSort(OLGraph G)
 2 {
 3     int i = 0;
 4     int count = 0;
 5     SeqStack S;
 6     ArcNode* P = NULL;
 7     int indegree[MAXVEX] = { 0 };
 8 
 9     for (i = 0; i < G.vexnum; i++)//求各个顶点入度并存入indegree数组
10     {
11         P = G.vertex[i].head;
12         while (P)
13         {
14             indegree[i]++;
15             P = P->hnext;
16         }
17     }
18 
19     S.top = -1;//初始化栈
20     for (i = 0; i < G.vexnum; i++)
21     {
22         if (indegree[i] == 0)
23         {
24             PushStack(&S, i);
25         }
26     }
27 
28     while (S.top != -1)//非空栈
29     {
30         count++;
31         PopStack(&S, &i);
32         printf("%c", G.vertex[i].vexdata);
33         for (P = G.vertex[i].tail; P; P = P->tnext)//对所有弧尾为i的边，其弧头点入度减1
34         {
35             i = P->headvex;
36             indegree[i]--;
37             if (indegree[i] == 0)
38             {
39                 PushStack(&S, i);
40             }
41         }
42     }
43 
44     if (count < G.vexnum)
45     {
46         printf("该有向网有回路");
47     }
48 }

源代码：

  1 #define _CRT_SECURE_NO_WARNINGS
  2 #include <stdio.h>
  3 #include <stdlib.h>
  4 #define MAXVEX 20
  5 
  6 typedef struct ArcNode
  7 {
  8     int tailvex;
  9     int headvex;
 10     struct ArcNode* tnext;
 11     struct ArcNode* hnext;
 12 }ArcNode;
 13 
 14 typedef struct VexNode
 15 {
 16     char vexdata;
 17     ArcNode* tail;
 18     ArcNode* head;
 19 }VexNode;
 20 
 21 typedef struct
 22 {
 23     int vexnum;
 24     int arcnum;
 25     VexNode vertex[MAXVEX];
 26 }OLGraph;//Orthogonal List Graph
 27 
 28 typedef struct
 29 {
 30     int top;
 31     int elem[MAXVEX];
 32 }SeqStack;//定长顺序栈
 33 
 34 void PushStack(SeqStack* S, int elem)
 35 {
 36     if (S->top == MAXVEX - 1)
 37     {
 38         printf("栈满");
 39         exit(1);
 40     }
 41     else
 42     {
 43         S->top++;
 44         S->elem[S->top] = elem;
 45     }
 46 }
 47 
 48 void PopStack(SeqStack* S, int* elem)
 49 {
 50     if (S->top == -1)
 51     {
 52         printf("栈空");
 53         exit(1);
 54     }
 55     else
 56     {
 57         (*elem) = S->elem[S->top];
 58         S->top--;
 59     }
 60 }
 61 
 62 void TopoSort(OLGraph G)
 63 {
 64     int i = 0;
 65     int count = 0;
 66     SeqStack S;
 67     ArcNode* P = NULL;
 68     int indegree[MAXVEX] = { 0 };
 69 
 70     for (i = 0; i < G.vexnum; i++)//求各个顶点入度并存入indegree数组
 71     {
 72         P = G.vertex[i].head;
 73         while (P)
 74         {
 75             indegree[i]++;
 76             P = P->hnext;
 77         }
 78     }
 79 
 80     S.top = -1;//初始化栈
 81     for (i = 0; i < G.vexnum; i++)
 82     {
 83         if (indegree[i] == 0)
 84         {
 85             PushStack(&S, i);
 86         }
 87     }
 88 
 89     while (S.top != -1)//非空栈
 90     {
 91         count++;
 92         PopStack(&S, &i);
 93         printf("%c", G.vertex[i].vexdata);
 94         for (P = G.vertex[i].tail; P; P = P->tnext)//对所有弧尾为i的边，其弧头点入度减1
 95         {
 96             i = P->headvex;
 97             indegree[i]--;
 98             if (indegree[i] == 0)
 99             {
100                 PushStack(&S, i);
101             }
102         }
103     }
104 
105     if (count < G.vexnum)
106     {
107         printf("该有向网有回路");
108     }
109 }
110 
111 
112 //返回顶点vex在十字链表G中的位置
113 int LocateVex(OLGraph G, char vex)
114 {
115     int i = 0;
116     for (i = 0; i < G.vexnum; i++)
117     {
118         if (G.vertex[i].vexdata == vex)
119         {
120             return i;
121         }
122     }
123     return -1;
124 }
125 
126 void Create(OLGraph* G)
127 {
128     int i = 0, j = 0, k = 0;
129     char tail = '\0';
130     char head = '\0';
131     ArcNode* P = NULL;
132     ArcNode* Pre = NULL;
133 
134     printf("请输入顶点数和边数(逗号分隔)：");
135     scanf("%d%*c%d", &G->vexnum, &G->arcnum);
136 
137     for (i = 0; i < G->vexnum; i++)
138     {
139         printf("请输入第%d个顶点：", i + 1);
140         scanf(" %c", &G->vertex[i].vexdata);//%c前有一空格用于吸收空白字符
141         G->vertex[i].tail = NULL;
142         G->vertex[i].head = NULL;
143     }
144 
145     for (k = 0; k < G->arcnum; k++)
146     {
147         printf("请输入第%d条边的两端点(逗号分隔)：", k + 1);
148         scanf(" %c%*c%c", &tail, &head);
149         i = LocateVex(*G, tail);
150         j = LocateVex(*G, head);
151         
152         P = (ArcNode*)calloc(1, sizeof(ArcNode));
153         P->tailvex = i;
154         P->headvex = j;
155 
156         if (G->vertex[i].tail == NULL)//链接到相同弧尾域
157         {
158             G->vertex[i].tail = P;
159         }
160         else
161         {
162             Pre = G->vertex[i].tail;
163             while (Pre->tnext)
164             {
165                 Pre = Pre->tnext;
166             }
167             Pre->tnext = P;
168         }
169 
170         if (G->vertex[j].head == NULL)//链接到相同弧头域
171         {
172             G->vertex[j].head = P;
173         }
174         else
175         {
176             Pre = G->vertex[j].head;
177             while (Pre->hnext)
178             {
179                 Pre = Pre->hnext;
180             }
181             Pre->hnext = P;
182         }
183     }
184 }
185 
186 int main(void)
187 {
188     OLGraph G;
189     Create(&G);
190     TopoSort(G);
191     system("pause");
192     return 0;
193 }