DFS算法查找所有路径详解

DFS算法查找所有路径详解

算法介绍

深度优先搜索（Depth-First Search，DFS）是一种图遍历算法，它从起始节点开始，沿着一条路径尽可能深入，直到达到最深的节点，然后回溯到前一节点，继续探索下一条路径。DFS通常使用递归或栈（非递归）来实现。

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

• 选择起始节点： 从图中选择一个起始节点作为当前节点；
• 标记节点： 标记当前节点为已访问，以防止重复访问；
• 探索邻居节点： 对于当前节点的未访问邻居节点，选择一个邻居节点作为新的当前节点，然后重复步骤2和步骤3；
• 回溯： 如果当前节点没有未访问的邻居节点，回溯到上一节点，重复步骤3；
• 重复过程： 重复步骤3和步骤4，直到所有节点都被访问。

递归实现的伪代码

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

非递归实现的伪代码

DFS的非递归实现通常使用栈来模拟递归调用的过程，具体步骤如下：

• 创建一个空栈，并将起始节点压入栈中；
• 进入循环，直到栈为空；
• 弹出栈顶节点作为当前节点；
• 如果当前节点未访问，标记为已访问；
• 遍历当前节点的邻居节点，将未访问的邻居节点压入栈中；
• 重复步骤3到步骤5，直到栈为空为止。

注意：在处理连通图时可能导致栈溢出，因此在实际应用中可能需要注意栈深度的问题。
伪代码如下：

function DFS_non_recursive(start):
    stack = empty stack
    push start onto stack

    while stack is not empty:
        current = pop from stack
        if current is not visited:
            mark current as visited
            for each neighbor of current:
                push neighbor onto stack

具体算法实现

由于可能存在非常多的路径，我们设置一个maxLength，表示限制经过的节点个数。

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; // 回溯时减去当前边的长度
                }
            }
        }
    }

    visited.erase(current);
    path.pop_back();
}