DAG图最长路的递推函数d(i)表示从某个顶点i出发的最长路长度 。
举一反三
- DAG图最长路的反推关系是 L(i) = 1 + max {L(j) : (i, j) 为边}
- 以下关于图的说法正确的是()。I图G的生成树是该图的一个极小连通子图Ⅱ生成树中最长路径的起点和终点的度均为1Ⅲ对任意一个图，从某个顶点出发进行一次深度优先或广度优先遍历，可访问图的所有顶点 A: I、Ⅱ B: Ⅱ、Ⅲ C: I、Ⅱ D: 仅有Ⅱ
- 已知一个图的邻接矩阵表示，删除所有从第i个顶点出发的弧方法是（）。
- 已知一个有向图用邻接矩阵表示,删除所有从第i个顶点出发的边的方法是( )。
- 对于序列X和Y，用D[i,j]表示X[1..i]和Y[1..j]的最长公共子序列的长度，当X[i]=Y[j]时，D[i,j]=D[i-1,j-1]+1，递推式中“+1”表示什么（ ）？[/i] A: 最长公共子序列中最后的元素，为相同的X[i]（Y[j]） B: X的最后一个元素 C: Y的最后一个元素 D: 无实际含义