1. 回答以下有关拓扑排序的问题： （1）给出如图所示有向图的所有不同的拓扑序列。 （2）什么样的有向图的拓扑序列是唯一的？ 2. 已知有6 个顶点（顶点编号为0～5）的带权有向图G，其邻接矩阵数组A 为上三角矩阵，按行为主序（行优先）保存在如下的一维数组中： 要求： （1）写出图G的邻接矩阵数组A。 （2）画出带权有向图G。 （3）求图G的关键路径，并计算该关键路径的长度。（第3小问选做）

1.
（1）有以下拓扑序列：
0 1 2 3 4 5
0 1 3 2 4 5
0 2 1 3 4 5
0 2 3 1 4 5
0 3 1 2 4 5
0 3 2 1 4 5
（2）当且仅当有向图是DAG（有向无环图）时，拓扑序列才是唯一的。

2.
（1）邻接矩阵数组A如下：
0 2 1 3 1 3 // 第0行
0 0 4 1 3 2 // 第1行
0 0 0 1 2 1 // 第2行
0 0 0 0 4 3 // 第3行
0 0 0 0 0 2 // 第4行
0 0 0 0 0 0 // 第5行
（2）带权有向图G如下：

    2      1
0 ----> 1 ----> 2
|       |  4  / |
v 3     v   v   v 1
3 ----> 2 ----> 3
|       |  2    |
v 1     v   v   v 4
4 ----> 3 ----> 4
|       |  3    |
v 2     v   v   v 3
5 ----> 4 ----> 5

（3）求图G的关键路径：
首先，计算出每个顶点的最早开始时间et和最晚开始时间lt。其中，et表示从源点到该点的最长路径的长度，lt表示从汇点到该点的最长路径的长度。具体计算方法如下：
- et[0] = 0
- 对于其他顶点i，计算其前驱顶点j的et值，然后et[i] = max(et[j]+a[j][i])，其中a[j][i]表示从顶点j到i的边的权重。
- lt[n-1] = et[n-1]
- 对于其他顶点i，计算其后继顶点j的lt值，然后lt[i] = min(lt[j]-a[i][j])，其中a[i][j]表示从顶点i到j的边的权重。

计算出et和lt后，可以计算每条边的最早开始时间e和最晚开始时间l，以及该边是否为关键路径，具体计算方法如下：
- 对于每条边(i,j)，计算e = et[i]+a[i][j]和l = lt[j]-a[i][j]。
- 如果e = l，则该边为关键路径。

根据上述方法可以得到图G的关键路径为0 -> 1 -> 2 -> 3 -> 4 -> 5，长度为11。