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

．试编写求无向图G的连通分量的算法要求输出每一连通分量的顶点值(设图G已用邻接表存储)【南京航空航天大学 十一(分)】

类似本题的另外叙述有

()写出求无向图G中各连通分量的顶点集的算法COMF(G)可调用的运算是FIRST_ADJ(GV)求顶点V的第一邻接点NEXTADJ(GVW)求顶点V关于W的下一个邻接点【北京科技大学 八(分)】

()编程求解无向图G的所有连通分量 【南京航空航天大学 七】

．设无向图G已用邻接表结构存储顶点表为GL[n] (n为图中顶点数)试用广度优先搜索方法写出求图G中各连通分量的C语言描述算法BFSCOM(GL)(注算法中可调用队列操作的基本算法)【北京科技大学 七 (分)】

．设一个连通无向图G=(VE)采用邻接表方式存储V=(…n}一维数组HAED[…n]用来存放每个单链表的头指针单链表中节点结构为(VERLINK)其中LINK是链接字段VER字段表示顶点内容一维数组MARK[…n]用于对相应顶点加标号MARK[i]=表示顶点i未被访问到 MARK[i]=表示顶点i已经被访问过试写出对上述图G进行广度(或宽度)优先遍历(或访问)的非递归算法BFS(HEADnsMARKMARK)其中S为任一遍历起始顶点【吉林大学 二 (分)】

．写出图的深度优先搜索DFS算法的非递归算法【北京邮电大学 十 (分)】

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