这样说，可能理解起来比较抽象。下面通过简单的例子进行说明！

例如，一个项目包括A、B、C、D四个子部分来完成，并且A依赖于B和D，C依赖于D。现在要制定一个计划，写出A、B、C、D的执行顺序。这时，就可以利用到拓扑排序，它就是用来确定事物发生的顺序的。

在拓扑排序中，如果存在一条从顶点A到顶点B的路径，那么在排序结果中B出现在A的后面。

拓扑排序算法的基本步骤：

以上图为例，来对拓扑排序进行演示。

拓扑排序 - 图2

第1步：将B和C加入到排序结果中。

​ 顶点B和顶点C都是没有依赖顶点，因此将C和C加入到结果集T中。假设ABCDEFG按顺序存储，因此先访问B，再访问C。访问B之后，去掉边和，并将A和D加入到队列Q中。同样的，去掉边和，并将F和G加入到Q中。

​ (01) 将B加入到排序结果中，然后去掉边和；此时，由于A和D没有依赖顶点，因此并将A和D加入到队列Q中。

​ (02) 将C加入到排序结果中，然后去掉边和；此时，由于F有依赖顶点D，G有依赖顶点A，因此不对F和G进行处理。

第2步：将A,D依次加入到排序结果中。

​ 第1步访问之后，A,D都是没有依赖顶点的，根据存储顺序，先访问A，然后访问D。访问之后，删除顶点A和顶点D的出边。

因此访问顺序是：B -> C -> A -> D -> E -> F -> G

拓扑排序是对有向无向图的排序。下面以邻接表实现的有向图来对拓扑排序进行说明。

1. 基本定义

(01) ListDG是邻接表对应的结构体。 mVexs则是保存顶点信息的一维数组。

(02) VNode是邻接表顶点对应的结构体。 data是顶点所包含的数据，而firstEdge是该顶点所包含链表的表头指针。

(03) ENode是邻接表顶点所包含的链表的节点对应的结构体。 ivex是该节点所对应的顶点在vexs中的索引，而nextEdge是指向下一个节点的。

2. 拓扑排序

  2.  * 拓扑排序
  3.  *
  4.  * 返回值：
  5.  *     -1 -- 失败(由于内存不足等原因导致)
  6.  *      0 -- 成功排序，并输入结果
  7.  *      1 -- 失败(该有向图是有环的)
  8.  */
  9. public int topologicalSort() {
  10.     int index = 0;
  11.     int num = mVexs.size();
  12.     int[] ins;               // 入度数组
  13.     char[] tops;             // 拓扑排序结果数组，记录每个节点的排序后的序号。
  14.     Queue<Integer> queue;    // 辅组队列
  16.     ins   = new int[num];
  17.     tops  = new char[num];
  18.     queue = new LinkedList<Integer>();
  20.     for(int i = 0; i < num; i++) {
  22.         ENode node = mVexs.get(i).firstEdge;
  23.         while (node != null) {
  24.             ins[node.ivex]++;
  25.             node = node.nextEdge;
  26.         }
  27.     }
  29.     // 将所有入度为0的顶点入队列
  30.     for(int i = 0; i < num; i ++)
  31.         if(ins[i] == 0)
  32.             queue.offer(i);                 // 入队列
  34.     while (!queue.isEmpty()) {              // 队列非空
  35.         int j = queue.poll().intValue();    // 出队列。j是顶点的序号
  36.         tops[index++] = mVexs.get(j).data;  // 将该顶点添加到tops中，tops是排序结果
  37.         ENode node = mVexs.get(j).firstEdge;// 获取以该顶点为起点的出边队列
  39.         // 将与"node"关联的节点的入度减1；
  40.         // 若减1之后，该节点的入度为0；则将该节点添加到队列中。
  42.             ins[node.ivex]--;
  43.             // 若节点的入度为0，则将其"入队列"
  44.             if( ins[node.ivex] == 0)
  45.                 queue.offer(node.ivex);    // 入队列
  47.             node = node.nextEdge;
  48.         }
  49.     }
  51.     if(index != num) {
  52.         System.out.printf("Graph has a cycle\n");
  53.         return 1;
  54.     }
  56.     // 打印拓扑排序结果
  57.     System.out.printf("== TopSort: ");
  58.     for(int i = 0; i < num; i ++)
  59.         System.out.printf("%c ", tops[i]);
  60.     System.out.printf("\n");
  62. }

说明：

(01) queue的作用就是用来存储没有依赖顶点的顶点。它与前面所说的Q相对应。

(02) tops的作用就是用来存储排序结果。它与前面所说的T相对应。