src/graph/GraphAlgorithms.java - master - victor_t/simple_navigator

src/graph/GraphAlgorithms.java
556 строк17 KB
Victor
fix: library classes
06 июл 2026, 01:06
06 июл 2026, 01:0641665e7
package graph;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.HashSet;
import java.util.List;
import java.util.Random;
import java.util.Set;

/**
 * Коллекция алгоритмов на графах: DFS, BFS, Дейкстра,
 * Флойд-Уоршелл и алгоритм Прима (MST).
 */
public class GraphAlgorithms {

  /**
   * Выполняет обход графа в глубину (DFS), начиная с заданной вершины.
   * Используется явный стек для избежания рекурсии.
   *
   * @param graph       граф (вершины нумеруются с 1)
   * @param startVertex стартовая вершина (индексация с 1)
   * @return список вершин в порядке их посещения
   * @throws IllegalArgumentException если {@code startVertex} вне допустимого диапазона
   */
  public List<Integer> depthFirstSearch(Graph graph, int startVertex) {
    int size = graph.getSize();
    if (startVertex < 1 || startVertex > size) {
      throw new IllegalArgumentException("Vertex out of range: " + startVertex);
    }

    boolean[] visited = new boolean[size + 1];
    List<Integer> result = new ArrayList<>();
    Stack<Integer> stack = new Stack<>();
    stack.push(startVertex);
    visited[startVertex] = true;

    while (!stack.isEmpty()) {
      int vertex = stack.pop();
      result.add(vertex);

      List<Integer> neighbors = graph.getNeighboringVertices(vertex);
      for (int neighbor : neighbors) {
        if (!visited[neighbor]) {
          visited[neighbor] = true;
          stack.push(neighbor);
        }
      }
    }

    return result;
  }

  /**
   * Выполняет обход графа в ширину (BFS), начиная с заданной вершины.
   *
   * @param graph       граф (вершины нумеруются с 1)
   * @param startVertex стартовая вершина (индексация с 1)
   * @return список вершин в порядке их посещения
   * @throws IllegalArgumentException если {@code startVertex} вне допустимого диапазона
   */
  public List<Integer> breadthFirstSearch(Graph graph, int startVertex) {
    int size = graph.getSize();
    if (startVertex < 1 || startVertex > size) {
      throw new IllegalArgumentException("Vertex out of range: " + startVertex);
    }

    boolean[] visited = new boolean[size + 1];
    List<Integer> result = new ArrayList<>();
    Queue<Integer> queue = new Queue<>(graph.getSize());

    queue.push(startVertex);
    visited[startVertex] = true;

    while (!queue.isEmpty()) {
      int vertex = queue.pop();
      result.add(vertex);

      List<Integer> neighbors = graph.getNeighboringVertices(vertex);
      for (int neighbor : neighbors) {
        if (!visited[neighbor]) {
          visited[neighbor] = true;
          queue.push(neighbor);
        }
      }
    }

    return result;
  }

  /**
   * Находит кратчайшее расстояние между двумя вершинами с помощью алгоритма Дейкстры.
   * Граф должен содержать неотрицательные веса рёбер.
   *
   * @param graph   граф (вершины нумеруются с 1)
   * @param vertex1 начальная вершина (индексация с 1)
   * @param vertex2 целевая вершина (индексация с 1)
   * @return кратчайшее расстояние от {@code vertex1} до {@code vertex2}
   * или {@code Integer.MAX_VALUE}, если пути не существует
   */
  public int getShortestPathBetweenVertices(Graph graph, int vertex1, int vertex2) {
    int size = graph.getSize();
    int[][] adj = graph.getAdjMatrix();

    int[] dist = new int[size];
    boolean[] visited = new boolean[size];
    Arrays.fill(dist, Integer.MAX_VALUE);
    dist[vertex1 - 1] = 0;

    for (int i = 0; i < size; i++) {
      int u = -1;
      for (int v = 0; v < size; v++) {
        if (!visited[v] && (u == -1 || dist[v] < dist[u])) {
          u = v;
        }
      }

      if (u == -1 || dist[u] == Integer.MAX_VALUE) {
        break;
      }
      visited[u] = true;

      for (int v = 0; v < size; v++) {
        if (!visited[v] && adj[u][v] != 0 && dist[u] + adj[u][v] < dist[v]) {
          dist[v] = dist[u] + adj[u][v];
        }
      }
    }

    return dist[vertex2 - 1];
  }

