中南大学数据结构与算法第7章图课后作业答案

《中南大学数据结构与算法第7章图课后作业答案》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、第7章图(基础知识)习题练习答案7.1在图7.23所示的各无向图中：　　　　　(1)找出所有的简单环。　(2)哪些图是连通图?对非连通图给出其连通分量。　(3)哪些图是自由树(或森林)?答:　(1)所有的简单环：(同一个环可以任一顶点作为起点)　　　(a)1231　　　(b)无　　　(c)1231、2342、12341　　　(d)无　(2)连通图：　　　(a)、(c)、(d)是连通图，　　　(b)不是连通图，因为从1到2没有路径。具体连通分量为：　　　　　　(3)自由树(森林)：自由树是指没有确定根的树，无回路的连通图称为自由树：　　　(a

2、)不是自由树，因为有回路。　　　(b)是自由森林，其两个连通分量为两棵自由树。　　　(c)不是自由树。　　　(d)是自由树。7.2在图7.24(下图)所示的有向图中：　　　　　　　　　(1)该图是强连通的吗?若不是，则给出其强连通分量。　(2)请给出所有的简单路径及有向环。　(3)请给出每个顶点的度，入度和出度。　(4)请给出其邻接表、邻接矩阵及逆邻接表。答：　(1)该图是强连通的，所谓强连通是指有向图中任意顶点都存在到其他各顶点的路径。　(2)简单路径是指在一条路径上只有起点和终点可以相同的路径：　　有v1v2、v2v3、v3v1、v1v

3、4、v4v3、v1v2v3、v2v3v1、v3v1v2、v1v4v3、v4v3v1、v3v1v4、另包括所有有向环,有向环如下：　　　　　v1v2v3v1、v1v4v3v1(这两个有向环可以任一顶点作为起点和终点)　(3)每个顶点的度、入度和出度：　　　D(v1)=3　ID(v1)=1　OD(v1)=2　　　D(v2)=2　ID(v2)=1　OD(v2)=1　　　D(v3)=3　ID(v3)=2　OD(v3)=1　　　D(v4)=2　ID(v4)=1　OD(v4)=1　(4)邻接表：(注意边表中邻接点域的值是顶点的序号，这里顶点的序号是顶点

4、的下标值-1)  vertexfirstedge next　　　┌─┬─┐ ┌─┬─┐ ┌─┬─┐　　0│v1│　─→│1│　─→│3│∧│     ├─┼─┤ ├─┼─┤ └─┴─┘    1│v2│　─→│2│∧│     ├─┼─┤ ├─┼─┤    2│v3│　─→│0│∧│     ├─┼─┤ ├─┼─┤    3│v4│　─→│2│∧│     └─┴─┘ └─┴─┘ 逆邻接表：   ┌─┬─┐ ┌─┬─┐  0│v1│　─→│2│∧│   ├─┼─┤ ├─┼─┤  1│v2│　─→│0│∧│   ├─┼─┤ ├─┼─┤ ┌─┬

5、─┐  2│v3│　─→│1│　─→│3│∧│   ├─┼─┤ ├─┼─┤ └─┴─┘  3│v4│　─→│0│∧│   └─┴─┘ └─┴─┘ 邻接矩阵：   0101   0010   1000   00107.3假设图的顶点是A,B...，请根据下述的邻接矩阵画出相应的无向图或有向图。　　　　　　　　┌　　　　┓ ┌      ┓  

6、01100

7、 

8、0111

9、  

10、00010

11、  

12、1011

13、  

14、00010

15、  

16、1101

17、  

18、10001

19、  

20、1110

21、  

22、01010

23、 ┕      ┙　┕　      ┙     (a) 

24、             (b) 答:   7.4假设一棵完全二叉树包括A,B,C...等七个结点，写出其邻接表和邻接矩阵。解： 邻接表如下：　　┌─┬─┐ ┌─┬─┐ ┌─┬─┐　0│A│　─→│1│ ─→│2│∧│   ├─┼─┤ ├─┼─┤ ├─┼─┤ ┌─┬─┐  1│B│　─→│0│　─→│3│　─→│4│∧│   ├─┼─┤ ├─┼─┤ ├─┼─┤ ├─┼─┤  2│C│　─→│0│　─→│5│　─→│6│∧│   ├─┼─┤ ├─┼─┤ └─┴─┘ └─┴─┘  3│D│　─→│1│∧│   ├─┼─┤ ├─┼─┤  4│E│

25、　─→│1│∧│   ├─┼─┤ ├─┼─┤  5│F│　─→│2│∧│   ├─┼─┤ ├─┼─┤  6│G│　─→│2│∧│   └─┴─┘ └─┴─┘ 邻接矩阵如下：       0110000       1001100       1000011        0100000       0100000        0010000       00100007.5对n个顶点的无向图和有向图，采用邻接矩阵和邻接表表示时，如何判别下列有关问题? (1)图中有多少条边? (2)任意两个顶点i和j是否有边相连? (3)任意一个顶点的度是

26、多少?答：   对于n个顶点的无向图和有向图，用邻接矩阵表示时： (1)设m为矩阵中非零元素的个数 　　　无向图的边数=m/2　　　有向图的边数=m　(2)无论是有向图还是无向图