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

．请设计一个图的抽象数据类型(只需要用类PASCAL或类C/C++语言给出其主要功能函数或过程的接口说明不需要指定存储结构也不需要写出函数或过程的实现方法)利用抽象数据类型所提供的函数或过程编写图的宽度优先周游算法算法不应该涉及具体的存储结构也不允许不通过函数或过程而直接引用图结构的数据成员抽象数据类型和算法都应该加足够的注释【北京大学 二(分)】

设计算法以判断给定的无向图G中是否存在一条以V为起点的包含所有顶点的简单路径若存在返回TRUE否则返回FALSE(注本算法中可以调用以下几个函数FIRSTADJ(GV)返回图G中顶点V的第一个邻接点的号码若不存在则返回NEXTADJ(GVW)返回图G中顶点V的邻接点中处于W之后的邻接点的号码若不存在则返回NODES(G)返回图G中的顶点数)【合肥工业大学 五 (分)】

．已有邻接表表示的有向图请编程判断从第u顶点至第v顶点是否有简单路径若有则印出该路径上的顶点要求先描述图的存储结构并简述算法思路查找邻接点等图的运算要自己实现(尽量采用非递归算法否则满分１５分)【北京工业大学 六 (分)】

类似本题的另外叙述有

已知有向图和图中的两个结点u和v试编写算法求有向图中从u到v的所有简单路径【东南大学 四 (分)】

() 已知有向图和图中两个顶点U和V编写算法求有向图中从U到V的所有简单路径并以下图为例执行所编写的算法画出相应的搜索过程图【山东科技大学 六 (分)】

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