В примере в этой статье описывается, как Java реализует обход в ширину (BFS) для расчета кратчайшего пути. Поделитесь этим со всеми для справки. Конкретный анализ заключается в следующем:
Мы используем строки для представления вершин графа, чтобы моделировать местоположения класса, площади, туалета, столовой, южных и северных ворот в школе, а затем вычисляем кратчайший путь между любыми двумя точками.
Как показано ниже:
Например, если я хочу пройти от Северных ворот до столовой, результат программы должен быть таким:
BFS: От [Северных ворот] до [Столовой]:North GateSquareCanteen.
Сначала определите интерфейс алгоритма. Алгоритм:
public Interface Algorithm { /** * Выполнить алгоритм*/ void Perform(Graph g, String sourceVertex /** * Получить путь*/ Map<String, String> getPath();}Затем определите график:
/** * (Ненаправленный) Graph*/public class Graph { // Начальная точка графика Private String firstVertax // Список смежности Private Map<String, List<String>> adj = new HashMap<>(); / Алгоритм обхода частный алгоритм алгоритма; public Graph(алгоритм алгоритма) { this.algorithm = алгоритм } /** * Выполнить алгоритм*/ public void Done() { алгоритм.perform(this, firstVertax); } /** * Получить кратчайший путь от начальной точки до точки {@code vertex} * @param vertex * @return */ public Stack<String> findPathTo(String vertex) { Stack<String> stack = new Stack< >() ; stack.add(vertex); Map<String, String> path = алгоритм.getPath(); for (String location = path.get(vertex) ; false == location.equals(firstVertax) ; location = path.get(location)) { stack.push(location); } stack.push(firstVertax); return stack; } /** * Добавить ребро*/ public void addEdge(String fromVertex, String toVertex) { если (firstVertax == null) { firstVertax = fromVertex } adj.get(fromVertex).add(toVertex); adj.get(toVertex).add(fromVertex); } /** * Добавить вершину*/ public void addVertex(String vertex) { adj.put(vertex, new ArrayList<>() } public Map<String, List<String>> getAdj() { return adj; }}Здесь мы используем шаблон стратегического проектирования, чтобы отделить алгоритм от класса Graph и выбрать алгоритм обхода для Graph, передав реализацию интерфейса Algorithm при построении объекта Graph.
общедоступный график (алгоритм алгоритма) {this.algorithm = алгоритм};Структура хранения неориентированного графа представляет собой список смежности. Здесь для представления списка смежности используется карта. Ключом карты является местоположение школы (String), а значением — список расположений (List<String>). связано с местоположением.
// Список смежности Private Map<String, List<String>> adj = new HashMap<>();
Затем напишите реализацию интерфейса алгоритма BFS:
/** * Инкапсулирует алгоритм BFS*/public class BroadFristSearchAlgorithm реализует алгоритм { // Сохраняем посещенные местоположения Private List<String> VisitVertex; // Сохраняем кратчайший путь Private Map<String, String> path; @Override public void Perform( Graph g, String sourceVertex) { if (null == visitVertex) {visitedVertex = new ArrayList<>() } if (null == path) {path = новый HashMap<>(); } BFS(g, sourceVertex); } @Override public Map<String, String> getPath() {возвратный путь; } Private void BFS(Graph g, String sourceVertex) {Queue<String> очередь = new LinkedList<>(); // Отметить начальную точку visitVertex.add(sourceVertex); // Поставить в очередь начальную точку length.add(sourceVertex); while (false ==); очередь.isEmpty()) { String ver =queue.poll(); List<String> toBeVisitedVertex = g.getAdj().get(ver); for (String v: toBeVisitedVertex) { if (false == visitVertex.contains( v)) { visitVertex.add(v); path.put(v, ver); очередь.add(v);Среди них путь — это тип карты, что означает путь от значения к ключу.
Описание алгоритма BFS:
1. Отметьте источник как посещенный и поместите его в очередь.
2. Возьмите вершину из очереди и получите все вершины, связанные с этой вершиной.
3. Пройдите через эти вершины, сначала определите, была ли вершина посещена, если нет, пометьте точку как посещенную, запишите текущий путь и поставьте текущую вершину в очередь.
4. Повторяйте шаги 2 и 3, пока очередь не станет пустой.
Тестовый пример:
String[] vertex = {"Северные ворота", "Южные ворота", "Классная комната", "Площадь", "Туалет", "Столовая"}; Edge[] Edges = { new Edge("Северные ворота", "Классная комната" ), new Edge("Северные ворота", "Квадрат"), new Edge("Класс", "Туалет"), new Edge("Квадрат", "Туалет"), new Edge("Квадрат", "Столовая"), new Edge("Туалет", "Южные ворота"), new Edge("Туалет", "Южные ворота"), };@Test public void testBFS() { Graph g = new Graph(new BroadFristSearchAlgorithm( )); addVertex(g); addEdge(g); g.done(); Stack<String> result = g.findPathTo("Столовая"); System.out.println("BFS: От [Северных ворот] до [Столовой]:"); while (!result.isEmpty()) { System.out.println(result.pop() });Я надеюсь, что эта статья будет полезна каждому, кто занимается программированием на Java.