盗墓笔记,盗墓笔记

問答題 已知有向圖如下所示，請寫出該圖所有的拓撲序列。

1.問答題 已知圖G如下所示，根據Prim算法，構造最小生成樹。（要求給出生成過程）

2.問答題 AOE網G如下所示，求關鍵路徑。（要求標明每個頂點的最早發(fā)生時間和最遲發(fā)生時間，并畫出關鍵路徑）

（1）最早發(fā)生時間和最遲發(fā)生時間：

（2）關鍵路徑：

3.問答題 寫出下圖中全部可能的拓撲排序序列。

1，5，2，3，6，4
1，5，6，2，3，4
5，1，2，3，6，4
5，1，6，2，3，4
5，6，1，2，3，4

4.問答題 設一個無向圖的鄰接矩陣如下圖所示：
（1）畫出該圖；
（2）畫出從頂點0出發(fā)的深度優(yōu)先生成樹；

(1)圖形態(tài)

(2)深度優(yōu)先搜索樹

5.問答題 已知圖G的鄰接矩陣如下所示：
（1）求從頂點1出發(fā)的廣度優(yōu)先搜索序列；
（2）根據prim算法，求圖G從頂點1出發(fā)的最小生成樹，要求表示出其每一步生成過程。（用圖或者表的方式均可）。

(1)廣度優(yōu)先遍歷序列：1; 2, 3, 4; 5; 6
(2)最小生成樹（prim算法）

宁国都颈装饰工程有限公司