数据结构课后作业习题7

习题7

（1）求从顶点W出发，深度遍历图G所得的深度优先生成树

1.邻接矩阵和邻接表是储存图的常用数据结构，请问他们对应的空间复杂度是多少？分别适用于什么情况？

2.用邻接表存储有向图，若其中某顶点的入度和出度分别是5和ch，则该顶点对应的单链表的结点数是多少？

3.若G是一个具有45条边的非连通无向图（不含自回路和多重边），则图G至少有多少个顶点？

4.一个含有n个顶点和e条边的简单无向图，在其邻接矩阵存储结构中共有多少个零元素？

5.无向图G的顶点集合V和邻接矩阵A如下图所示

（2）求从顶点V2到顶点V8的最短路径及最短路径长度0111000^B1011101C1100111V D100001二E10000F0111010J

（1）画出自顶点A出发进行遍历所得的深度优先生成树

（2）画出自顶点C出发进行遍历所得的广度优先生成树

6.采用邻接表存储结构，编写算法判别无向图中任意给定的两个顶点之间是否存在一条长度为k的简单路径，并分析算法的时间复杂度

7.某区域发现了油田的存在，现在请你探测该区域一共有多少块油田输入一个m行n列的字符矩阵来代表该区域，由“”和“@”两种字符组成，“@”代表的是油田，与其相邻区域（八个方向，横竖或对角线）的属于同一块油田例如，以下5行5列区域中就有2块油田****@，能”@*@**@鲍**@

8.有向网G的邻表表为:V1264165▲345641▲V288▲V351▲v4397\5577V685▲V7V▲

89.给出一个连通的无向图，请设计算法判断其最小生成树是否是唯一，即是否有两个以上总权值相等的最小生成树

10.在选课系统中，有一些选修课程需要你来进行选择我们知道，在选择某些课程之前需要先完成一些先修的课程，例如要学习课程2可能先需要学习课程3,默认课程按照重要程度顺序给出，即应尽量先完成编号较小的课程现在给定总的课程量和选修的先决条件，请你安排出学习所有课程的顺序。