c - 在给定邻接图和多次遍历的情况下优化方法以找到遍历最多的边

Question

我得到了一棵树的 N 个顶点及其对应的邻接图，表示为 N×N 数组 adjGraph[N][N]。例如，如果 (1,3) 是一条边，则 adjGraph[0][2] == 1。否则，对于不是边的 (i,j)，adjGraph[i][j] == 0。

我得到了以下形式的一系列输入:

1 5

表示从顶点 1 到顶点 5 已经遍历了一条路径。我想找到被遍历次数最多的边，以及它被遍历的次数。为此，我有另一个 N×N 数组 numPass[N][N]，我首先将其元素初始化为 0，然后每次我识别出包含一条边的路径时递增 1匹配它的索引。例如，如果路径 (2,4) 包含边 (2,3) 和 (3,4)，我会递增 numPass[1][2] 和 numPass[2][ 3] 每个 1 个。

据我了解，要解决的主要问题是输入仅提供起始顶点和结束顶点的信息，由我来确定哪些边连接这两个顶点。由于给定的图是一棵树，因此两个顶点之间的任何路径都是唯一的。因此，我假设给定任何输入路径的结束顶点的索引，我将能够递归回溯哪些边已连接。

以下是我考虑到这个想法而尝试实现的功能代码:

// find the (unique) path of edges from vertices x to y
// and increment edges crossed during such a path
void findPath(int x, int y, int N, int adjGraph[][N], int numPass[][N]) {
int temp;

// if the path is a single edge, case is trivial
if (adjGraph[x][y] == 1) {
    numPass[x][y] += 1;
    return;
}

// otherwise, find path by backtracking from y
backtrack: while (1) {
    temp = y-1;
    if (adjGraph[temp][y] == 1) {
        numPass[temp][y] += 1;
        break;
    }
}
if (adjGraph[x][temp] == 1) {
    numPass[x][temp] += 1;
    return;
} else {
    y = temp;
    goto backtrack;
}

但是，问题是虽然我的代码对于小输入工作正常，但对于大输入它会耗尽内存，因为我需要 128MB 的内存限制和 1 秒的时间限制。输入的范围最多为 222222 个顶点和 222222 个输入路径。

如何优化我的方法以满足如此大的输入？

Answer 1

1. 摆脱邻接矩阵(它使用 O(N^2) 空间)。请改用邻接表。

2. 使用更高效的算法。让我们让树生根。对于从 a 到 b 的路径，我们可以将 a 和 b 加 1，然后从它们的 lca 中减去 1(很容易看出，通过这种方式，a 被添加到这条路径上的边缘，并且只添加到它们)。

3. 处理完所有路径后，经过边的路径数只是子树中的总和。

如果我们使用高效算法来计算 lca，则此解决方案在 O(N + Q * log N) 中有效，其中 Q 是路径数。对于这个约束看起来已经足够好了(我们实际上可以通过使用更复杂和更有效的算法来找到 lca 来做得更好，但我认为这里没有必要)。

注:lca 表示最低共同祖先。