第6章应用题
(1)已知图6.32所示的有向图,请给出:
① 每个顶点的入度和出度;
② 邻接矩阵;
③ 邻接表;
④ 逆邻接表。
答案:
(2)已知如图6.33所示的无向网,请给出:
① 邻接矩阵;
② 邻接表;
③ 最小生成树
答案:
(3)已知图的邻接矩阵如图6.34所示。试分别画出自顶点1出发进行遍历所得的深度优先生成树和广度优先生成树。
(4)有向网如图6.35所示,试用迪杰斯特拉算法求出从顶点a到其他各顶点间的最短路径,完成表6.9。
(5)试对图6.36所示的AOE-网:
① 求这个工程最早可能在什么时间结束;
② 求每个活动的最早开始时间和最迟开始时间;
③ 确定哪些活动是关键活动