  /**
   * Вычисляет кратчайшие пути между всеми парами вершин с помощью алгоритма Флойда‑Уоршелла.
   *
   * @param graph входной граф (вершины нумеруются с 1)
   * @return двумерный массив, где {@code result[i][j]} — кратчайшее расстояние
   * от вершины i+1 до j+1,
   * или {@code Integer.MAX_VALUE}, если пути не существует.
   * Массив использует нулевую индексацию, но соответствует вершинам 1..size.
   */
  public int[][] getShortestPathsBetweenAllVertices(Graph graph) {
    int size = graph.getSize();
    int[][] adj = graph.getAdjMatrix();
    int[][] dist = new int[size][size];

    for (int i = 0; i < size; i++) {
      for (int j = 0; j < size; j++) {
        if (i == j) {
          dist[i][j] = 0;
        } else if (adj[i][j] != 0) {
          dist[i][j] = adj[i][j];
        } else {
          dist[i][j] = Integer.MAX_VALUE;
        }
      }
    }

    for (int k = 0; k < size; k++) {
      for (int i = 0; i < size; i++) {
        for (int j = 0; j < size; j++) {
          if (dist[i][k] != Integer.MAX_VALUE && dist[k][j] != Integer.MAX_VALUE) {
            dist[i][j] = Math.min(dist[i][j], dist[i][k] + dist[k][j]);
          }
        }
      }
    }

    return dist;
  }

  /**
   * Находит минимальное остовное дерево (MST) с помощью алгоритма Прима.
   * Алгоритм начинает работу с вершины 1.
   *
   * @param graph входной неориентированный связный граф (вершины нумеруются с 1)
   * @return матрица смежности (размером size×size) для MST.
   * Массив использует нулевую индексацию, но соответствует вершинам 1..size.
   * Рёбра, не вошедшие в MST, равны 0.
   */
  public int[][] getLeastSpanningTree(Graph graph) {
    int size = graph.getSize();
    int[][] adj = graph.getAdjMatrix();
    int[][] result = new int[size][size];

    boolean[] inMST = new boolean[size];
    int[] minDist = new int[size];
    int[] parent = new int[size];

    Arrays.fill(minDist, Integer.MAX_VALUE);
    Arrays.fill(parent, -1);
    minDist[0] = 0;

    for (int i = 0; i < size; i++) {
      int u = -1;
      for (int v = 0; v < size; v++) {
        if (!inMST[v] && (u == -1 || minDist[v] < minDist[u])) {
          u = v;
        }
      }

      if (minDist[u] == Integer.MAX_VALUE) {
        break;
      }
      inMST[u] = true;

      if (parent[u] != -1) {
        result[parent[u]][u] = adj[parent[u]][u];
        result[u][parent[u]] = adj[u][parent[u]];
      }

      for (int v = 0; v < size; v++) {
        if (!inMST[v] && adj[u][v] != 0 && adj[u][v] < minDist[v]) {
          minDist[v] = adj[u][v];
          parent[v] = u;
        }
      }
    }

    return result;
  }

