График транзитивности Java

Question

Я использую пользовательский график для представления набора данных, как показано на рисунке:

Я уже создал несколько методов что позволяет мне заполнить структуру. Основная цель этого типа представления - быстро узнать, существует ли указанный c путь. У меня есть следующая проблема с методом поиска пути:

Например, если я рассматриваю пути "A-> D-> X", "B-> D -> #", "A-> E -> # "," A-> D -> # ", тогда я бы хотел получить существование путей. Однако, если я рассмотрю путь «B -> D -> X», я хотел бы получить, что путь не существует.

Есть ли у вас какие-либо предложения по разработке этого типа метода без учета начального набор данных?

Answer 1

Если в вашей таблице доступны только пути, вы можете использовать любую реализацию заданной структуры данных, например HashSet или TreeSet в Java. Просто добавьте все пути к набору, а затем используйте метод Set.contains, чтобы проверить, является ли путь допустимым.

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

Например, tr ie - это набор для последовательностей элементы, которые позволяют проверить, присутствует ли последовательность во времени, пропорциональном длине последовательности. Он традиционно использовался для строк, но вы можете легко использовать его для путей к графам. При таком использовании узлы в tr ie будут хранить узлы вашего графа, так что путь в tr ie соответствует действительному пути в вашем графе.

Answer 2

Здесь делается два предположения:

1. Ребра двунаправлены;
2. В отличие от перечисленных вами примеров, вы не ищете пути с 3 узлами (или 2 ребрами) только значение A->E->#->D->B также является допустимым путем и должно возвращать значение true.

---

Несвязанные множества / структура данных объединения-поиска дает вам именно эту возможность.

В этом DS, который имеет более одной базовой реализации, все подключенные узлы будут в одном наборе. Таким образом, если у вас есть n связанных компонентов, то у вас будет столько же непересекающихся наборов.

Чтобы узнать, существует ли путь между узлом-1 и узлом-2, просто посмотрите, если они находятся в одном наборе.