2. 考研
  3. 假定图G=(V，E)是有向图，V={1，2，…，N}，，N≥1，G以邻接矩阵方式存储，G的邻接矩阵为A，即A是一个二维数组。如果i到j有边，则A[i，j]=1，否则A[i，j]=0。请给出一个算法思想，该算法能判断G是否是非循环图(即G中是否存在回路)，要

假定图G=(V，E)是有向图，V={1，2，…，N}，，N≥1，G以邻接矩阵方式存储，G的邻接矩阵为A，即A是一个二维数组。如果i到j有边，则A[i，j]=1，否则A[i，j]=0。请给出一个算法思想，该算法能判断G是否是非循环图(即G中是否存在回路)，要

admin2023-02-06  43
问题 假定图G=(V，E)是有向图，V={1，2，…，N}，，N≥1，G以邻接矩阵方式存储，G的邻接矩阵为A，即A是一个二维数组。如果i到j有边，则A[i，j]=1，否则A[i，j]=0。请给出一个算法思想，该算法能判断G是否是非循环图(即G中是否存在回路)，要求算法的时间复杂性为O(n2)。
选项
答案此题考查的知识点是图的遍历。采用深度优先遍历算法，在执行DFS(v)时，若在退出DFS(v)前碰到某顶点u，其邻接点是已经访问的顶点v，则说明v的子孙u有到v的回边，即说明有环；否则，无环。
解析
转载请注明原文地址:https://kaotiyun.com/show/MIwD777K
本试题收录于： 计算机408题库学硕统考专业分类
0

计算机408

学硕统考专业

相关试题推荐
随机试题
最新回复(0)