十一、已知一个图的顶点集V和边集G分别为V={0, 1, 2, 3, 4, 5, 6, 7, 8},E={<0, 1>, <0, 2>, <1, 3>, <1, 4>, <2, 4>, <2, 5>, <3, 6>, <3, 7>, <4, 7>, <4, 8>, <5, 7>, < 6, 7>, <7, 8>},若采用邻接表存储,并且每个顶点邻接表中的边结点都是按照终点序号从大到小的次序连接的,则按照拓扑排序算法,写出得到的拓扑序列,并编程实现。
十二、如下图所示的有向网络,利用Dijkstra算法求从顶点v1到其他各顶点的最短路径(要求写出如教材P155表4-2所示的Dijkstra算法的执行过程),并编程验证。
十三、应用Floyd算法,编程求下图所示有向图的每对顶点之间的最短路径(写出相应的矩阵),并求该图的中心点。并利用Warshall算法,编程求该图的传递闭包(矩阵)。
思考题1:跳马周游棋盘问题:在n×n(n<15)的国际象棋上的某一位置(键盘输入)上放置一个马,然后采用象棋中“马走日字”的规则,要求这个马能不重复地走完 n×n个格子,试用计算机求马能够走的一条路径。 提示:用深度优先搜索法
思考题2:n×n(n<15)国际象棋棋盘上有一个马,要从起点(键盘输入)跳到指定目标(键盘输入),最少跳几步,试用计算机实现。 提示:用广度优先搜索法。