подсчитать все пары вершин с ограничениями в неориентированном графе

Question

Я пытаюсь решить следующую головоломку с алгоритмом c:

, учитывая график с N вершинами и N ребрами. Я должен подсчитать все пары вершин (A, B) со следующими свойствами: A> B и существует хотя бы один путь из всех вершин, помеченных номерами между A и B ...

. Пример (1,5) является допустимой парой вершин, если существует следующий путь: (1 , 2,3,4,5), но было бы хорошо, даже если бы существовало следующее (1,5,2,3,4) или (1,3,4,3,2,3,5) ... I меня не интересует длина пути или его порядок, просто нужно включить все вершины с метками> = A и <= B. Я пробовал с модифицированными bfs и dfs, но безуспешно. </p>

может кто-нибудь помочь?

дать подсказку?

спасибо

Answer 1

Удалить все ребра, соединяющие два узла с непоследовательными номерами. (например, ребро, соединяющее узел 2 с узлом 6, но не ребро от узла 2 к узлу 3). В измененном графе каждый узел имеет степень 0, 1 или 2.

Теперь просмотрите график, начиная с узла 1. Сохраните все посещенные узлы в списке. Если вы достигли узла со степенью 1, начните снова с узла 2. (а затем с узла 3 и т. Д.).

Рассмотрим следующий пример вывода для графа с 7 узлами и ребрами E = {{1 , 2}, {2,3}, {3,4}, {4,5}, {6,7}}. Обратите внимание, что 1..5 обозначает список со следующими элементами {1}, {2}, {3}, {4}, {5}.

node | список | действительные пары

1 | 1..5 | 4 {(1,5), (1,4), (1,3), (1,2)}

2 | 2..5 | 3 {(2,5), {2,4), (2,3)}

3 | 3..5 | 2

4 | 4..5 | 1

5 | 5..5 | 0

6 | 6..7 | 1

7 | 7..7 | 0

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