  /**
   * Решает задачу коммивояжёра (TSP) с использованием муравьиного алгоритма.
   *
   * <p>Алгоритм имитирует поведение муравьёв, строящих маршруты с учётом
   * феромонов и эвристики расстояний. После каждой итерации феромоны
   * испаряются и обновляются на основе лучших найденных путей.</p>
   *
   * @param graph граф, на котором выполняется поиск маршрута
   * @return результат, содержащий оптимальный найденный маршрут и его длину
   * @throws RuntimeException если невозможно построить ни одного корректного маршрута
   */
  public TsmResult solveTravelingSalesmanProblem(Graph graph) {
    int size = graph.getSize();
    final int ANTS_COUNT = size;
    final int ITERATIONS = 1000;
    final double ALPHA = 1.0;
    final double BETA = 2.0;
    double[][] pheromones = new double[size][size];

    for (int i = 0; i < size; i++) {
      Arrays.fill(pheromones[i], 1.0);
    }
    Random random = new Random();
    List<Integer> bestPath = null;
    double bestDistance = Double.MAX_VALUE;

    for (int iteration = 0; iteration < ITERATIONS; iteration++) {

      List<AntPath> antPaths = new ArrayList<>();

      for (int ant = 0; ant < ANTS_COUNT; ant++) {

        int startVertex = random.nextInt(size) + 1;

        List<Integer> path = buildPath(
            graph,
            startVertex,
            pheromones,
            random,
            ALPHA,
            BETA
        );

        if (path == null) {
          continue;
        }

        double distance = calculateDistance(graph, path);

        antPaths.add(new AntPath(path, distance));

        if (distance < bestDistance) {
          bestDistance = distance;
          bestPath = new ArrayList<>(path);
        }
      }

      evaporatePheromones(pheromones);
      updatePheromones(pheromones, antPaths);
    }

    if (bestPath == null) {
      throw new RuntimeException("Impossible to solve the problem");
    }

    TsmResult result = new TsmResult();
    result.vertices = bestPath.stream()
        .mapToInt(Integer::intValue)
        .toArray();
    result.distance = bestDistance;

    return result;
  }

  /**
   * Строит маршрут муравья, начиная с заданной вершины.
   *
   * <p>Маршрут строится пошагово с выбором следующей вершины
   * на основе вероятностей, зависящих от феромонов и расстояний.</p>
   *
   * @param graph       граф
   * @param startVertex начальная вершина
   * @param pheromones  матрица феромонов
   * @param random      генератор случайных чисел
   * @param alpha       коэффициент влияния феромонов
   * @param beta        коэффициент влияния расстояния
   * @return список вершин маршрута или {@code null}, если маршрут невозможен
   */
  private List<Integer> buildPath(
      Graph graph,
      int startVertex,
      double[][] pheromones,
      Random random,
      double alpha,
      double beta
  ) {

    int verticesCount = graph.getSize();

    List<Integer> path = new ArrayList<>();
    Set<Integer> visited = new HashSet<>();

    int currentVertex = startVertex;

    path.add(currentVertex);
    visited.add(currentVertex);

    while (visited.size() < verticesCount) {

      int nextVertex =
          chooseNextVertex(
              graph,
              currentVertex,
              visited,
              pheromones,
              random,
              alpha,
              beta
          );

      if (nextVertex == -1) {
        return null;
      }

      path.add(nextVertex);
      visited.add(nextVertex);

      currentVertex = nextVertex;
    }

    if (!graph.hasEdge(currentVertex, startVertex)) {
      return null;
    }

    path.add(startVertex);

    return path;
  }

  /**
   * Выбирает следующую вершину для посещения на основе вероятностного правила.
   *
   * <p>Вероятность зависит от уровня феромонов и расстояния до вершины.</p>
   *
   * @param graph         граф
   * @param currentVertex текущая вершина
   * @param visited       множество уже посещённых вершин
   * @param pheromones    матрица феромонов
   * @param random        генератор случайных чисел
   * @param alpha         влияние феромонов
   * @param beta          влияние расстояния
   * @return следующая вершина или -1, если выбор невозможен
   */
  private int chooseNextVertex(
      Graph graph,
      int currentVertex,
      Set<Integer> visited,
      double[][] pheromones,
      Random random,
      double alpha,
      double beta
  ) {

    int verticesCount = graph.getSize();

    double[] probabilities =
        calculateProbabilities(graph,
            currentVertex,
            visited,
            pheromones,
            alpha,
            beta);

    double randomValue = random.nextDouble();

    double cumulativeProbability = 0.0;

    for (int vertex = 1; vertex <= verticesCount; vertex++) {

      cumulativeProbability += probabilities[vertex];

      if (randomValue <= cumulativeProbability) {
        return vertex;
      }
    }

    return -1;
  }

