在給定鄰接圖和多次遍歷的情況下優化查找遍歷最多的邊的方法

Question

我給出了樹的N個頂點及其對應的鄰接圖，表示爲N乘N陣列adjGraph[N][N]。例如，如果（1,3）是邊緣，則adjGraph[0][2] == 1。否則，adjGraph[i][j] == 0（i，j）s不是邊。

我給出一系列輸入的形式：

1 5 

這表示，一個路徑已遍歷從頂點1開始到頂點5.我希望能夠找到這是travesed的邊緣大部分時間以及遍歷的次數。要做到這一點，我有另一個N乘N數組，numPass[N][N]，其元素I首先初始化爲0，然後每次識別包含與其索引匹配的邊的路徑時，將其加1。例如，如果路徑（2,4）包含邊（2,3）和（3,4），則I將每個增加numPass[1][2]和numPass[2][3]。

據我所知，要解決的主要問題是輸入只給出了起始頂點和結束頂點的信息，並且由我來確定哪些邊連接了這兩個邊。由於給定的圖是樹，所以兩個頂點之間的任何路徑都是唯一的。因此，我假定給定任何輸入路徑的結束頂點的索引，我將能夠遞歸地回溯哪些邊被連接。

以下是我試圖與這個想法在頭腦來實現功能代碼：

// 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的路徑，我們可以將1添加到a和b，並從它們的lca中減去1（很容易看出，這種方式將一個添加到此路徑上的邊緣並僅添加到它們）。

3. 處理所有路徑後，通過邊緣的路徑數量只是子樹中的總和。

如果我們用一個有效的算法計算LCA，這個解決方案工作於O(N + Q * log N)，其中Q是路徑的數量。對於這個約束來說它看起來不錯（我們實際上可以通過使用更復雜和更高效的算法來找到lca更好，但我認爲這不是必要的）。

注意：lca意味着最低的共同祖先。