目录

第六章 图

1．选择题

2．应用题

（1）已知如下图所示的有向图，请给出：

（2）已知如图6.28所示的无向网，请给出：          ​

（3）已知图的邻接矩阵如6.29所示。试分别画出自顶点1出发进行遍历所得的深度优先生成树和广度优先生成树。

（4）有向网如图6.30所示，试用迪杰斯特拉算法求出从顶点a到其他各顶点间的最短路径，完成表6.9。  

（5）试对图6.31所示的AOE-网：

3．算法设计题

（1）分别以邻接矩阵和邻接表作为存储结构，实现以下图的基本操作：

（2）一个连通图采用邻接表作为存储结构，设计一个算法，实现从顶点v出发的深度优先遍历的非递归过程。

（3）设计一个算法，求图G中距离顶点v的最短路径长度最大的一个顶点，设v可达其余各个顶点。

（4）试基于图的深度优先搜索策略写一算法，判别以邻接表方式存储的有向图中是否存在由顶点vi到顶点vj的路径（i≠j）。

（5）采用邻接表存储结构，编写一个算法，判别无向图中任意给定的两个顶点之间是否存在一条长度为为k的简单路径。      

                                               第六章 图

1．选择题

（1）在一个图中，所有顶点的度数之和等于图的边数的（   ）倍。

  A．1/2            B．1             C．2             D．4

（2）在一个有向图中，所有顶点的入度之和等于所有顶点的出度之和的（   ）倍。

  A．1/2            B．1             C．2             D．4

（3）具有n个顶点的有向图最多有（   ）条边。  

A．n              B．n(n-1)         C．n(n+1)        D．n2 

（4）n个顶点的连通图用邻接距阵表示时，该距阵至少有（   ）个非零元素。

A．n              B．2(n-1)         C．n/2           D．n2 

（5）G是一个非连通无向图，共有28条边，则该图至少有（   ）个顶点。

A．7              B．8             C．9             D．10

（6）若从无向图的任意一个顶点出发进行一次深度优先搜索可以访问图中所有的顶点，则该图一定是（   ）图。

A．非连通         B．连通          C．强连通        D．有向

（7）下面（　）算法适合构造一个稠密图G的最小生成树。

A． Prim算法      B．Kruskal算法   C．Floyd算法     D．Dijkstra算法

（8）用邻接表表示图进行广度优先遍历时，通常借助（   ）来实现算法。

A．栈            B. 队列            C.  树            D．图

（9）用邻接表表示图进行深度优先遍历时，通常借助（   ）来实现算法。

A．栈            B. 队列            C.  树            D．图

（10）深度优先遍历类似于二叉树的（   ）。

A．先序遍历      B．中序遍历        C．后序遍历      D．层次遍历

（11）广度优先遍历类似于二叉树的（   ）。

A．先序遍历      B．中序遍历        C．后序遍历       D．层次遍历

（12）图的BFS生成树的树高比DFS生成树的树高（   ）。

A．小            B．相等            C．小或相等       D．大或相等

（13）已知图的邻接矩阵如图6.25所示，则从顶点0出发按深度优先遍历的结果是（   ）。

 

（14）已知图的邻接表如图6.26所示，则从顶点0出发按广度优先遍历的结果是（   ），按深度优先遍历的结果是（   ）。

 （15）下面（   ）方法可以判断出一个有向图是否有环。

A．深度优先遍历      B．拓扑排序      C．求最短路径     D．求关键路径

2．应用题

（1）已知如下图所示的有向图，请给出：

 

① 每个顶点的入度和出度；    ② 邻接矩阵；③ 邻接表；④ 逆邻接表。

（2）已知如图6.28所示的无向网，请给出：          

a

→

b

4

→

c

3

b

→

a

4

→

c

5

→

d

5

→

e

9

^

c

→

a

3

→

b

5

→

d

5

→

h

5

^

d

→

b

5

→

c

5

→

e

7

→

f

6

→

g

5

→

h

4^

e

→

b

9

→

d

7

→

f

3

^

f

→

d

6

→

e

3

→

g

2

^

g

→

d

5

→

f

2

→

h

6

^

h

→

c

5

→

d

4

→

g

6

^

（3）已知图的邻接矩阵如6.29所示。试分别画出自顶点1出发进行遍历所得的深度优先生成树和广度优先生成树。

（4）有向网如图6.30所示，试用迪杰斯特拉算法求出从顶点a到其他各顶点间的最短路径，完成表6.9。  

