-1

我正在解决这个基于 IDDFS 的问题，我正在使用一个基于深度执行递归 DFS 的实用程序函数。我已经为其编写了完美运行的python代码，但我被要求将其转换为CPP，其中出现了问题。

让我借助我正在使用的示例图进行解释，其中有 7 个节点标记为从 0 到 6。它们的邻接列表如下：

0: [4],
1: [4, 5],
2: [3, 5],
3: [2, 6],
4: [0, 1, 5],
5: [1, 2, 4],
6: [3]

我试图找到深度为 2 的 4 到 2 之间的 DFS，其答案应该是 [4,5,2]。

现在，我将附加工作 python 代码及其输出：

def dfs_util(path,target,depth):
    # Returns path if it exists, None otherwise
    curr_node = path[-1]
    if curr_node == target:
        return path
    if depth<=0:
        return None
    for child in adj_list[curr_node]:
        print(child)
        new_path = list(path)
        new_path.append(child)
        result = dfs_util(new_path,target,depth-1)
        # Remove this print statement gurllllll
        print(new_path, result)
        if result is not None:
            return result
    return None

我在那里添加了额外的打印语句来帮助调试和理解流程。这为命令 dfs_util([4],2,2) 提供的输出是：

0
4
[4, 0, 4] None
[4, 0] None
1
4
[4, 1, 4] None
5
[4, 1, 5] None
[4, 1] None
5
1
[4, 5, 1] None
2
[4, 5, 2] [4, 5, 2]
[4, 5] [4, 5, 2]
[4, 5, 2]

正如我们所看到的，这将返回正确的输出。

当我尝试将其转换为 CPP 时，我编写了以下函数：

vector<int> dfs_util(vector<int> path, int target, vector<vector<int> > adj_list, int depth){
    int curr_node = path.back();
    if(curr_node == target)
        return path;
    if(depth<=0){
        vector<int> tmp;
        tmp.push_back(NULL);
        return tmp;
    }
    for(auto child : adj_list[curr_node]){
        cout<<child<<endl;
        vector<int> new_path = path;
        new_path.push_back(child);
        vector<int> result = dfs_util(new_path, target, adj_list, --depth);
        cout<<"[";
        for(auto i : new_path)
            cout<<i<<" ";
        cout<<"]\t";
        cout<<"res=";
        for(auto i : result)
            cout<<i<<" ";
        cout<<"\n";
        if(result.back()!=NULL)
            return result;
    }
    vector<int> tmp;
    tmp.push_back(NULL);
    return tmp;        
}

使用相同的输入参数，理想情况下它应该返回与上面提到的 python 代码相同的输出。但相反，它会打印以下内容：

0
4
[4 0 4 ]        res=0 
[4 0 ]  res=0 
1
[4 1 ]  res=0 
5
[4 5 ]  res=0

在写出逻辑的同时，我开始明白，在进入调用 dfs_util([4,1],2,1) 的递归循环后，它不会进入进一步提到的 for 循环，因此不会探索连接到的边节点 1。

我觉得它在技术上应该可行（至少当我尝试逐行解决并在纸上解决时）。

4

0 回答 0