int BPGraph (AdjMatrix g)
//判断以邻接矩阵表示的图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 {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); }//是二部图 [算法讨论] 题目给的是连通无向图，若非连通，则算法要修改。 2、设计一个尽可能的高效算法输出单链表的倒数第K个元素。 3、我们可用“破圈法”求解带权连通无向图的一棵最小代价生成树。所谓“破圈法”就是“任取一圈，去掉圈上权最大的边”，反复执行这一步骤，直到没有圈为止。请给出用“破圈法”求解给定的带权连通无向图的一棵最小代价生成树的详细算法，并用程序实现你所给出的算法。注：圈就是回路。 4、给定n个村庄之间的交通图，若村庄i和j之间有道路，则将顶点i和j用边连接，边上的Wij表示这条道路的长度，现在要从这n个村庄中选择一个村庄建一所医院，问这所医院应建在哪个村庄，才能使离医院最远的村庄到医院的路程最短?试设计一个解答上述问题的算法，并应用该算法解答如图所示的实例。（20分） 5、请设计一个算法，要求该算法把二叉树的叶子结点按从左到右的顺序连成一个单链表，表头指针为head。 二叉树按二叉链表方式存储，链接时用叶子结点的右指针域来存放单链表指针。分析你的算法的时、空复杂度。 6、编程实现单链表的就地逆置。 23．在数组 A[1..n]中有n个数据，试建立一个带有头结点的循环链表，头指针为h，要求链中数据从小到大排列，重复的数据在链中只保存一个. 7、#define maxsize 栈空间容量 void InOutS(int s[maxsize]) //s是元素为整数的栈，本算法进行入栈和退栈操作。 {int top=0; //top为栈顶指针，定义top=0时为栈空。 for(i=1; i<=n; i++) //n个整数序列作处理。 {scanf(“%d”,&x); //从键盘读入整数序列。 if(x!=-1) // 读入的整数不等于-1时入栈。 if(top==maxsize-1){printf(“栈满\\n”);exit(0);} else s[++top]=x; //x入栈。 else //读入的整数等于-1时退栈。 {if(top==0){printf(“栈空\\n”);exit(0);} else printf(“出栈元素是%d\\n”,s[top--])；} } }//算法结 8、设T是一棵满二叉树，编写一个将T的先序遍历序列转换为后序遍历序列的递归算法。 因篇幅问题不能全部显示，请点此查看更多更全内容