1

Здравствуйте! Задача состоит в следующем:

Найти такую вершину заданного графа, которая принадлежит каждому пути между двумя выделенными (различными) вершинами и отлична от каждой из них.

Не совсем разобрался с методом решения. Представляется наиболее удобным использование обхода графа в глубину. Граф храню в виде списка смежности. Думаю, нужно делать что-то в таком духе: 1) найти первый путь между двумя заданными вершинами, положить путь в массив 2) найти еще один путь, сравнить с тем, что в массиве, вершины второго пути, которых нет в массиве, убрать оттуда. Так делать до тех пор пока массив не опустел (значит, нет искомой вершины) или не нашли все пути (искомые вершины останутся в массиве).

Остается вопрос: как найти все эти различные пути? Буду очень признателен любым подсказкам.

Также есть другая идея, но, как мне кажется, не совсем хорошая. Последовательно удалять каждую вершину графа (кроме двух заданных) и проверять тем же обходом в глубину, есть ли путь между двумя этими вершинами. (Т.е. не оказались ли они в двух разных компонентах связности). Если оказались, то удаленная вершина искомая.

P.S. Найти все пути между двумя вершинами графа не думаю, что подходит мне. В моем графе могут (и скорее всего будут) присутствовать циклы.

1
  • Я бы рекомендовал посмотреть этот алгоритм: e-maxx.ru/algo/cutpoints
    – Harry
    Commented 6 мая 2017 в 15:07

1 ответ 1

0

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

Модификация этого алгоритма для решения задачи состоит в том, чтобы при запуске его от начальной вершины, при нахождении в графе конечной вершины, он останавливался. Таким образом, если конечная вершина найдется, то путь существует. Иначе пути между двумя заданными вершинами нет. При первом запуске поиска сохраним найденный путь.

Для нахождения вершины, принадлежащей каждому пути между двумя заданными, тоже можно воспользоваться этим алгоритмом.

При удалении такой вершины из графа, две данные вершины станут недостижимы, т.е. между ними перестанет существовать путь. Следовательно, для обнаружения искомой вершины, достаточно последовательно удалять каждую вершину сохраненного пути (кроме данных начальной и конечной). Если после удаления очередной вершины, две данные станут недостижимыми, то удаленная вершина и есть искомая.

В нашем случае в качестве удаления будем делать вершину “посещенной”, чтобы из нее не выполнялся обход графа в глубину.

int search() {
int v; //текущая вершина
while(empty(stack)!=1) {
    pop(&v, &stack);
    if (v != a && v != b) {
        for (int j = 0; j < n; j++)
            M[j] = 0;
        M[v] = 1;
        if(dfs(a)==0) //обход графа в глубину, возвращает 0 если нет пути между a, b
            return v;
    }
}
return -1;}

Здесь массив M содержит метки вершин ("посещенная"/"не посещенная"), n - количество вершин графа.

Ваш ответ

Нажимая «Отправить ответ», вы соглашаетесь с условиями пользования и подтверждаете, что прочитали политику конфиденциальности.

Всё ещё ищете ответ? Посмотрите другие вопросы с метками или задайте свой вопрос.