Хороший способ пометить узлы графа как посещенные, когда вы не можете редактировать структуру узла?

Question

Время от времени я сталкиваюсь с проблемой, подобной следующей.(Это написано на C, но вы можете представить, что эта проблема может возникнуть на любом языке):

struct node {
    int value;
    struct node *left;
    struct node *right;
    struct node *up;
    struct node *down;
}

void visit(struct node *n);

void DFS_traverse(struct node *source) {
    if (source == NULL) return;

    visit(source);
    markAsVisited(source);

    if (isNotVisited(source->left)) {
        DFS_traverse(source->left);
    }

    //etc...
}

В этом примере кода нам нужно иметь возможность markAsVisited и проверить ifNotVisited.Обычный способ сделать это состоит в том, чтобы изменить структуру, чтобы иметь дополнительный член:

struct node {
    int value;
    struct node *left;
    struct node *right;
    struct node *up;
    struct node *down;
    int visited;
}

и соответственно перевернуть член visited.

Это решение, однако, не совсемвозможно, если вы не можете (или не должны) редактировать структуру, которую используете (скажем, в чужом коде, или вам по какой-то причине требуется, чтобы эта структура имела определенный размер).

Вот список других опций, которые я смог придумать:

• Создание структуры оболочки, такой как

struct wrapped_node {
    struct node *n;
    int visited;
}

• Хранить отдельный списокиз всех указателей, с которыми вы столкнулись (и, если хотите, вы можете использовать какое-то двоичное дерево поиска или хэш-таблицу)

• Если вы знаете, что value внутриузел может принимать только определенные значения (например, только положительные числа), вы можете сжать посещаемую информацию в один из его битов, а затем отменить это после того, как закончите поиск.

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

Так какой же метод вы предпочитаете для решения этой проблемы?