假定图G=（V E)是有向图 V={1 2 … N} N≥1 G以邻接矩阵方式存储 G的邻接矩阵为A 即A是一个二维数组
矩阵,数组,假定
已帮助 人
假定图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(n×n)。
请帮忙给出正确答案和分析，谢谢！
-
正确答案：采用深度优先遍历算法在执行DFS(v)时若在退出DFS(v)前碰到某顶点u其邻接点是已经访问的顶点v则说明v的子孙u有到v的回边即说明有环；否则无环。
采用深度优先遍历算法,在执行DFS(v)时,若在退出DFS(v)前,碰到某顶点u,其邻接点是已经访问的顶点v,则说明v的子孙u有到v的回边,即说明有环；否则,无环。