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

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

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

Изменить: я должен упомянуть, что название автора и вопрос изменились так сильно, что некоторая информация в этом ответе может быть не на 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()) {
            ...
        }
    }
}

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

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

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

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

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

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

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

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

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