Графовые структуры данных на Java

Введение

В этом руководстве вы узнаете, как создавать и манипулировать структурами данных графов на Java. Графы - это фундаментальная структура данных, используемая для представления отношений между объектами. Мы рассмотрим различные типы графов, способы их представления и реализацию общих операций, таких как добавление и удаление вершин и ребер, поиск в ширину, поиск в глубину и др.

Создайте класс Node

Сначала мы создадим класс Node, чтобы представлять вершины в графе. Каждая вершина будет иметь имя и, возможно, другую информацию, такую как значение или вес.

public class Node {
    private String name;

    public Node(String name) {
        this.name = name;
    }

    public String getName() {
        return name;
    }
}

Создайте класс Graph

Далее мы создадим класс Graph, чтобы представить сам граф. Мы будем использовать список смежности для хранения ребер и их концов.

import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

public class Graph {
    private Map<Node, List<Node>> adjacencyList;

    public Graph() {
        this.adjacencyList = new HashMap<>();
    }

    public void addNode(Node node) {
        adjacencyList.putIfAbsent(node, new ArrayList<>());
    }

    public void addEdge(Node node1, Node node2) {
        adjacencyList.get(node1).add(node2);
        adjacencyList.get(node2).add(node1);
    }

    public void removeNode(Node node) {
        adjacencyList.values().stream().forEach(e -> e.remove(node));
        adjacencyList.remove(node);
    }

    public void removeEdge(Node node1, Node node2) {
        List<Node> list1 = adjacencyList.get(node1);
        List<Node> list2 = adjacencyList.get(node2);
        if (list1!= null) {
            list1.remove(node2);
        }
        if (list2!= null) {
            list2.remove(node1);
        }
    }

    public List<Node> getNeighbors(Node node) {
        return adjacencyList.get(node);
    }
}

Создайте граф

Теперь создадим граф и добавим несколько вершин и ребер.

Graph graph = new Graph();
Node nodeA = new Node("A");
Node nodeB = new Node("B");
Node nodeC = new Node("C");
Node nodeD = new Node("D");

graph.addNode(nodeA);
graph.addNode(nodeB);
graph.addNode(nodeC);
graph.addNode(nodeD);

graph.addEdge(nodeA, nodeB);
graph.addEdge(nodeB, nodeC);
graph.addEdge(nodeC, nodeD);
graph.addEdge(nodeD, nodeA);

Поиск в ширину

Теперь мы реализуем алгоритм поиска в ширину для обхода вершин графа в ширину.

import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.Deque;
import java.util.List;

public class BreadthFirstSearch {
    public List<Node> bfs(Graph graph, Node start) {
        List<Node> visited = new ArrayList<>();
        Deque<Node> queue = new ArrayDeque<>();
        visited.add(start);
        queue.add(start);

        while (!queue.isEmpty()) {
            Node node = queue.poll();
            List<Node> neighbors = graph.getNeighbors(node);
            for (Node neighbor : neighbors) {
                if (!visited.contains(neighbor)) {
                    visited.add(neighbor);
                    queue.add(neighbor);
                }
            }
        }

        return visited;
    }
}

Пример запуска:

javac Graph.java BreadthFirstSearch.java Node.java && java BreadthFirstSearch

Поиск в глубину

Теперь мы реализуем алгоритм поиска в глубину для обхода вершин графа в глубину.

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

public class DepthFirstSearch {
    public List<Node> dfs(Graph graph, Node start) {
        List<Node> visited = new ArrayList<>();
        dfsHelper(graph, start, visited, new HashSet<>());
        return visited;
    }

    private void dfsHelper(Graph graph, Node current, List<Node> visited, Set<Node> seen) {
        visited.add(current);
        seen.add(current);
        for (Node neighbor : graph.getNeighbors(current)) {
            if (!seen.contains(neighbor)) {
                dfsHelper(graph, neighbor, visited, seen);
            }
        }
    }
}

Пример запуска:

javac Graph.java DepthFirstSearch.java Node.java && java DepthFirstSearch

Удалить узел

Мы можем удалить вершину из графа и также удалить любые ребра, соединенные с этой вершиной.

Graph graph = new Graph();
Node nodeA = new Node("A");
Node nodeB = new Node("B");
Node nodeC = new Node("C");
Node nodeD = new Node("D");

graph.addNode(nodeA);
graph.addNode(nodeB);
graph.addNode(nodeC);
graph.addNode(nodeD);

graph.addEdge(nodeA, nodeB);
graph.addEdge(nodeB, nodeC);
graph.addEdge(nodeC, nodeD);
graph.addEdge(nodeD, nodeA);

graph.removeNode(nodeC);

Удалить ребро

Мы можем удалить ребро между двумя вершинами в графе.

Graph graph = new Graph();
Node nodeA = new Node("A");
Node nodeB = new Node("B");

graph.addNode(nodeA);
graph.addNode(nodeB);

graph.addEdge(nodeA, nodeB);
graph.addEdge(nodeB, nodeC);

graph.removeEdge(nodeA, nodeB);

需注意，原始内容中“graph.addEdge(nodeB, nodeC);”这里的“nodeC”未定义，翻译时保留了原文错误。

Резюме

В этом уроке мы узнали, как создавать структуру данных "граф" на Java с использованием представления вершин и списка смежности. Мы также реализовали операции по манипуляции с графом, включая добавление и удаление вершин и ребер. Наконец, мы реализовали два алгоритма поиска: поиск в ширину и поиск в глубину.