Глобальная переменная, используемая рекурсивной функцией

Question

Предположим, вам нужно реализовать класс Graph, содержащий некоторые алгоритмы, используя dfs (поиск в глубину).Например, это может быть проверка соединения, и класс Graph будет выглядеть так:

class Graph {
    void dfsConnected(int v) {
        visited[v] = true;
        //indexing over v's adjacencies and calling dfsConnected recursively
    }
    bool isConnected {
        //indexing over vertice list and calling dfsConnected
    }
}

Предположим, у нас есть несколько алгоритмов, использующих dfs в этом классе (каждый из них использует определенные dfs).Проблема в visited массиве:

• мы могли бы определить его как личное поле для каждого dfs вроде visitedConnectivity, visitedTopSorting, visitedBridges и т. Д. Так что у нас будет многочастные переменные в каждом экземпляре Graph.А что если у нас есть 3-4 таких «глобальных» переменных для каждого dfs?
• , мы можем передать visited в качестве аргумента dfs.В этом случае у нас будут накладные расходы при каждом вызове dfs.

Итак, каково самое простое и реально используемое решение этой проблемы?Конечно, это связано не только с алгоритмами графов, но мне было проще объяснить это в терминах DFS.

Answer 1

Чем больше ООП, на мой взгляд, является разделение поля visited для каждого класса DFS и заставить его запускать свою собственную DFS ....

Это помешает вам отслеживать 'чтоя выделил?с чем это связано?etc ... "

Ваша DFS будет гораздо более инкапсулирована и потребует меньше данных, затем добавит дополнительный параметр для каждой dfs, который вам придется поддерживать отдельно.

Производительностьпроблема здесь пренебрегается [в большинстве случаев] удобочитаемостью и удобством обслуживания , которых вы достигнете, инкапсулируя как можно больше данных в самом классе.

Answer 2

вы можете использовать статические переменные!

Answer 3

передать visited в качестве аргумента.Накладных расходов нет!

Обновление ОК. Я исправлен.Позвольте мне сказать, что издержки незначительны;) Тем не менее, я бы предпочел хранить указатель в стеке вокруг наличия поля / глобальной переменной, которая не имеет смысла вне функции, и потреблять память после того, как это делается каждый день.

Есливы действительно заботитесь, вы можете инкапсулировать DFS в объект, который имеет свое собственное поле visited и принимает граф в качестве аргумента.Но даже тогда это, вероятно, приводит к вызову функции с указателем объекта в стеке.