Почти все связанные с трассой алгоритмы графа, похоже, используют шаблон, который включает сохранение края, которое использовалось для перехода к текущей вершине. Напротив, почему в текущей вершине не содержится ссылки на следующий ребро, подобно связанным спискам? Думаю, вы могли бы, но какие компромиссы?Почему алгоритмы графа ссылаются на предыдущий край?
Действительно, здесь есть несколько смешанных концепций. Во-первых, я просмотрю структуру данных Graph.
Структура данных представляет собой способ структурирования данных (ок, этот был легко). Вот как ваш график будет представлен внутри. И есть много возможностей.
Если вы думаете об этом немного, на графике есть два центральных понятия: ребра и вершины. То, как вы решили хранить их, полностью зависит от вас. Для более легкого объяснения я рассмотрю, что вершинам присваивается уникальный номер от 0 до V-1.
Существует несколько представлений вокруг, и в зависимости от вашей проблемы можно быть более подходящим, чем другое. В принципе, существует избыточная информация между вершинами и ребрами, поэтому создание структуры для обоих является излишним. Сейчас я рассмотрю оба дела.
Вы можете создать явную явную структуру Вершины. Каждая вершина содержит список вершин, в которые он тоже может идти. Структура графа должна поддерживать массив всех Вершин, чтобы сделать его эффективным. Это структура, о которой вы говорите, и она действительна.
В этом случае ребра неявны: если вершина может перейти на другую, то между ними есть ребро. Однако структура Edge не создается, это подразумевается списком, содержащимся в каждой вершине.
Вторая возможность, создать структуру края. Каждый Edge содержит свою начальную точку и конечную точку (которые являются вершинами и могут быть представлены целыми числами). Структура данных Графа содержит массив, и для каждого слота хранится список всех ребер, начинающихся (или заканчивающих) в этой вершине.
Опять же, это допустимая структура данных, обычно называемая представлением списка смежности. И на этот раз нет явной структуры Vertex: они представляют собой целые числа, содержащиеся в Edges.
Используя явные грани (и неявные вершины), существует также представление смежности-матрицы, которое может быть полезно, если граф плотен.
В конце концов, выбор представления графа о том, что лучше всего подходит вашему делу, и который вы понимаете лучше, но абсолютного правила нет.
В моем случае я быстро понял список смежности, но мне нелегко было разглядеть первое представление, поэтому вы должны выбрать тот, с которым вам удобнее.
Теперь выполните алгоритмы. Идея заключается в том, что с учетом структуры графа (независимо от того, какое представление стоит позади), который предоставляет некоторые определенные функции, обработайте этот график, чтобы получить некоторую информацию об этом.
В случае DFS/BFS, поиск информации - это перемещение графика из одной исходной вершины в каждую достижимую вершину. Это правда, что в отношении этих алгоритмов каждая вершина связана с одним из его предшественников.
Это потому, что информация, которую мы хотим получить от этих алгоритмов, состоит в том, чтобы получить один путь от источника к другой вершине:. Конечно, есть и другие пути, но это не имеет значения.
Фактически, поиск всех возможных путей от одной вершины к каждой другой является NP-полной проблемой, а иногда и невозможной (если есть цикл, например).
Вот почему хранится только предшественник вершины: потому что все, что нам нужно, - один из путей, и это делает эти алгоритмы эффективными как с точки зрения пространства, так и с памятью.
Надеюсь, это ответит на ваш вопрос и очистит ваши мысли.
Мне было любопытно узнать о * дизайне *. Но я более подробно рассмотрел алгоритм dijkstra, и только ссылка на предыдущий край привела к изящному способу борьбы с «отключением» предыдущего пути, поскольку это просто побочный эффект изменения предыдущего края. – user1164937
Не знаете, к каким примерам вы обращаетесь, но обычно в ориентированном графе вершина делает ссылкой на «следующие ребра», вершины IE в окрестности узла. Это обычно более полезно, чем удерживание вершин, чьи окрестности содержат текущий узел. Вы можете записывать оба, но недостатком является то, что:
Вы говорите о двух разных понятиях в этом вопросе; алгоритм и структура данных. Точка в связанных с пути алгоритмах (скажем, BFS DFS) заключается в том, что вы должны иметь возможность пересекать пути, то есть алгоритм, но то, как вы хотите сконструировать свою структуру данных, зависит от вас и зависит от конкретной проблемы, которую вы хотите решить , каковы ваши ограничения и точные требования. Вы можете проверить структуру данных Half-Edge, Face-Based Data Structures, которые используются для решения сложных топологических и алгоритмических задач с графиками (точнее, сетками). Надеюсь, это поможет
Что делать, если есть несколько следующих краев? Какой из них вы будете хранить? Мне кажется, что это зависит от меня. "Как я сюда попал?" – duffymo