Блог

Предположим, у меня есть конкретный неориентированный граф: «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;
}
 

Спасибо.

Нет логической разницы между вариантом 1 и вариантом 3, но вариант 3 является оптимизированной версией, поскольку он позволит избежать нежелательных рекурсивных вызовов, которые могут быть очень сложными, если задействованы большие тестовые примеры. Это может потреблять больше памяти без необходимости.

Вариант 2 логически отличается от двух других вариантов, поскольку он позволяет посещать узел несколько раз во время DFS.

Количество посещений узла в варианте 2 будет зависеть от матрицы смежности / списка графа.

Использование ветвления команд в вариантах 1 и 3 не будет иметь никакого эффекта, поскольку мы уже проверяем, посещался ли узел ранее, но это, несомненно, заставит вариант 2 работать правильно (согласно определению DFS: посещайте каждый узел почти один раз.)