D 终点	i=1	i=2	i=3	i=4	i=5	i=6
b	15 (a,b)	15 (a,b)	15 (a,b)	15 (a,b)	15 (a,b)	15 (a,b)
c	2 (a,c)
d	12 (a,d)	12 (a,d)	11 (a,c,f,d)	11 (a,c,f,d)
e	∞	10 (a,c,e)	10 (a,c,e)
f	∞	6 (a,c,f)
g	∞	∞	16 (a,c,f,g)	16 (a,c,f,g)	14 (a,c,f,d,g)
S 终点集	{a,c}	{a,c,f}	{a,c,f,e}	{a,c,f,e,d}	{a,c,f,e,d,g}	{a,c,f,e,d,g,b}

（5）试对图6.31所示的AOE-网：

① 求这个工程最早可能在什么时间结束；    

② 求每个活动的最早开始时间和最迟开始时间；

③ 确定哪些活动是关键活动

 【解答】按拓扑有序的顺序计算各个顶点的最早可能开始时间Ve和最迟允许开始时间Vl。然后再计算各个活动的最早可能开始时间e和最迟允许开始时间l，根据l - e = 0? 来确定关键活动，从而确定关键路径。

	1	2	3	4	5	6
Ve	0	19	15	29	38	43
Vl	0	19	15	37	38	43

e	0	0	15	19	19	15	29	38
l	17	0	15	27	19	27	37	38
l-e	17	0	0	8	0	12	8	0

此工程最早完成时间为43。关键路径为

3．算法设计题

（1）分别以邻接矩阵和邻接表作为存储结构，实现以下图的基本操作：

① 增添一个新顶点v，InsertVex(G, v)；

② 删除顶点v及其相关的边，DeleteVex(G, v);

③ 增加一条边，InsertArc(G, v, w);

④ 删除一条边，DeleteArc(G, v, w)。

//本题中的图G均为有向无权图,其余情况容易由此写出
Status Insert_Vex(MGraph &G, char v)//在邻接矩阵表示的图G上插入顶点v
{
if(G.vexnum+1)>MAX_VERTEX_NUM return INFEASIBLE;
G.vexs[++G.vexnum]=v;
return OK;
}//Insert_Vex
Status Insert_Arc(MGraph &G,char v,char w)//在邻接矩阵表示的图G上插入边(v,w)
{
if((i=LocateVex(G,v))nextarc)

    {

      k=p->adjvex;

      if(!visited[k]&&exist_path(k,j)) return 1;//i下游的顶点到j有路径

    }//for

  }//else

}//exist_path_DFS

解2：（以上算法似乎有问题：如果不存在路径，则原程序不能返回0。我的解决方式是在原程序的中引入一变量level来控制递归进行的层数。具体的方法我在程序中用红色标记出来了。）

int visited[MAXSIZE]; //指示顶点是否在当前路径上

int level＝1;//递归进行的层数

int exist_path_DFS(ALGraph G,int i,int j)//深度优先判断有向图G中顶点i到顶点j

是否有路径,是则返回1,否则返回0

{

  if(i==j) return 1; //i就是j

  else

  {

    visited[i]=1;

    for(p=G.vertices[i].firstarc;p;p=p->nextarc，level--)

    { level++;

      k=p->adjvex;

      if(!visited[k]&&exist_path(k,j)) return 1;//i下游的顶点到j有路径

}//for

  }//else

if (level==1)  return 0;

}//exist_path_DFS

（5）采用邻接表存储结构，编写一个算法，判别无向图中任意给定的两个顶点之间是否存在一条长度为为k的简单路径。      

（注1：一条路径为简单路径指的是其顶点序列中不含有重现的顶点。

注2：此题可参见严题集P207-208中有关按“路径”遍历的算法基本框架。）

int visited[MAXSIZE];

int exist_path_len(ALGraph G,int i,int j,int k)//判断邻接表方式存储的有向图G

的顶点i到j是否存在长度为k的简单路径

{

{

  if(i==j&&k==0) return 1; //找到了一条路径,且长度符合要求

  else if(k>0)

  {

    visited[i]=1;

    for(p=G.vertices[i].firstarc;p;p=p->nextarc)

    {

      l=p->adjvex;

      if(!visited[l])

        if(exist_path_len(G,l,j,k-1)) return 1; //剩余路径长度减一

    }//for

    visited[i]=0; //本题允许曾经被访问过的结点出现在另一条路径中

  }//else

  return 0; //没找到

}//exist_path_len