Графы. Простой класс графа (неориентированного)

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

import java.util.Map;
import java.util.List;
import java.util.HashMap;
import java.util.ArrayList;
import java.util.Collections;
 
public class UndirectedGraph {
 
    private HashMap<String, List<String>> vertexMap = new HashMap<String, List<String>>();
 
    public void addVertex(String vertexName) {
        if (!hasVertex(vertexName)) {
            vertexMap.put(vertexName, new ArrayList<String>());
        }
    }
 
    public boolean hasVertex(String vertexName) {
        return vertexMap.containsKey(vertexName);
    }
 
    public boolean hasEdge(String vertexName1, String vertexName2) {
        if (!hasVertex(vertexName1)) return false;
        List<String> edges = vertexMap.get(vertexName1);
        return Collections.binarySearch(edges, vertexName2) != -1;
    }
 
    public void addEdge(String vertexName1, String vertexName2) {
        if (!hasVertex(vertexName1)) addVertex(vertexName1);
        if (!hasVertex(vertexName2)) addVertex(vertexName2);
        List<String> edges1 = vertexMap.get(vertexName1);
        List<String> edges2 = vertexMap.get(vertexName2);
        edges1.add(vertexName2);
        edges2.add(vertexName1);
        Collections.sort(edges1);
        Collections.sort(edges2);
    }
 
    public Map<String, List<String>> getVertexMap() {
        return vertexMap;
    }
}

Отметим некоторые особенности:

• Внутреннее представление графа - список смежности


• Вершины однозначно идентифицируются строковыми идентификаторами (именами). Не допускается двух вершин с одинаковым именем


• Список смежных вершин держится отсортированным, так чтобы можно было быстро найти вершину в списке по имени (для поиска в отсортированном списке используется двоичный поиск)


• Для того, чтобы добавить ребро между двумя вершинами, необязательно предварительно добавлять вершины в граф. Несуществующие вершины будут созданы автоматически