一个有向图G的邻接表存储如图8-37所示，现按深度优先搜索方式从顶点执行一次遍历，所得到的顶点

于此存储结构从顶点A开始进行深度优先搜紫，得到的项点序列是()。

A、ABCDGIFE

B、ABCDGFHE

C、ABGHFECD

D、ABFHEGDC

E、ABEHFGDC

F、ABEHGFCD

A.0132

B.0231

C.0321

D.0123

试写一个算法，判别以邻接表方式存储的有向图中是否存在由顶点v到顶点y的路径（i≠j)。假设分别基于下述策路: 1)图的深度优先搜索: 2)图的广度优先搜索。

所谓单目标最短路径（single-destinationshortestpath)问题是指在一个带权有向图G中求从各个顶

点到某一指定顶点v的最短路径，例如，对于图8-47(a)所示的带权有向图，用该算法求得的从各顶点到顶点2的最短路径如图8-47(b)所示.

关于最短路径的读法以顶点0为例，在从顶点0到顶点2的最短路径上，顶点0的后继为顶点1(即path[0]=1)，顶点1的后继为顶点3(即path[1]=3)，顶点3的后继顶点为2(即path[3]=2).

编写一个算法，求解一个带权有向图的单目标最短路径问题。假设图G的顶点数据的类型为char，边上权值的数据类型为float。

在以下假设下，重写Djkstra算法：（1)用邻接表表示有向带权图G，其中每个边结点有3个域：邻接顶点v

在以下假设下，重写Djkstra算法：

(1)用邻接表表示有向带权图G，其中每个边结点有3个域：邻接顶点vertex，边上的权值length和边链表的链接指针link

(2)用集合T=V(G)-S代替S(已找到最短路径的顶点集合)，利用链表来表示集合T。

试比较新算法与原来的算法，计算时间是快了还是慢了，给出定量的比较。

对于一个具有n个顶点和e条边的无向图，若用邻接表存储，顶点向量的大小至少为（①)，所有顶点的边链表中的结点总数最多为（②)。

A、n²

B、n(n-l

C、n(n+1)

D、n(n-I)/2

本题给出二部图（bipartitegraph)的概念。设G=（V，E)是一类无向图，可以把它们的顶点划分为两个互

不相交的子集A和B=V-A，并且这两个子集具有下列性质：

(a)A中任何两个顶点在G中都不是相互邻接的;(b)B中任何两个顶点在G中都不是相互邻接的。例如，图8-34就是二部图。对V(G)的一个划分可能是A=(0，3，4，6)和B=(1，2，5，7).

(1)试编写一个算法，判断图G是否是二部图。如果图G是二部图，则你的算法应当把项点划分成为具有上述性质的两个互不相交的子集A和B。证明：当用邻接表表示图G时，这个算法的复杂度可以做到O(n+e)。其中n是图G的顶点个数，e是边数。

(2)证明：任何-棵树都是二部图

(3)证明：当且仅当图G不包含奇数条边的回路时.它是二部图。

_______个。

一个有向图如图8-45所示。试问：

(1)它是强连通图吗？如果不是，画出它的强连通分量。

(2)分别给出经过深度优先搜索和广度优先搜索所得到的生成树(森林)。