DFS算法查找所有路徑詳解

算法介紹

深度優(yōu)先搜索（Depth-First Search，DFS）是一種圖遍歷算法，它從起始節(jié)點開始，沿著一條路徑盡可能深入，直到達(dá)到最深的節(jié)點，然后回溯到前一節(jié)點，繼續(xù)探索下一條路徑。DFS通常使用遞歸或棧（非遞歸）來實現(xiàn)。

以下是DFS算法的基本步驟：

• 選擇起始節(jié)點： 從圖中選擇一個起始節(jié)點作為當(dāng)前節(jié)點；
• 標(biāo)記節(jié)點： 標(biāo)記當(dāng)前節(jié)點為已訪問，以防止重復(fù)訪問；
• 探索鄰居節(jié)點： 對于當(dāng)前節(jié)點的未訪問鄰居節(jié)點，選擇一個鄰居節(jié)點作為新的當(dāng)前節(jié)點，然后重復(fù)步驟2和步驟3；
• 回溯： 如果當(dāng)前節(jié)點沒有未訪問的鄰居節(jié)點，回溯到上一節(jié)點，重復(fù)步驟3；
• 重復(fù)過程： 重復(fù)步驟3和步驟4，直到所有節(jié)點都被訪問。

遞歸實現(xiàn)的偽代碼

function DFS(node):if node is not visited:mark node as visitedfor each neighbor of node:DFS(neighbor)

非遞歸實現(xiàn)的偽代碼

DFS的非遞歸實現(xiàn)通常使用棧來模擬遞歸調(diào)用的過程，具體步驟如下：

• 創(chuàng)建一個空棧，并將起始節(jié)點壓入棧中；
• 進(jìn)入循環(huán)，直到棧為空；
• 彈出棧頂節(jié)點作為當(dāng)前節(jié)點；
• 如果當(dāng)前節(jié)點未訪問，標(biāo)記為已訪問；
• 遍歷當(dāng)前節(jié)點的鄰居節(jié)點，將未訪問的鄰居節(jié)點壓入棧中；
• 重復(fù)步驟3到步驟5，直到棧為空為止。

注意：在處理連通圖時可能導(dǎo)致棧溢出，因此在實際應(yīng)用中可能需要注意棧深度的問題。
偽代碼如下：

function DFS_non_recursive(start):stack = empty stackpush start onto stackwhile stack is not empty:current = pop from stackif current is not visited:mark current as visitedfor each neighbor of current:push neighbor onto stack

具體算法實現(xiàn)

由于可能存在非常多的路徑，我們設(shè)置一個maxLength，表示限制經(jīng)過的節(jié)點個數(shù)。

void Graph::DFS(int current, int end, std::unordered_set<int>& visited, std::vector<int>& path, int maxLength)
{static int currentLength = 0;static int i = 1;visited.insert(current);path.push_back(current);if (path.size() <= maxLength) {if (current == end){// 生成路徑for (int node : path) {std::cout<<node<<' ';}std::cout<<"路徑總長度為："<<currentLength<<std::endl;}else{for (int neighbor = 0; neighbor < V; ++neighbor){if (adjMatrix[current][neighbor] != INF && visited.find(neighbor) == visited.end()) {int edgeWeight = adjMatrixLength[current][neighbor];currentLength += edgeWeight;DFS(neighbor, end, visited, path, maxLength);currentLength -= edgeWeight; // 回溯時減去當(dāng)前邊的長度}}}}visited.erase(current);path.pop_back();
}