dfs 实现的各种变体

Question

假设我有具体的无向图： “1----2----3----4”。

算法的下一个实现有什么区别"dfs":

#include <iostream>
#include <vector>
using namespace std;
const int maxSize=4000;
vector<int> graph[maxSize];
bool visited0[maxSize];
void dfs0(int firstPoint, int previousPoint)
{
    visited0[firstPoint]=true;
    for(int secondPoint : graph[firstPoint])
    {
        if(visited0[secondPoint]==false)
        {
            dfs0(secondPoint, firstPoint);
        }
    }
    return;
}
bool visited1[maxSize];
void dfs1(int firstPoint, int previousPoint)
{
    visited1[maxSize]=true;
    for(int secondPoint : graph[firstPoint])
    {
        if(secondPoint==previousPoint)
        {
            continue;
        }
        dfs1(secondPoint, firstPoint);
    }
    return;
}
bool visited2[maxSize];
void dfs2(int firstPoint, int previousPoint)
{
    visited2[firstPoint]=true;
    for(int secondPoint : graph[firstPoint])
    {
        if(secondPoint==previousPoint)
        {
            continue;
        }
        if(visited2[secondPoint]==false)
        {
            dfs2(secondPoint, firstPoint);
        }
    }
    return;
}
int main()
{
    dfs0(1, -1);
    dfs1(1, -1);
    dfs2(1, -1);
    return 0;
}

如果更准确地说，我想知道什么时候（在什么情况下）我应该使用命令分支：

if(visited0[secondPoint]==false)
{
    dfs0(secondPoint, firstPoint);        (Variation #1)
}

和

if(secondPoint==previousPoint)
{
    continue;
}
dfs1(secondPoint, firstPoint);        (Variation #2)

和

if(secondPoint==previousPoint)
{
    continue;
}
if(visited2[secondPoint]==false)
{
    dfs2(secondPoint, firstPoint);        (Variation #3)
}

请描述每个变体（变体 #1、变体 #2、变体 #3）。

在什么情况下我必须使用变体#1？

在什么情况下我必须使用变体#2？

在什么情况下我必须使用变体#3？

下一个命令分支（位于下方）的出现将如何影响算法的各种实现"dfs" (dfs0(1, -1) , dfs1(1, -1), dfs2(1, -1)):

Use the parameter "visited" in dependence of the version of the algorithm "dfs": either "visited0", or "visited1", or "visited2".

How is it important to use this command-branching at the beginning of the various implementations of the algorithm "dfs" (dfs0(1, -1), dfs1(1, -1), dfs2(1, -1))?

if(visited0[firstPoint]==true)
{
    return;
}

谢谢。

Answer 1

变体 1 和 变体 3 在逻辑上没有区别，但是 变体 3是优化版本，因为它将避免不需要的递归调用，如果涉及 large 测试用例，这可能是一个很好的选择。这可能会不必要地消耗更多内存。

变体 2 在逻辑上不同于其他两个变体，因为它允许在 DFS 期间多次访问一个节点。

在变体 2 中访问节点的次数将取决于图的邻接 matrix/list。

使用变体1和变体3中的命令分支，将没有效果，因为我们已经在检查之前是否访问过该节点，但它肯定会使 Variation 2 正常工作（根据 DFS 的定义：几乎访问每个节点一次。）

dfs 实现的各种变体

Various variations of the implementation of dfs

c++

algorithm

graph

depth-first-search