Graph.java - master - ProjectEroxa/hw_20

Graph.java
49 строк2 KB
Евгений Ерошкин
upload files
21 июл 2025, 11:40
21 июл 2025, 11:40eeb090f
import java.util.ArrayList;
import java.util.HashSet;
import java.util.List;
import java.util.Set;

public class Graph<T> {
    private List<Vertex<T>> vertices = new ArrayList<>();

    public Vertex<T> createVertex(T value) {
        Vertex<T> v = new Vertex<>(value);
        vertices.add(v);
        return v;
    }

    public void createEdge(Vertex<T> a, Vertex<T> b) {
        // добавляем их друг друга в их списки смежности
        // ВАШ КОД
        a.getAdjacent().add(b);
        b.getAdjacent().add(a);
    }

    public boolean isConnected(Vertex<T> a, Vertex<T> b) {
        return dfsFind(a, b, new HashSet<>()); // рекурсивный обход в глубину
    }

    // метод отвечает на вопрос, нашли ли мы обходом из v вершину target с учётом
    // посещённых вершин, которые записаны в visited
    private boolean dfsFind(Vertex<T> v, Vertex<T> target, Set<Vertex<T>> visited) {
        // если вершина в которую зашли (v) это та которую мы искали (target), то поиск закончен
        if (v.equals(target)) {
            return true; // нашли
        }
        visited.add(v); // запоминаем вершину которую посетили

        // ВАШ КОД
        // перебираем все смежные вершины у v
        for (Vertex<T> neighbor : v.getAdjacent()) {
            // если такую вершину ещё не посещали, заходим рекурсивно в неё
            if (!visited.contains(neighbor)) {
                // если такой заход завершился нахождением target-а - выходим из метода с true
                if (dfsFind(neighbor, target, visited)) {
                    return true;
                }
            }
        }
        return false; // ничего не нашли
    }

}