第七次作業第2題 獨立路徑數計算（DFS）

為什么是DFS？

已經對DFS有良好理解的同學可以跳過這一部分。

首先回顧一下生成全排列的算法：

int visit[n], path[n];

void dfs(int level) {
    if (level == n) {             // 有明確的終止條件
        print(path);
        return ;
    }
    for (int i = 0; i < n; i++) { // 搜索所有可行選擇
        if (!visit[i]) {          // 不會做出重復的選擇
            visit[i] = 1;
            path[level] = i;      // 進行記錄
            dfs(level + 1);
            visit[i] = 0;
        }
    }
}

int main() { dfs(0); }

借助全排列的過程，分析一下DFS的要素：

• 每次都面臨多種選擇，能夠通過搜索找到所有可行的選擇；
  • 每次都遍歷visit數組，從小到大尋找還未被使用過的數。
• 不會做出重復的選擇；
  • 每選擇一個數，就將visit數組中的對應元素標為1；返回時則清空該標記。
• 能夠記錄曾經做出的選擇，且該記錄隨著遞歸的調用而推進、隨著遞歸的返回而回退；
  • path數組記錄了當前level之前選擇的數，并將當前的選擇記錄在第level位。
• 有明確的終止條件；
  • 每當填充到第n位時，一次排列生成，輸出結果，并返回。

對應到本題的計算路徑：

• 每個點都和多個點鄰接；通過按邊的序號從小到大搜索鄰接的結點，恰好能按照路徑邊字典序找到所有路徑。
• 每經過一個結點，就用visit做標記，使得之后不能再次經過；當從該結點搜索完畢返回時，又清空該標記，使得之后從別的路徑又可以再次經過。
• 用path數組記錄每個經過的邊的編號，恰好就能保存路徑。
• 每當搜索到終點時，找到一條路徑，輸出該路徑，并返回。

總結一下，DFS的功能就是不重不漏地找到一個問題的所有可行解，這可能需要在熟練掌握遞歸的基礎上有一定感性的認識。本次的作業題，其實就是對很多問題的高度抽象，即用暴力搜索的手段來求得一個難題的解。

本題存圖的數據結構

鄰接矩陣 or 鏈式邊表？

• 鄰接矩陣的含義是，用一個二維數組map[n][n]表示任意兩點間的邊關系。顯然，在這種情況下，任意兩點間只能存儲至多一條邊的信息；本題提到了，兩個頂點之間有多條邊時，邊的序號會不同；因此，本題不能使用鄰接矩陣。
  • 鄰接矩陣的優點：能夠方便地按照點的序號有序地訪問；能快速地查詢任意兩點間的邊信息，查詢效率高；只用數組，代碼復雜度低。
  • 鄰接矩陣的缺點：遍歷時要對圖中所有結點的鄰接性進行判斷，遍歷效率低；并且需要\(n^2\)的空間復雜度來存儲。
• 鏈式邊表的含義是，為每個結點建立一個鏈表，其中存儲與該結點鄰接的所有邊。顯然，這種方法對兩點間邊的數量沒有限制，適用于本題。
  • 鏈式邊表的優點：每次訪問都只訪問到鄰接的邊，遍歷效率高；占用的內存大小只和邊數有關，空間復雜度低。
  • 鏈式邊表的缺點：每個點鄰接的邊的順序需要手動維護；查詢任意兩點間的邊信息需要遍歷該點所有的鄰接邊，查詢效率低；需要使用鏈表的數據結構，代碼復雜度高。

靜態數組 or malloc+指針？

使用數組和指針存儲的實質都是一樣的，都是從索引到數據的映射。區別在于：數組是從下標到數據的映射，指針是從地址到數據的映射。

在本題中，題目用標號描述結點和邊，恰好就是整數到數據的映射；并且給定了標號的范圍，因此使用靜態數組是最優解。

建圖注意事項&小技巧

用邊表存圖時，我們往往將一條無向邊轉化為兩條有向邊處理。對于每一條有向邊，可以只存儲這條邊指向的終點。

struct Edge{
    int to;  // 終點的標號
    // 其他屬于邊的信息，如長度、路費等
    int next; // 鏈表中下一條邊的標號，需初始化為-1
}edges[M * 2];

