src/Graph.java - master - Hatshess/Graphs

src/Graph.java
51 строка2 KB
Hatshess
Загрузить файлы в «»
04 окт 2025, 16:50
04 окт 2025, 16:50c999fde
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
        // если такую вершину ещё не посещали, заходим рекурсивно в неё
        // если такой заход завершился нахождением target-а - выходим из метода с true

        for (Vertex tempVertex : v.getAdjacent()) {
            if (!visited.contains(tempVertex)) {
                if (dfsFind(tempVertex, target, visited)) {
                    return true;
                }
            }
        }

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

}