问题
问答题
已知有6个顶点（顶点编号为0～5）的有向带权图G，其邻接矩阵A为上三角矩阵，按行为主序（行优先）保存在如下的一维数组中。
要求：
（1）写出图G的邻接矩阵A。
（2）画出有向带权图G。
（3）求图G的关键路径，并计算该关键路径的长度。
答案
参考答案：（1）由题可以画出待定上三角矩阵的结构图如下（图中“？”待定元素）
可以看出，第一行至第五行主对角线上方的元素分别5、4、3、2、1个，由此可以画出压缩存储数组中的元素所属行的情况，如下图所示：
将个元素填入各行即得邻接矩阵：
（2）根据第一步所得矩阵A容易作出有向带权图G，如下：
（3）下图中粗线箭头所标识的4个活动组成G的关键路径：
由上图容易求得图的关键路径长度为；4+5+4+3=16。