struct Node{
    int first; // 邊鏈表中第一個結點的邊標號，初始化為-1
    // 其他屬于點的信息，如坐標、溫度、人口數量等
}nodes[N];

但本題給每條邊都標好了號，而我們又要用數組存圖，沒法讓兩條有向邊共用一個下標，這該怎么辦呢？

一種通用的思路，是采用兩套標號系統。一套系統用來表示題目中的標號，只用該標號排序和輸出；另一套系統用于我們的鏈式邊表。但這樣就喪失了用數組存儲的意義，直接用malloc+指針反而更為方便。

對于本題來說，一種巧妙的做法，是將題目給定的邊號乘上2，再分別+0和+1后，作為兩條有向邊的新編號；排序時原先的大小關系沒有改變，輸出時只要將新編號除以2就能得到原編號，可謂是一舉兩得。

int main() {
    ...
    // 讀入信息：邊標號為e，兩點標號為v1 v2
    // 轉化為兩條有向邊
    buildEdge(v1, v2, e*2+0); // 從v1到v2，邊標號轉化為e*2+0
    buildEdge(v2, v1, e*2+1); // 從v2到v1，邊標號轉化為e*2+1
}

下面的關鍵就是書寫buildEdge(from, to, e)函數了，它的含義是增加一條從from到to的標號為e的邊。由于是鏈式邊表存圖，該函數就是需要將邊e插入到from結點存儲的邊鏈表中。又由于題目要求按字典序輸出所有路徑，我們需要保證每個鏈表中邊的標號都從小到大排列。

為了保證鏈表元素的有序性，有兩種做法：一是每次都找到正確的位置插入；二是先將所有邊按標號排序，再依次插入到每個鏈表頭部。由于后者可以借助qsort降低排序和插入的代碼復雜度，且時間復雜度也十分優秀，這里用后者為例。

struct Tmp{
    int e, vi, vj;
}tmpData[1005];

int main() {
    ...
    for (int i = 0; i < e; ++i) 
    	scanf("%d%d%d", &tmpData[i].e, &tmpData[i].vi, &tmpData[i].vj);
    qsort(tmpData, e, sizeof Tmp, cmp); //將讀入的所有邊按e值從大到小排列
    for (int i = 0; i < e; ++i) {
        buildEdge(tmpData[i].vi, tmpData[i].vj, tmpData[i].e * 2 + 0);
        buildEdge(tmpData[i].vj, tmpData[i].vi, tmpData[i].e * 2 + 1);
    }
    ...
}

void buildEdge(int from, int to, int e) {
    edges[e].to = to;
    // 直接插入到鏈表頭部
    edges[e].next = nodes[from].first;
    nodes[from].first = e;
}

到這里，本題建圖的部分就大功告成；接下來就是參考全排列的算法依葫蘆畫瓢，書寫DFS。

用DFS進行搜索

顯然，dfs函數需要至少兩個參數：一是當前搜索到的結點，二是當前的深度（用來記錄路徑）。

int path[N], visit[N];
void dfs(int now, int depth);
int main() {
    ...
    visit[0] = 1;
    dfs(0, 0);
    ...
}

• 終止條件：
  • 當前搜索到的結點now為終點時，表示找到一條路徑；用for (int i = 0; i < depth; ++i) printf("...", path[i]);輸出路徑記錄數組中記錄的路徑（標號要除以二再輸出），并返回。
• 遍歷選擇：
  • 用for(int e = nodes[now].first; e != -1; e = edges[e].next)遍歷當前now結點鄰接的所有邊，并用int to = edges[e].to訪問該邊到達的結點。
• 保證不重：
  • 先判斷visit[to]，只有當未訪問過時才訪問to。
• 記錄路徑
  • 如果未訪問過，則立即將visit[to]置為1，同時記錄路徑path[depth] = e；
  • 進行遞歸調用dfs(to, depth+1);；
  • 返回后，將visit[to]恢復為0，繼續搜索下一個可行的鄰接結點。

參考遞歸實現的全排列，即可輕松完成上面的算法。相信你已經能夠掌握DFS的奧妙了。