已知某图的邻接表如图4-12所示。 ①此邻接表所对应的无向图为(14)。 ②此图由F开始的深度优先遍历为(15)。 ③此图由9开始的深度优先遍历的支撑树为(16)。 ④此图由F开始的广度优先遍历为(17)。 ⑤此

admin2019-03-04 20

问题已知某图的邻接表如图4-12所示。

①此邻接表所对应的无向图为(14)。
②此图由F开始的深度优先遍历为(15)。
③此图由9开始的深度优先遍历的支撑树为(16)。
④此图由F开始的广度优先遍历为(17)。
⑤此图由9开始的广度优先遍历的支撑树为(18)。

选项 A、

B、

C、

答案B

解析本题实际上是考查无向图的邻接表存储方式，以及深度、广度优先遍历。
在图的邻接表中，为图的每个顶点建立一个链表，且第i个链表中的结点代表与顶点i相关联的一条边或由顶点i出发的一条弧。有n个顶点的图，需用n个链表表示，这n个链表的头指针通常由顺序线性表存储。
第一问是求邻接表所对应的无向图。首先我们看邻接表的第一行链表，在这个链表中，头结点为几后继结点有G、H和M，这表示的是结点G、H、M与结点F直接相连，而题目备选答案B中F和M并不是直接相连的，因此可以排除答案B。再看邻接表的第二行链表，在这个链表中，头结点为G，后继结点有F、I、L、J和K，这表示的是结点F、I、L、J、K与结点G直接相连，而题目备选答案A中G和L并不是直接相连的，所以答案A也可以排除。这样答案也就出来了，(1)应选C。
接下来求深度优先遍历。在图中任选一顶点V为初始出发点(源点)，则深度优先遍历可定义如下：首先访问出发点V，并将其标记为已访问过：然后依次从V出发搜索 y的每个邻接点W。若W未曾访问过，则以W为新的出发点继续进行深度优先遍历，直至图中所有和源点V有路径相通的顶点(亦称为从源点可达的顶点)均已被访问为止。若此时图中仍有未访问的顶点，则另选一个尚未访问的顶点作为新的源点重复上述过程，直至图中所有顶点均已被访问为止。
在本题中，以9为源点。首先访问9，然后扫描其邻接表，邻接表的第一个元素是 G，且G未被访问过，所以访问G。接下来扫描G的邻接表，G邻接表的第一个元素是F，已经访问过，所以跳过：第二个是I，I未被访问过，所以访问结点I。接下来扫描I的邻接表，I的邻接表的第一个元素是G，已经访问过，所以跳过：第二个是L，L未被访问过，所以访问结点L，依次类推。最终得到深度优先遍历序列为F、G、I、L、 J、K、H、M。所以(2)应选答案B。
求出了深度优先遍历，深度优先遍历的支撑树就好求了。支撑树实际上就是生成树，也就是留下深度优先遍历时经过的边，去除其余的边而得到的树。如图4-15所示。
图4-15中的实线表示深度优先遍历经过的边，虚线表示不经过的边，把虚线去除，便得到深度优先遍历生成树，如图4-16所示。
接下来求广度优先遍历。广度优先遍历的过程是：首先访问出发顶点y，然后访问与顶点V邻接的全部未被访问过的顶点W0，W1，…，Wk-1；接着再依次访问与顶点 W0，W1，…，Wk-1邻接的全部未被访问过的顶点。依次类推，直至图的所有顶点都被访问到，或出发顶点V所在的连通分量的全部顶点都被访问到为止。
在本题中，从F点出发。首先访问F，然后依次访问F邻接表中所有未被访问过的结点G、H、M。接着访问当前邻接表第一个元素所指邻接表的所有未被访问过的元素，即G的邻接表中所有未访问元素I、L、J、K。所以得到广度优先遍历序列F、G， H，M，I，L，J，K。