2015年青海省理论数据基础

//判断以邻接矩阵表示的图g是否是二部图。

{int s[]; //顶点向量，元素值表示其属于那个集合（值1和2表示两个集合） int Q[];//Q为队列，元素为图的顶点，这里设顶点信息就是顶点编号。

int f=0,r,visited[]; //f和r分别是队列的头尾指针,visited[]是访问数组 for (i=1;i<=n;i++) {visited[i]=0;s[i]=0;} //初始化，各顶点未确定属于那个集合

Q[1]=1; r=1; s[1]=1;//顶点1放入集合S1 while(f{v=Q[++f]; if (s[v]==1) jh=2; else jh=1;//准备v的邻接点的集合号 if (!visited[v])

{visited[v]=1; //确保对每一个顶点，都要检查与其邻接点不应在一个集合中 for (j=1,j<=n;j++)

if (g[v][j]==1){if (!s[j]) {s[j]=jh; Q[++r]=j;} //邻接点入队列 else if (s[j]==s[v]) return(0);} //非二部图 }//if (!visited[v]) }//while

return(1); }//是二部图

[算法讨论] 题目给的是连通无向图，若非连通，则算法要修改。

4、两棵空二叉树或仅有根结点的二叉树相似；对非空二叉树，可判左右子树是否相似，采用递归算法。

int Similar(BiTree p,q) //判断二叉树p和q是否相似 {if(p==null && q==null) return (1); else if(!p && q || p && !q) return (0);

else return(Similar(p->lchild,q->lchild) && Similar(p->rchild,q->rchild)) }//结束Similar

5、证明由二叉树的中序序列和后序序列，也可以唯一确定一棵二叉树。 当n=1时，只有一个根结点，由中序序列和后序序列可以确定这棵二叉树。 设当n=m-1时结论成立，现证明当n=m时结论成立。 设中序序列为S1，S2，„，Sm,后序序列是P1,P2,„，Pm。因后序序列最后一个元素Pm是根，则在中序序列中可找到与Pm相等的结点（设二叉树中各结点互不相同）Si(1≤i≤m)，因中序序列是由中序遍历而得，所以Si是根结点，S1，S2，„，Si-1是左子树的中序序列，而Si+1,Si+2,„,Sm是右子树的中序序列。

若i=1，则S1是根，这时二叉树的左子树为空，右子树的结点数是m-1,则{S2，S3，„，Sm}和{P1，P2，„，Pm-1}可以唯一确定右子树，从而也确定了二叉树。 若i=m,则Sm是根，这时二叉树的右子树为空，左子树的结点数是m-1，则{S1，S2，„，Sm-1}和{P1，P2，„，Pm-1}唯一确定左子树，从而也确定了二叉树。

最后，当1序遍历是“左子树—右子树—根结点”，所以{P1,P2,„,Pi-1}和{Pi,Pi+1,„Pm-1}是二叉树的左子树和右子树的后序遍历序列。因而由{S1，S2，„，Si-1}和{P1，P2，„，Pi-1} 可唯一确定二叉树的左子树，由{Si+1,Si+2,„，Sm}和 {Pi,Pi+1,„，Pm-1}可唯一确定二叉树的右子树。 6、连通图的生成树包括图中的全部n个顶点和足以使图连通的n-1条边，最小生成树是边上权值之和最小的生成树。故可按权值从大到小对边进行排序，然后从大到小将边删除。每删除一条当前权值最大的边后，就去测试图是否仍连通，若不再连通，则将该边恢复。若仍连通，继续向下删；直到剩n-1条边为止。 void SpnTree (AdjList g)

//用“破圈法”求解带权连通无向图的一棵最小代价生成树。

{typedef struct {int i,j,w}node; //设顶点信息就是顶点编号，权是整型数 node edge[];

scanf( \"%d%d\输入边数和顶点数。

for (i=1;i<=e;i++) //输入e条边：顶点，权值。

scanf(\"%d%d%d\" ,&edge[i].i ,&edge[i].j ,&edge[i].w);

for (i=2;i<=e;i++) //按边上的权值大小，对边进行逆序排序。 {edge[0]=edge[i]; j=i-1;

while (edge[j].wwhile (eg>=n) //破圈，直到边数e=n-1. {if (connect(k)) //删除第k条边若仍连通。

{edge[k].w=0; eg--; }//测试下一条边edge[k]，权值置0表示该边被删除 k++; //下条边 }//while }//算法结束。

connect()是测试图是否连通的函数，可用图的遍历实现，