1.已知以二维数组表示的图的邻接矩阵如下图所示。
试分别画出自序号为0的顶点出发进
行遍历所得的深度优先生成树和广度优先生成树。
图题7.1
2.请对图题7.2的无向带权图,
(1)写出它的邻接矩阵,并按Prim算法求其最小生成树
(2)写出它的邻接表,并按Kruskal算法求其最小生成树
图题7.2 (注意:约定字符ASCII值小的物理存储也在前)
3.试按所述Dijkstra算法求图题7.3从顶点a到其他各定点间的最短路径,并写出执行过
程中Dist和Path的值的变化状况。
图题7.3
4.试列出图题7.4中全部可能的拓扑有序序列,并指出按7.5节中所描述的拓扑排序算法
求得的是哪个序列(注意:应确定其存储结构)
图题7.4
5.对于图题7.5所示的AOE网络,计算各事件(顶点)的ve(v i)和vl(v j)函数值以及各活动弧
的ee(a i)和el(a j)函数值。
并列出各条关键路径。
图题7.5
思考题
6.试基于图的深度优先搜索策略写一算法,判别以邻接表方式存储的有向图中是否存在由
顶点v i到顶点v j的路径(i≠j)。