Graph.java - master - hel_bumer/Graph

Graph.java
54 строки2 KB
hel_bumer
Graph
08 фев 2026, 11:26
08 фев 2026, 11:26e93b6e4
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) {
        // добавляем их друг друга в их списки смежности
        // ВАШ КОД
        if (!a.getAdjacent().contains(b)) {
            a.getAdjacent().add(b);
        }
        if (!b.getAdjacent().contains(a)) {
            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
        // если такую вершину ещё не посещали, заходим рекурсивно в неё
        // если такой заход завершился нахождением target-а - выходим из метода с true
        for (Vertex<T> neighbor : v.getAdjacent()) {
            if (!visited.contains(neighbor)) {
                if (dfsFind(neighbor, target, visited)) {
                    return true;
                }
            }
        }

        return false; // ничего не нашли
    }

}