Должен ли я выполнять итерацию по ориентированному графу с использованием итеративного углубления поиска в глубину (IDDFS)?

Question

Пример: у меня есть 20 человек в качестве объекта, и каждый человек знает 0-н других.Направление ссылки имеет значение!Человек A может знать B, но B может не знать A. Это ориентированный граф.

Редактировать: Для упрощения, мои объекты узлов (в данном случае объекты Person)возможность хранить произвольную информацию.Я знаю, что это не лучший дизайн, но сейчас это было бы хорошо.

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

Это иллюстрирует проблему в упрощенном виде: благодаря источнику

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

Давайтепредставьте, что человек A знает B, кто знает C, и кто знает A. Выходные данные могут быть:

A знает, что B знает, что C знает A (хорошо, но мы не хотим заканчивать бесконечный цикл, поэтому мы останавливаемсяздесь) A знает, что C знает, что AA знает, что T знает, что R знает, что V

Это было бы глупо и должно быть устранено: A знает, что B знает, что C знает, A знает, что C знает, знает, что T знает, что R знает, что V ...

У меня есть пара сумасшедших идей, как решить эту проблему.Но ...

Вопрос) Должен ли я сделать это с помощью итеративного углубленного поиска в глубину (IDDFS)?

---

Джон любезно указал DFS в Википедии

Я застрял с этой частью в статье:

поиск в глубину, начинающийся с A, при условии, что левые края на показанном графикевыбираются перед правыми краями, и, предполагая, что поиск запоминает ранее посещенные узлы и не будет повторять их (так как это небольшой график), будет посещать узлы в следующем порядке: A, B, D, F, E, C,G. Пересекаемые в этом поиске ребра образуют дерево Тремо, структуру с важными приложениями в теории графов.

, в частности, это примечание:

"(поскольку этомаленький график) "

Хорошо, а что, если это огромный график?

Answer 1

Редактировать: я должен упомянуть название автора, и вопрос так сильно изменился, некоторая информация в этом ответе может не соответствовать 100%.

Как уже упоминал Джон, это действительно график.,Фактически ориентированный граф.

Я предлагаю вам взглянуть на Матрицы смежности , они предоставят вам прямое представление о том, как вы можете найти решение.Я полагаю, что ваше оригинальное ленивое решение было, вероятно, чем-то вроде списка смежности ;это хорошо, но не так легко реализовать, а также может быть сложнее пройти.Существует два основных различия между этими двумя.

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

Основной проблемой, которую я обнаружил при использовании списков смежности, было не их теоретическое пространство, нов C ++ я сохранял каждый связанный узел как указатель на вектор внутри каждого узла;это может выйти из-под контроля, как только сеть станет больше, и было очень недружелюбно визуализировать, а также управлять новыми узлами и удалять узлы.По сравнению с матрицами смежности, которые имеют единую ссылку для всех узлов (могут храниться в одном векторе узлов) и могут быть легко изменены.

---

Если ваш вопрос действительно касается обхода, то еслиВаш граф реализован в виде матрицы смежности, как вектор векторов, обход которого прост.См. Ниже псевдокод:

Чтобы прочитать (для каждого нейрона) все нейроны, к которым подключен аксон нейрона (т. Е. Выходы нейрона)

for (size_t i = 0; i < n; ++i) { // adjacency matrix is n * n
    Neuron& neuron = nodes[i];
    for (size_t j = 0; i < n; ++i) {
        Axon_connection& connection = edges[j][i];
        if (connection.exists()) {
            ...
        }
    }
}

Чтобы прочитать все (для каждого нейрона) нейроны нейронадендриты подключены (например, к нейронным входам)

for (size_t i = 0; i < n; ++i) { // adjacency matrix is n * n
    Neuron& neuron = nodes[i];
    for (size_t j = 0; i < n; ++i) {
        Dendrite& dendrite = edges[j][i];
        if (dendrite.exists()) {
            ...
        }
    }
}

Обратите внимание, что этот второй метод может не поддерживать кеш для больших сетей, в зависимости от вашей реализации.Существующий метод просто гарантирует, что бит матрицы смежности установлен в true, после чего вы можете реализовать другие данные, например, сильные стороны в этих ребрах.

Answer 2

Мой друг, вы отправили много похожих вопросов за последние день или два. Я предлагаю вам потратить немного времени и прочитать вводный учебник по теории графов или найти несколько лекций на эту тему.

Тогда вы хотя бы узнаете, как распознать и классифицировать стандартные проблемы. Все, что вы собираетесь получить на SO, - это ссылки на такие ресурсы - никому не стоит писать свежую экспозицию. Если у вас есть конкретный вопрос или вы застряли в понимании того или иного вопроса, спросите, и мы будем рады помочь, но вам нужно встретиться с нами на полпути.

Чтобы ответить на ваш вопрос, вы можете выполнить поиск в глубину и поиск в ширину на произвольном графике, как вы это делали ранее в дереве - вам просто нужно отслеживать, какие узлы вы посетили. Обращайте внимание на это в любом коде / псевдокоде, с которым вы столкнетесь. Вам не нужно отслеживать посещенные заметки на дереве (как и в других ваших вопросах), поскольку дерево - это особый экземпляр графа (связного ациклического графа), который не может быть «дико взаимосвязанным».

Answer 3

Отвечая на ваш оригинальный вопрос, это, безусловно, теоретически возможно решить.Однако, если вы идете по кратчайшему пути, то это выглядит подозрительно как проблема коммивояжера , которая NP-hard .

В любом случае, существует много разных графиков.алгоритмы обхода (DFS, IDDFS, BFS и т. д.), которые могут быть полезны.

Answer 4

Один из способов (и не обязательно лучший) сделать это - изменить график.

Например, скажем, что граф изначально кодирует A -> B -> C. Если ребро A -> C не существует, добавьте ребро A -> C.

Вы можете сделать это для каждого узла в графе, чтобы явно указать, какие узлы знают друг друга.

Answer 5

Ваша структура данных действительно является графиком.

Я не хочу давать такой простой ответ, но вопрос настолько прост, что Обход графика в Википедии более чем адекватен.Объясняются два основных подхода, а также псевдокод.