1 3 4 图7.25 2 1 5 7 9 6 2 8 3 6 4 4 4 图7.26 2 5
答：（1）假设指定从v1出发，用普里姆方法画出最小生成树的过程：
（2）用克鲁斯卡尔方法画出最小生成树的过程：
10. 修改PRIM算法，使之能在邻接链表存储结构上实现求图的最小生成树，并
分析其时间复杂度。 答;
#define MAX 100
typedef struct ArcNode {
int adjvex; /*该弧所指向的顶点的位置 */ struct ArcNode *nextarc; /*指向下一条弧的指针 */
int info; /*该弧相关信息的指针 */ }ArcNode;
typedef struct VNode {
char data; /*顶点信息 */
ArcNode *firstarc; /*指向第一条依附该顶点的弧的指针 */ }VNode,AdjList[MAX];
typedef struct{ AdjList vertices;
int vexnum,arcnum; /*图的当前顶点数和弧数 */ }ALGraph;
void Prim(ALGraph G,int k,CSTree &T)
/*从顶点k出发,构造邻接表结构的有向图G的最小生成森林T,用孩子兄弟链表存储*/ {
for(j=0;j closedge[j]={k,Max_int}; for(p=G.vertices[j].firstarc;p;p=p->nextarc) if(p->adjvex==k) closedge[j].lowcost=p->cost; }/*if*/ closedge[k].lowcost=0; for(i=1;i k=minimum(closedge); if(closedge[k].lowcost Addto_Forest(T,closedge[k].adjvex,k); /*把这条边加入生成森林中*/ closedge[k].lowcost=0; for(p=G.vertices[k].firstarc;p;p=p->nextarc) if(p->cost closedge[p->adjvex]={k,p->cost}; }//if else Forest_Prim(G,k); /*对另外一个连通分量执行算法*/ }/*for*/ }/*Forest_Prim */ void Addto_Forest(CSTree &T,int i,int j)/*把边(i,j)添加到孩子兄弟链表表示的树T中*/ { p=Locate(T,i); /*找到结点i对应的指针p,过程略*/ q=(CSTNode*)malloc(sizeof(CSTNode)); q->data=j; if(!p) /*起始顶点不属于森林中已有的任何一棵树*/ { p=(CSTNode*)malloc(sizeof(CSTNode)); p->data=i; for(r=T;r->nextsib;r=r->nextsib); r->nextsib=p; p->firstchild=q; } /*作为新树插入到最右侧*/ else if(!p->firstchild) /*双亲还没有孩子*/ p->firstchild=q; /*作为双亲的第一个孩子*/ else /*双亲已经有了孩子*/ { for(r=p->firstchild;r->nextsib;r=r->nextsib); r->nextsib=q; /*作为双亲最后一个孩子的兄弟*/ } }/*Addto_Forest */ main() { ... T=(CSTNode*)malloc(sizeof(CSTNode)); /*建立树根*/ T->data=1; Forest_Prim(G,1,T); ... }/*main*/ 分析:这个算法是在Prim算法的基础上添加了非连通图支持和孩子兄弟链表构建 模块而得到的,其时间复杂度为O(n^2). 11. 求出图7.27从顶点v1到其它各顶点之间的最短路径。绘制图表解题。 答: dist path dist path dist path V2 20 V1 20 V1 20 V1 V3 5 V1 V4 ∞ V1 ∞ V1 19 V6 V5 ∞ V1 ∞ V1 25 V6 V6 ∞ V1 15 v3 S V1 V1,v3 V1,v3, v6 V-S V2, v3,v4, v5, v6 V2, v4,v5, v6 v2, v4, v5 v2, v5 v5 shortpath v3 V6 v4 v2 v5 dist 20 25 V1,v3, v6,v4 path V1 V6 dist 25 V1,v3, path V6 v6,v4,v2 dist V1,v3, path v6,v4,v2, v5 12. 写出图7.28的三种可能的拓朴排序结果。 答: 5,2,1,3,4,6,7,8 5,2,4,3,1,7,6,8 7,5,2,1,3,4,6,8 5 10 4 6 5 4 30 10 图7.27 10 2 2 4 3 20 1 5 5 4 图7.28 1 2 3 8 7 6 讨论小课堂8 [参考内容] 1．若二叉排序树中的一个结点存在两个孩子，那么它的中序后继结点是否有左孩子？它的中序前驱结点是否有右孩子？ 【参考答案】：若p是给定的二叉排序树中的某个结点，且p有左、右孩子。按照中序遍历的思想，先中序遍历p的左子树，再访问根结点p，最后遍历p的右子树。左子树最后访问的结点x为p的前驱结点，x一定没有右子树， 否者x不是左子树上中序遍历中最后访问的结点。因而，p的前驱结点x没有右孩子。同理，p的中序后继结点x没有左孩子。 2．若将关键字1，2，3，┅，2k-1依次插入到一棵初始为空的AVL中，能证明结果树是完全平衡的吗？ 【参考答案】：所谓“完全平衡”是指所有叶子结点处于树的同一层次上，并在该层是满的。 第一步，当k=1时，21-1=1，AVL树只有一个结点，它既是根又是叶子并处在第0层，根据二叉树性质，应具有20=1个结点。因此，满足完全平衡要求。 第二步，设k=n，插入关键码1，2，3，┅，2n-1到AVL树中，恰好每一层(层次号码是i=0，1，2，3，┅，n-1)有2i个结点，根据二叉树性质，每一层达到最多结点个数，满足完全平衡要求。则当k=n+1时，插入关键码为1，2，3，┅，2n-1，2n，┅，2n+1-1，总共增加了从2n到2n+1-1的2n+1-1-2n+1=2n个关键码，使得AVL树在新增的第n层具有2n个结点，达到该层最多结点个数，因此，满足完全平衡要求。 由上可的，能证明它是完全平衡的。 3．假设有关键码A、B、C和D，按照不同的输入顺序，共可能组成多少不同的二叉排序树？AVL树有几种？完全二叉树有几种？请画出其中高度较小的6种。 【参考答案】：本题的含义是：给定中序序列1，2，3，4，有几种不同的二叉排序树，这是树的计数问题。设中序遍历序列中元素数为n，则二叉树的数目为1(n?1)n?C2n，这里n=4，故有14种。 AVL树有4种。 完全二叉树有1种。 6种高度较小的二叉排序树如下所示。 A B B C A C A D B D D C C B D A D B A B A C D C