(2) 强连通分量相关问题

• 强连通分量数量：通过分析各顶点间的可达性，可知该图的强连通分量数量为 6，每个顶点自身构成一个强连通分量（因为顶点间无法形成互相可达的环，除了可能的单个顶点）。
• 添加边使强连通分量数量为 1：至少需要添加 2 条边。一种添加方式为：添加从G到A的有向边，添加从F到B的有向边，使得所有顶点能通过这些边形成互相可达的关系。
• 删除边使顶点数量大于 1 的强连通分量数量为 0：至少需要删除 2 条边。一种删除方式为：删除D到A的有向边（权 3），删除E到C的有向边（权 8），破坏可能存在的、包含多个顶点的连通趋势。

(3) 拓扑排序判断关键路径及十字链表优势

• 判断关键路径思路：关键路径存在于有向无环图（DAG）中。首先利用拓扑排序判断图是否为 DAG（若拓扑排序结果包含所有顶点，则为 DAG，可能存在关键路径；否则不存在）。若为 DAG，再通过计算顶点的最早开始时间、最晚开始时间等，找出关键活动，进而确定关键路径。
• 十字链表优势：十字链表在存储有向图时，同时存储了以顶点为弧头和弧尾的弧信息。在求关键路径过程中，需要频繁访问某顶点的入弧和出弧（例如计算最早、最晚时间时，需要根据入弧和出弧来传递时间信息），十字链表能更直接、高效地获取这些入弧和出弧，相比邻接表（通常更便于获取出弧，获取入弧需额外操作），减少了操作步骤，提高了效率。