2. 计算机
  3. 设有向图G=(V，E)，其中V={V1，V2，V3，V4，V5，V6，V7，V8)，E={V1，V2＞，＜V1，V3＞，＜V2，V4＞，＜V2，V6＞，＜V3，V5＞，＜V4，V8＞，＜V5，V4＞，＜V6，V3＞，＜V6，V7＞， (V7，V5＞，＜V8

设有向图G=(V，E)，其中V={V1，V2，V3，V4，V5，V6，V7，V8)，E={V1，V2＞，＜V1，V3＞，＜V2，V4＞，＜V2，V6＞，＜V3，V5＞，＜V4，V8＞，＜V5，V4＞，＜V6，V3＞，＜V6，V7＞， (V7，V5＞，＜V8

admin2010-01-23  5
问题 设有向图G=(V，E)，其中V={V1，V2，V3，V4，V5，V6，V7，V8)，E={V1，V2＞，＜V1，V3＞，＜V2，V4＞，＜V2，V6＞，＜V3，V5＞，＜V4，V8＞，＜V5，V4＞，＜V6，V3＞，＜V6，V7＞， (V7，V5＞，＜V8，V7＞)，那么该图的邻接表可以是(10)，按照该邻接表从V1，出发，图G的深度优先遍历序列为(11)，广度优先遍历序列为(12)。
选项 A、V1 V2 V6 V3 V5 V4 V8 V7
B、V1 V3 V2 V4 V6 V5 V8 V7
C、V1 V2 V3 V4 V6 V5 V8 V7
D、V1 V2 V3 V4 V6 V5 V7 V8
答案C
解析 根据边集E可以得到图G如图13-29所示。

在有向无权图的邻接表中，对图中每个顶点Vi建立一个单链表，第i个单链表中的表结点表示从顶点Vi出发的边。每个表结点由两个域组成：邻接点域，用以指示与Vi邻接的点在图中的位置；链域。用以指向从顶点Vi出发的下一条边对应的结点。每个链表上附设一个表头结点，它设有两个域：链域，指向链表中的第一个结点；数据域，存储顶点的名称或其它信息，如图13-30所示。

图的深度优先遍历的基本思想是：从图G的某个顶点V0出发，访问、V0，然后选择一个与V0相邻且未被访问过的顶点Vi访问，再从Vi出发选择一个与Vi相邻且未被访问的顶点Vj进行访问，依此继续。如果当前被访问的顶点的所有邻接顶点都已被访问过，则退回到已被访问的顶点序列中最后一个拥有未被访问的相邻顶点的顶点W，从W出发按同样方法进行访问，直到图中所有与V0相通的顶点都被访问。此时，若图中尚有顶点未被访问，则另选图中一个未曾访问的顶点做起始点，重复上述过程，直到图中所有顶点都被访问过。值得强调的是。这里可能有回退的过程。在未给定图的邻接表时，由于一个顶点可能有多个邻接点，导致有不同的选择，从而最后得到不同的遍历顺序。而当给定一个图的邻接表之后，不管是深度优先遍历还是广度优先遍历，遍历结果都只有一种。在对G从V1开始进行深度优先遍历时，先访问V1，之后因为以V1为表头接点的单链表的第一个表结点的邻接点域里存的是1，这是V2所在的下标，于是访问V2，接着因为以V2为表头结点的单链表的第一个表结点的邻接点域里存的是5，这是V6的下标，于是访问V6。类似地，接下来依次访问V3、V5、V4、V8、V7。图的广度优先遍历的基本思想是：首先访问初始点Vi，并将其标记为已经访问过，接着访问Vi的所有未被访问过的邻接点Vi1、Vi2、Vi3... 、Vit，并标记为已访问过，然后再按照Vi1、Vi2、Vi3、... 、Vit的次序(注意，一定得按照这个对应的次序)访问每一个顶点的所有未被访问过的邻接点，并将其标记为已访问过。依此类推，直到图中所有和初始点Vi有路径相通的顶点都被访问过为止。此时，若图中尚有顶点未被访问，则另选图中一个未曾访问的顶点做起始点，重复上述过程，直到图中所有顶点都被访问过。换句话说，广度优先遍历图的过程是以Vi为起始点，由近至远，依次访问跟Vi有路径相通且路径长度为 1、2、…的顶点。从V1出发对G进行广度优先遍历，先访问V1，接着因为以V1为表头结点的单链表可知接下来依次访问V2、V3、V4，然后访问V2的邻接点V6，接着访问V3的邻接点V5，再接着访问V4的邻接点V8，最后访问V8的邻接点V7。
转载请注明原文地址:https://kaotiyun.com/show/0qxZ777K
本试题收录于： 软件设计师上午基础知识考试题库软考中级分类
0

软件设计师上午基础知识考试

软考中级

相关试题推荐
随机试题
最新回复(0)