DFS查找源点与终点相同路径：代码重复及错误路径修正问询

看起来你遇到的问题主要是重复路径输出和错误路径生成，这两个问题都源于原代码里的起点遍历逻辑和路径判断条件不够严谨。咱们一步步来修正：

原代码核心问题分析 #

• 多起点遍历导致重复：原DFS()函数循环遍历所有顶点调用DFSUtil，但我们只需要从源点0出发寻找路径，这就导致同一条路径被多次输出（比如从0跑一次，从1触发又跑一次0的路径）。
• 错误路径的产生：当从非0顶点（比如3）开始DFS时，会生成像0 3 1 0这种不符合要求的路径——因为原问题要求的是从0出发回到0的路径，而不是任意起点到0再延伸的路径。
• 回溯逻辑的局限性：原代码里只有当路径长度大于1时才回溯，这会导致某些情况下visited状态没有正确重置。

修正后的完整代码 #

#include <iostream>
#include <list>
#include <vector>
using namespace std;

// This class represents an undirected graph using adjacency list representation
class Graph
{
private:
    // No. of vertices
    int V;
    // Pointer to an array containing adjacency lists
    list<int> *adj;
    // A function used by DFS
    void DFSUtil(int v, int visited[], vector<int> &paths, int s, int d);
public:
    // Constructor
    Graph(int V);
    // function to add an edge to graph
    void addEdge(int v, int w);
    // Modified: DFS starting from a specific source vertex
    void DFS(int start);
};

Graph::Graph(int V)
{
    this->V = V;
    adj = new list<int>[V];
}

void Graph::addEdge(int v, int w)
{
    // Add w to v’s list (undirected graph)
    adj[v].push_back(w);
    adj[w].push_back(v);
}

Graph construct_graph()
{
    Graph g(4);
    g.addEdge(0, 1);
    g.addEdge(1, 3);
    g.addEdge(0, 2);
    return g;
}

void Graph::DFSUtil(int v, int visited[], vector<int> &paths, int s, int d)
{
    // Mark current node as visited and add to path
    visited[v]++;
    paths.push_back(v);

    // Simplified condition: if we've reached the destination and path length >1 (avoid single node)
    if(v == d && paths.size() > 1){
        cout << "Path: ";
        for(int i = 0; i < paths.size(); i++) {
            cout << paths[i] << " ";
        }
        cout << endl;
    }
    else
    {
        // Recur for all adjacent vertices
        list<int>::iterator i;
        for(i = adj[v].begin(); i != adj[v].end(); ++i)
        {
            // Allow nodes to be visited up to 2 times (supports paths like 0->1->3->1->0)
            if(visited[*i] < 2)
            {
                DFSUtil(*i, visited, paths, s, d);
            }
        }
    }
    // Always backtrack: reset visited count and remove node from path
    visited[v]--;
    paths.pop_back();
}

// Modified: Only start DFS from the specified source vertex
void Graph::DFS(int start)
{
    int *visited = new int[V];
    for(int i = 0; i < V; i++)
        visited[i] = 0;

    vector<int> paths;

    // Start DFS from the given source, target is the same as source
    DFSUtil(start, visited, paths, start, start);
}

int main()
{
    Graph g = construct_graph();
    // Start DFS from source vertex 0
    g.DFS(0);
    cout << endl;
    return 0;
}

关键修改说明 #

1. 固定起点的DFS函数：
   移除了原代码中遍历所有顶点的逻辑，改为接受start参数的DFS函数，只从指定源点（这里是0）启动一次DFS，彻底避免重复路径。

2. 简化路径输出条件：
   去掉了visited[s] == 2的冗余判断，只要当前节点是终点且路径长度大于1（避免输出单个0），就输出路径，逻辑更清晰。

3. 完善回溯逻辑：
   移除了paths.size() > 1的限制，确保每次递归返回时都正确重置visited计数并弹出路径节点，避免状态残留导致的错误。

运行结果 #

修正后的代码会输出符合期望的结果：

Path: 0 1 0
Path: 0 1 3 1 0
Path: 0 2 0

内容的提问来源于stack exchange，提问作者shubham