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

．假设以邻接矩阵作为图的存储结构编写算法判别在给定的有向图中是否存在一个简单有向回路若存在则以顶点序列的方式输出该回路(找到一条即可)(注图中不存在顶点到自己的弧)【清华大学 六 (分)】

类似本题的另外叙述有

()假定G=(VE)是有向图V={…n }n>=G以邻接矩阵方式存储G的邻接矩阵为A即A是一个二维数组如果i到 j有边则A[ ij]=否则A[ ij]=请给出一个算法该算法能判断G是否是非循环图(即G中是否存在回路)要求算法的时间复杂性为O( n*n )【吉林大学 五 (分)】

．假设一个有向图G已经以十字链表形式存储在内存中试写一个判断该有向图中是否有环路(回路)的算法【东北大学 四 (分)】

．用邻接多重表存储结构编写FIRSTADJ(GV)函数函数返回值为第一个邻接点若V没有邻接点返回零【北京工商大学 四 (分)】

．在有向图G中如果r到G中的每个结点都有路径可达则称结点r为G的根结点编写一个算法完成下列功能

()．建立有向图G的邻接表存储结构

()．判断有向图G是否有根若有则打印出所有根结点的值【东北大学 五 (分)】

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