


Программирование
+2Задача на Java
Нужно найти ребра заданного графа, которые принадлежат каждому пути между двумя
заданными вершинами. Какой примерно алгоритм мне нужно реализовать?
По дате
По рейтингу
какие ребра ты чё доктор?
123456789101112131415161718192021222324252627282930313233343536373839404142434445
import java.util.*;
class Graph {
private final Map<Integer, List<Integer>> adjList = new HashMap<>();
void addEdge(int src, int dest) {
try {
if (src < 0 || dest < 0) {
throw new IllegalArgumentException("Номера вершин должны быть неотрицательными.");
}
adjList.computeIfAbsent(src, k -> new ArrayList<>()).add(dest);
adjList.computeIfAbsent(dest, k -> new ArrayList<>()).add(src);
} catch (IllegalArgumentException e) {
System.err.println("Ошибка при добавлении ребра: " + e.getMessage());
}
}
Set<Integer> findBridges(int start, int end) {
Set<Integer> bridges = new HashSet<>();
try {
if (!adjList.containsKey(start) || !adjList.containsKey(end)) {
throw new NoSuchElementException("Одна из вершин не существует в графе.");
}
} catch (NoSuchElementException e) {
System.err.println("Ошибка при поиске рёбер: " + e.getMessage());
} catch (Exception e) {
System.err.println("Произошла непредвиденная ошибка: " + e.getMessage());
}
return bridges;
}
private Set<Integer> dfsFindBridges(int current, int end, Set<Integer> visited) {
return new HashSet<>();
}
public static void main(String[] args) {
Graph graph = new Graph();
graph.addEdge(0, 1);
graph.addEdge(1, 2);
Set<Integer> bridges = graph.findBridges(0, 2);
System.out.println("Рёбра, принадлежащие каждому пути: " + bridges);
}
}