* Алгоритм для неориентированного графа

Я знаюA*, что алгоритм может быть использован в направленном графе, можем ли мы использовать его в неориентированном графе?

1 ответ

  1. Алгоритм A* является общим для всех графиков. Так что да, вы можете использовать его с неориентированным графом.

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

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