  /**
   * Вычисляет вероятности перехода из текущей вершины в другие.
   *
   * <p>Используется формула муравьиного алгоритма с нормализацией.</p>
   *
   * @param graph         граф
   * @param currentVertex текущая вершина
   * @param visited       множество посещённых вершин
   * @param pheromones    матрица феромонов
   * @param alpha         влияние феромонов
   * @param beta          влияние расстояния
   * @return массив вероятностей перехода по вершинам
   */
  private double[] calculateProbabilities(
      Graph graph,
      int currentVertex,
      Set<Integer> visited,
      double[][] pheromones,
      double alpha,
      double beta
  ) {

    int verticesCount = graph.getSize();

    double[] probabilities = new double[verticesCount + 1];

    double total = 0.0;

    for (int vertex = 1; vertex <= verticesCount; vertex++) {

      if (visited.contains(vertex)) {
        continue;
      }

      if (!graph.hasEdge(currentVertex, vertex)) {
        continue;
      }

      double pheromone =
          Math.pow(
              pheromones[currentVertex - 1][vertex - 1],
              alpha
          );

      double visibility =
          Math.pow(
              1.0
                  / graph.getDistance(currentVertex, vertex),
              beta
          );

      probabilities[vertex] =
          pheromone * visibility;

      total += probabilities[vertex];
    }

    if (total == 0.0) {
      return probabilities;
    }

    for (int vertex = 1; vertex <= verticesCount; vertex++) {
      probabilities[vertex] /= total;
    }

    return probabilities;
  }

  /**
   * Вычисляет длину маршрута.
   *
   * @param graph граф
   * @param path  список вершин маршрута
   * @return суммарная длина пути
   */
  private double calculateDistance(
      Graph graph,
      List<Integer> path
  ) {

    double distance = 0.0;

    for (int i = 0; i < path.size() - 1; i++) {

      int from = path.get(i);
      int to = path.get(i + 1);

      distance += graph.getDistance(from, to);
    }

    return distance;
  }

  /**
   * Выполняет испарение феромонов на всех рёбрах графа.
   *
   * <p>Феромоны уменьшаются на фиксированный коэффициент испарения.</p>
   *
   * @param pheromones матрица феромонов
   */
  private void evaporatePheromones(
      double[][] pheromones
  ) {
    final double EVAPORATION_RATE = 0.5;
    for (int i = 0; i < pheromones.length; i++) {

      for (int j = 0; j < pheromones[i].length; j++) {

        pheromones[i][j] *=
            (1.0 - EVAPORATION_RATE);
      }
    }
  }

  /**
   * Обновляет феромоны на основе найденных маршрутов муравьёв.
   *
   * <p>Чем короче маршрут, тем больше феромонов он добавляет.</p>
   *
   * @param pheromones матрица феромонов
   * @param antPaths   список маршрутов, построенных муравьями
   */
  private void updatePheromones(
      double[][] pheromones,
      List<AntPath> antPaths
  ) {

    for (AntPath antPath : antPaths) {

      double contribution =
          1.0 / antPath.distance();

      List<Integer> path =
          antPath.path();

      for (int i = 0; i < path.size() - 1; i++) {

        int from = path.get(i);
        int to = path.get(i + 1);

        pheromones[from - 1][to - 1] += contribution;
        pheromones[to - 1][from - 1] += contribution;
      }
    }
  }
}