Простой способ найти ребро графа между вершинами графа

Question

если есть 100 graph vertexes, каждая вершина графа имеет 4 graph ребер в направлении другой вершины графа и хранится в массиве, X. "X(100, 4)" - это размер массива, тогда как "X(38, 2)" означает содержимое массива в дваразмерный индекс 38, 2.

Есть ли какой-нибудь простой способ найти путь от данной начальной вершины графа до другой данной вершины графа?

Это не обязательно самый короткий ват, так какПока пункт назначения может быть достигнут.Спасибо!

Answer 1

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

По существу, он следует этому шаблону:

1. Начните с x, равного начальному узлу.
2. Еслиx - конечный узел, тогда мы закончили.
3. Если мы уже посетили x, тогда оставьте этот путь.
4. Для каждого из узлов y, подключенных к x,
5. Добавьте x к текущему пути и установите y = x.
6. Выполните алгоритм с шага 2.
7. Переходите к шагу 4.

Это будет исследовать каждыйвозможный путь от х, идущий как можно глубже в каждую ветвь, чтобы найти цель или тупик.Отсюда «глубина прежде всего».