我们可用“破圈法”求解带权连通无向图的一棵最小代价生成树。所谓“破圈法”就是“任取一圈，去掉圈上

得：V1中的任何两个结点在图G中均不相邻，V2中的任何两个结点在图G中也均不相邻。 (1)请各举一个结点个数为5的二部图和非二部图的例子。 (2)请用C或Pascal编写一个函数BIPARTITE判断一个连通无向图G是否是二部图，并分析程序的时间复杂度。设G用二维数组A来表示，大小为n*n(n为结点个数)。请在程序中加必要的注释。若有必要可直接利用堆栈或队列操作。【浙江大学1998

大学2003五(10分)】

一条回路。(10分)【清华大学2001一(1 5分)】

且(v，w)∈E。写一个算法从给定的G求出G2，G和G2可分别用两个邻接表表示。【中国科学技术大学1998六(15分)】

无环图，每个操作数都用单个字母表示。试写出邻接表的类型定义；编写输出算术表达式的逆波兰表达式(后缀表达式)的算法(请写明算法的基本思路，并在算法的主要步骤上加注释)。【北京理工大学2002 8．2(7分)】

序存储在数组S中。请编写对以数组S存储的图G进行广度优先遍历的算法。另，请讨论若是无向非连通图，你的算法有何变化。【厦门大学2004七(15分)】【烟台大学2005五、3(15分)】

一种数据结构表示地图上各国相邻的关系。(6分) (2)描述涂色过程的算法。(不要求证明)(12分)【浙江大学2002八(18分)】

vi∈V，1≤i≤n)是否为该有向图的一个拓扑序列。若是，算法给出信息是1，否则，给出信息0。【北京航空航天大学2005三(10分)】

拓扑排序的算法。【中国海洋大学2007十(15分)】