（4）
8（4）邻接表和逆邻接表
9．（1） 邻接矩阵下标按字母升序:abcdefghi
注：
（2）强连通分量：（a），(d)，
（h），
(b，e，i，
f，c，g）
(3 ) 顶点a到顶点i的简单
路径：
（a?b?e?i），
(a?c?g?i)，
(a?c?b?e?i)
10．图G的具体存储结构略。
2
邻接矩阵表示法，有n个顶点的图占用n个元素的存储单元，与边的个数无关，当边数较少时，存储效率较低。这种结构下，对查找结点的度、第一邻接点和下一邻接点、两结点间是否有边的操作有利，对插入和删除顶点的操作不利。
邻接表表示法是顶点的向量结构与顶点的邻接点的链式存储结构相结合的结构，顶点的向量结构含有n（n≥0）个顶点和指向各顶点第一邻接点的指针，其顶点的邻接点的链式存储结构是根据顶点的邻接点的实际设计的。这种结构适合查找顶点及邻接点的信息，查顶点的度，增加或删除顶点和边（弧）也很方便，但因指针多占用了存储空间，另外，某两顶点间是否有边（弧）也不如邻接矩阵那么清楚。对有向图的邻接表，查顶点出度容易，而查顶点入度却困难，要遍历整个邻接表。要想查入度象查出度那样容易，就要建立逆邻接表。无向图邻接表中边结点是边数的二倍也增加了存储量。
十字链表是有向图的另一种存储结构，将邻接表和逆邻接表结合到一起，弧结点也增加了信息（至少弧尾，弧头顶点在向量中的下标及从弧尾顶点发出及再入到弧头顶点的下一条弧的四个信息）。查询顶点的出度、入度、邻接点等信息非常方便。
邻接多重表是无向图的另一种存储结构，边结点至少包括5个域：连接边的两个顶点在顶点向量中的下标，指向与该边相连接的两顶点的下一条边的指针，以及该边的标记信息（如该边是否被访问）。边结点的个数与边的个数相同，这是邻接多重表比邻接表优越之处。
11．
已知顶点i，找与i相邻的顶点j的规则如下：在顶点向量中，找到顶点i，顺其指针找到第一个边结点（若其指针为空，则顶点i无邻接点）。在边结点中，取出两顶点信息，若其中有j，则找到顶点j；否则，沿从i发出的另一条边的指针（ilink）找i的下一邻接点。在这种查找过程中，若边结点中有j，则查找成功；若最后ilink为空，，则顶点i无邻接点j。
12．按各顶点的出度进行排序。n个顶点的有向图，其顶点最大出度是n-1，最小出度为0。这样排序后，出度最大的顶点编号为1，出度最小的顶点编号为n。之后，进行调整，即若存在弧
13．采用深度优先遍历算法，在执行dfs(v)时，若在退出dfs(v)前，碰到某顶点u ，其邻接点是已经访问的顶点v，则说明v的子孙u有到v的回边，即说明有环，否则，无环。（详见下面算法题13）
14．深度优先遍历序列：125967384
宽度优先遍历序列：123456789
注：（1）邻接表不唯一，这里顶点的邻接点按升序排列
（2）在邻接表确定后，深度优先和宽度优先遍历序列唯一 （3）这里的遍历，均从顶点1开始
15．（1）V1V2V4V3V5V6 （2）V1V2V3V4V5V6
16成树
（2）深度优先生成树16.(1)
题（3）宽度优先生
为节省篇幅，生成树横画，下同。
17．设从顶点1开始遍历，则深度优先生成树(1)和宽度优先生成树(2)为：
图17(1) 图17(2)
18．遍历不唯一的因素有：开始遍历的顶点不同；存储结构不同；在邻接表情况下邻接点的顺序不同。
19．（1）邻接矩阵：（6*6个元素）*2字节/元素=72字节
邻接表：表头向量6*（4+2）+边结点9*(2+2+4)*2=180字节
邻接多重表：表头向量6*（4+2）+边结点9*（2+2+2+4+4）=162字节
邻接表占用空间较多，因为边较多，边结点
又是边数的2倍，一般来说，邻接矩阵所占空间与边个数无关（不考虑压缩存储），适合存储稠密图，而邻接表适合存储稀疏图。邻接多重表边结点个数等于边数，但结点中增加了一个顶点下标域和一个指针域。
（2）因未确定存储结构，从顶点1开始的DFS
树
不唯一，现列出两个：
20．未确定存储结构，其DFS树不唯一，其中之一（按邻接点逆序排列）是
（2）关节点有3，1，8，7，2
百度搜索“77cn”或“免费范文网”即可找到本站免费阅读全部范文。收藏本站方便下次阅读，免费范文网，提供经典小说综合文库数据结构第七章考试题库(含答案)(7)在线全文阅读。
相关推荐：