本文探讨了图数据结构中的两种表示方法——邻接矩阵和邻接多重表。分析它们的特点、应用场景及各自的优缺点，旨在为实际问题提供有效的解决方案。
对于任意给定的图（顶点数至少为20且边数不少于30），能够输入其顶点与边的信息，并将其存储在邻接矩阵或邻接表等两种数据结构中，完成以下功能：
1. 对无向图求每个顶点的度或者对有向图分别计算入度和出度（5分）。
2. 实现插入新顶点及连接它们的新边的功能（5分）。
3. 提供删除指定顶点或边的方法（5分）。
4. 可以在两种存储结构之间进行转换，如果其中一种是十字链表或者邻接多重表则额外加5分。（5分）
5. 输出图的深度优先遍历序列或是广度优先遍历序列（5分）。
6. 根据孩子-兄弟表示法生成树，并对其进行遍历操作（15分）。
7. 判断给定图是否连通，输出其连通分支的数量（5分）。
8. 检查是否存在环路的情况：无向图为5分；有向图为10分。
9. 根据输入的顶点u和v判断两者间是否有路径连接（5分）。
10. 寻找从起点u到终点v的一条简单路径（10分）。
11. 列出所有可能存在的从u到达v的不同简单路径（15分）。
12. 计算顶点u至v的最短距离或最小权重路线（10分）。
13. 算法计算起始点u到其它任何节点间的最短路径长度（15分）。
14. 求任意两个不同节点之间的所有可能最短路径（包括单源和多源情况，共计15分）。
15. 寻找给定图的最小生成树或支撑树（共需完成此题得分为满分中的15分）。
16. 在具有单一起点与终点的有向网络中确定关键路线（20分）。编程可以使用C、VC++或者JAVA语言，每位学生从上述题目中选取总价值为一百分的任务来实现。请注意，必须包含第一至第六项任务在内的选择。
5星
