Top.Mail.Ru
Ответы
Аватар пользователя
Аватар пользователя
Аватар пользователя
Аватар пользователя
Программирование
+2

Задача на Java

Нужно найти ребра заданного графа, которые принадлежат каждому пути между двумя
заданными вершинами. Какой примерно алгоритм мне нужно реализовать?

По дате
По рейтингу
Аватар пользователя
Новичок
9мес

какие ребра ты чё доктор?

Аватар пользователя
Мудрец
9мес
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); 
    } 
}