HNU数据结构与算法分析-作业4-图结构

 

1. (简答题)

【应用题】11.3

（a）画出所示图的相邻矩阵表示

（b）画出所示图的邻接表表示

（c）如果每一个指针需要4字节，每一项顶点的标号占用2字节，每一条边的权需要2字节，这个图采用哪种表示方法需要占用的空间更多？

（d）如果每一个指针需要4字节，每一项顶点的标号占用1字节，每一条边的权需要2字节，这个图采用哪种表示方法需要占用的空间更多？

【应用题】11.4 对于所示图，给出从顶点1开始的DFS树

【应用题】11.6 对于所示图，给出从顶点1开始的BFS树

【应用题】11.10对于所示图，给出从顶点4出发，使用Dijkstra最短路径算法产生的最短路径。注意要有过程。

【应用题】11.17对于所示图，给出从顶点3出发使用Prim的MST算法时各个边的访问顺序，并给出最终的MST。

【应用题】11.18对于所示图，给出使用Kruskal的MST算法时各个边的访问顺序，每当把一条边添加到MST中时，显示等价类数组中的结果。

注意：课后作业必须在作业本上完成，需要有完整的计算过程。在截止时间之前，在系统提交答案照片。

作业本统一交给课代表。