数据结构第六章图

《数据结构第六章图》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、一、问答题1.在图7.1所示的各无向图中：(1)找出所有的简单环。(2)哪些图是连通图?对非连通图给出其连通分量。(3)哪些图是自由树(或森林)?2.在图7.2(下图)所示的有向图中：　　　　(1)该图是强连通的吗?若不是，则给出其强连通分量。　(2)请给出所有的简单路径及有向环。　(3)请给出每个顶点的度，入度和出度。　(4)请给出其邻接表、邻接矩阵及逆邻接表。3.假设图的顶点是A,B...，请根据下述的邻接矩阵画出相应的无向图或有向图。(1)该图是强连通的吗?若不是，则给出其强连通分量。　(2)请给出所有的简单路径及

2、有向环。　(3)请给出每个顶点的度，入度和出度。　(4)请给出其邻接表、邻接矩阵及逆邻接表3.假设图的顶点是A,B...，请根据下述的邻接矩阵画出相应的无向图或有向图。窗体底部4.假设一棵完全二叉树包括A,B,C...等七个结点，写出其邻接表和邻接矩阵。5. 对n个顶点的无向图和有向图，采用邻接矩阵和邻接表表示时，如何判别下列有关问题?(1)图中有多少条边?(2)任意两个顶点i和j是否有边相连?(3)任意一个顶点的度是多少?6.n个顶点的连通图至少有几条边?强连通图呢?7.DFS和BFS遍历各采用什么样的数据结构来暂存顶

3、点?当要求连通图的生成树的高度最小，应采用何种遍历答案1.在图7.1所示的各无向图中：(1)找出所有的简单环。(2)哪些图是连通图?对非连通图给出其连通分量。(3)哪些图是自由树(或森林)?答:　(1)所有的简单环：(同一个环可以任一顶点作为起点)　　　(a)1231　　　(b)无　　　(c)1231、2342、12341　　　(d)无　(2)连通图：　　　(a)、(c)、(d)是连通图，　　　(b)不是连通图，因为从1到2没有路径。具体连通分量为：　  (3)自由树(森林)：自由树是指没有确定根的树，无回路的连通图称为

4、自由树：　　　(a)不是自由树，因为有回路。　　　(b)是自由森林，其两个连通分量为两棵自由树。　　　(c)不是自由树。(d)是自由树。2答：　(1)该图是强连通的，所谓强连通是指有向图中任意顶点都存在到其他各顶点的路径。　(2)简单路径是指在一条路径上只有起点和终点可以相同的路径：　　有v1v2、v2v3、v3v1、v1v4、v4v3、v1v2v3、v2v3v1、v3v1v2、v1v4v3、v4v3v1、v3v1v4、另包括所有有向环,有向环如下：　　　　　v1v2v3v1、v1v4v3v1(这两个有向环可以任一顶点作

5、为起点和终点)　(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)邻接矩阵：01010010100000103.4.5.对n个顶点的无向图和有向图，采用邻接矩阵和邻接表表示时，如何判别下列有关问题? (1)图中有多少条边?(2)任意两个顶点i和j是否有边相连?(3)任意一个顶点的度是多少?答：对于n个顶点的

6、无向图和有向图，用邻接矩阵表示时：(1)设m为矩阵中非零元素的个数　　　无向图的边数=m/2　　　有向图的边数=m　(2)无论是有向图还是无向图，在矩阵中第i行,第j列的元素若为非零值，则该两顶点有边相连。　(3)对于无向图，任一顶点i的度为第i行中非零元素的个数。　　对于有向图，任一顶点i的入度为第i列中非零元素的个数，出度为第i行中非零元素的个数，度为入度出度之和。　　当用邻接表表示时：　(1)对于无向图，图中的边数=边表中结点总数的一半。　　　对于有向图，图中的边数=边表中结点总数。(2)对于无向图，任意两顶点间是

7、否有边相连，可看其中一个顶点的邻接表，若表中的adjvex域有另一顶点位置的结点，则表示有边相连。　　　对于有向图，则表示有出边相连。　(3)对于无向图，任意一个顶点的度则由该顶点的边表中结点的个数来决定。　　对于有向图，任意一个顶点的出度由该顶点的边表中结点的个数来决定，入度则需遍历各顶点的边表。(用逆邻接表可容易地得到其入度。)6.n个顶点的连通图至少有几条边?强连通图呢?答：n个顶点的连通图至少有n-1条边，强连通图至少有2(n-1)条边。7.DFS和BFS遍历各采用什么样的数据结构来暂存顶点?当要求连通图的生成树

8、的高度最小，应采用何种遍历?答：DFS遍历采用栈来暂存顶点。BFS采用队列来暂存顶点。当要求连通图的生成树的高度最小时，应采用BFS遍历。