Расширение реализации этого списка смежности

Question

Что было бы лучшим способом изменить реализацию этого списка смежности для включения "веса" между двумя вершинами?

Если позже я добавлю ребро между двумя теми же вершинами, которые я сделал ранее, я просто хочу увеличить его вес.

http://www.keithschwarz.com/interesting/code/edmonds-matching/UndirectedGraph.java.html

Answer 1

Вместо того, чтобы хранить график как карту узлов для набора узлов, вы можете сохранить его как карту узлов для набора пар (узел, вес) (которые также могут быть картой). Так что вместо

    private final Map<T, Set<T>> mGraph = new HashMap<T, Set<T>>();

это будет

    private final Map<T, Map<T, Integer>> mGraph = new HashMap<T, Map<T, Integer>>();

В текущей реализации добавление ребра - это просто вставка нового в набор, с весами вам нужно будет прочитать текущий вес, увеличить его и сохранить на карте. Обратите внимание на угловые случаи, чтобы проверить, как при удалении ребра, и если его вес становится 0, вы должны удалить запись с карты.