Структура и алгоритм графа кратчайшего пути Найта

Question

У меня есть вопрос по одному из предыдущих постов в стеке @ Шахматный вопрос о кратчайшем пути Найта

Я понимаю ответ "хорошо, это вопрос графика, и его разреженная матрица похожа":

(a1,b3)=1,
(a1,c2)=1,
  .....

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

http://en.wikipedia.org/wiki/Dijkstra%27s_algorithm.

Из описания алгоритма выглядит удобно, если структура данных графа представляет собой набор вершин с доступной информацией о соседних вершинах. Но как нам этого добиться?

Кто-нибудь может помочь выписать пример структуры данных для этого графа и немного объяснить, как его можно удобно связать с алгоритмом Дейкстры?

Спасибо,

Answer 1

График очень разреженный (64 вершины, каждая вершина имеет не более 8 ребер), поэтому матрица смежности является пустой IMO.

Лучшей структурой для этого будет список смежности:

v1->v2,v3,v4,v5
v2->v1,...
...

Идея в том, чтобы действительно провести Set<Vertex>и для Vertex введите поле: List<Vertex> neighbors, который будет содержать все соседние вершины вершины.

В этом случае нет необходимости в какой-либо дополнительной информации о весе - поскольку график не взвешен.

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

Answer 2

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

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

edit: хорошо, на самом деле, вам все еще может понадобиться это, если вы используете этот трюк, но тогда остается, что он просто требует нескольких быстрых операций, таких как битовое сканирование и x &= x -1,