数据结构考研分类复习真题 第七章 图[60]

．二部图(bipartite graph) G=(VE)是一个能将其结点集V分为两不相交子集V 和V=VV的无向图使得V中的任何两个结点在图G中均不相邻V中的任何结点在图G中也均不相邻

()．请各举一个结点个数为的二部图和非二部图的例子

()．请用C或PASCAL编写一个函数BIPARTITE判断一个连通无向图G是否是二部图并分析程序的时间复杂度设G用二维数组A来表示大小为n*n(n为结点个数)请在程序中加必要的注释若有必要可直接利用堆栈或队列操作【浙江大学 八 (分)】

．我们可用破圈法求解带权连通无向图的一棵最小代价生成树所谓破圈法就是任取一圈去掉圈上权最大的边反复执行这一步骤直到没有圈为止请给出用破圈法求解给定的带权连通无向图的一棵最小代价生成树的详细算法并用程序实现你所给出的算法注圈就是回路

【复旦大学 六 (分)】

设图用邻接表表示写出求从指定顶点到其余各顶点的最短路径的Dijkstra 算法

要求()．对所用的辅助数据结构邻接表结构给以必要的说明(分)

()．写出算法描述(C类Pascal类C均可)(分)【南京理工大学 四 (分)】

类似本题的另外叙述有

()写出求从某个源点到其余各顶点最短路径的Dijkstra算法要求说明主要的数据结构及其作用最后针对所给有向图利用该算法求V到各顶点的最短距离和路线即填写下表【山东师范大学 六 (分)】

[] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] []