已知一个具有n个顶点的无向图G,用邻接矩阵存储。试写一个递归算法,判断图G中是否包含一条长度为k的简单路径。要求: (1)描述算法的基本设计思想(3分) (2)根据设计思想,采用类C语言描述算法,关键之处给出简要注释。(7分)
已知一个具有n个顶点的无向图G,用邻接矩阵存储。试写一个递归算法,判断图G中是否包含一条长度为k的简单路径。要求: (1)描述算法的基本设计思想(3分) (2)根据设计思想,采用类C语言描述算法,关键之处给出简要注释。(7分)
参考答案和解析
BCD
相关考题:
下面描述中,不正确的是( )。 A.递归法的关键是必须有一个递归终止的条件。B.递归算法要求语言具有反复自我调用子程序的能力。C.对于同一个问题,递推算法比递归算法的执行时间要长。D.递推算法总可以转换为一个递归算法。
设某有向无环图的顶点个数为n、弧数为e,那么用邻接表存储该图时,实现上述拓扑排序算法的函数TopSort的时间复杂度是(6)。若有向图采用邻接矩阵表示(例如,图4-1所示有向图的邻接矩阵如图4-3所示),且将函数TopSort中有关邻接表的操作修改为针对邻接矩阵的操作,那么对于有n个顶点、e条弧的有向无环图,实现上述拓扑排序算法的时问复杂度是(7)。
●设一个包含N 个顶点、E 条边的简单无向图采用邻接矩阵存储结构(矩阵元素 A[i][j]等于1/0 分别表示顶点i与顶点 j 之间有/无边),则该矩阵中的非零元素数目为 (60)。(60)A.NB.EC.2ED.N+E
阅读下列说明和C代码,回答问题1至问题2,将解答写在答题纸的对应栏内。【说明】一个无向连通图G点上的哈密尔顿(Hamiltion)回路是指从图G上的某个顶点出发,经过图上所有其他顶点一次且仅一次,最后回到该顶点的路径。哈密尔顿回路算法的基础如下:假设图G存在一个从顶点V0出发的哈密尔顿回路V1--V2--V3--...--Vn-1--V0。算法从顶点V0出发,访问该顶点的一个未被访问的邻接顶点V1,接着从顶点V1出发,访问V1一个未被访问的邻接顶点V2,..。;对顶点Vi,重复进行以下操作:访问Vi的一个未被访问的邻接接点Vi+1;若Vi的所有邻接顶点均已被访问,则返回到顶点Vi-1,考虑Vi-1的下一个未被访问的邻接顶点,仍记为Vi;直到找到一条哈密尔顿回路或者找不到哈密尔顿回路,算法结束。【C代码】下面是算法的C语言实现。(1)常量和变量说明n :图G中的顶点数c[][]:图G的邻接矩阵K:统计变量,当前已经访问的顶点数为k+1x[k]:第k个访问的顶点编号,从0开始Visited[x[k]]:第k个顶点的访问标志,0表示未访问,1表示已访问(2)C程序#include #include #define MAX 100voidHamilton(intn,int x[MAX,intc[MAX][MAX]){int;int visited[MAX];int k;/*初始化 x 数组和 visited 数组*/for (i=0:i=0){x[k]=x[k]+1;while(x[k]【问题1】(10分)根据题干说明。填充C代码中的空(1)~(5)。【问题2】(5分)根据题干说明和C代码,算法采用的设计策略为( ),该方法在遍历图的顶点时,采用的是( )方法(深度优先或广度优先)。
结构化开发方法中,(1)主要包含对数据结构和算法的设计。对算法设计时,其主要依据来自(2)描述算法时,(3)不是理想的表达方式。3、____A.流程图B.决策图C.程序设计语言代码D.伪代码
设一个包含N个顶点、E条边的简单无向图采用邻接矩阵存储结构(矩阵元素A[i][j]等于I/O分别表示顶点i与顶点j之间有/无边),则该矩阵中的非零元素数目为( )。A.NB.EC.2ED.N+E
阅读下列说明和?C?代码,回答问题?1?至问题?2,将解答写在答题纸的对应栏内。【说明】一个无向连通图?G?点上的哈密尔顿(Hamiltion)回路是指从图?G?上的某个顶点出发,经过图上所有其他顶点一次且仅一次,最后回到该顶点的路劲。一种求解无向图上哈密尔顿回路算法的基础私下如下:假设图?G?存在一个从顶点?V0?出发的哈密尔顿回路?V1——V2——V3——...——Vn-1——V0。算法从顶点?V0?出发,访问该顶点的一个未被访问的邻接顶点?V1,接着从顶点?V1?出发,访问?V1?一个未被访问的邻接顶点?V2,..。;对顶点?Vi,重复进行以下操作:访问?Vi?的一个未被访问的邻接接点?Vi+1;若?Vi?的所有邻接顶点均已被访问,则返回到顶点?Vi-1,考虑Vi-1?的下一个未被访问的邻接顶点,仍记为?Vi;知道找到一条哈密尔顿回路或者找不到哈密尔顿回路,算法结束。【C?代码】下面是算法的?C?语言实现。(1)常量和变量说明n :图?G?中的顶点数c[][]:图?G?的邻接矩阵K:统计变量,当期已经访问的定点数为?k+1x[k]:第?k?个访问的顶点编号,从?0?开始Visited[x[k]]:第?k?个顶点的访问标志,0?表示未访问,1?表示已访问⑵C?程序【问题?1】(10?分)根据题干说明。填充?C?代码中的空(1)~(5)。【问题?2】(5?分)根据题干说明和?C?代码,算法采用的设计策略为( ),该方法在遍历图的顶点时,采用的是(?)方法(深度优先或广度优先)。
填空题n个顶点e条边的图采用邻接矩阵存储,广度优先遍历算法的时间复杂度为();若采用邻接表存储,该算法的时间复杂度为()。