Представление графа в Java

@XSasha · Регистрация: 19.09.2018

Студворк — интернет-сервис помощи студентам

Всем привет. У меня есть 2 вопроса. Может кто сталкивался с представлением графа в java:

1) Подскажите, как представить взвешенный граф в виде матрицы смежности. Ну то есть я понимаю, что двумерный массив должен быть, но он мне нужен ещё и динамический, потому что в моей программе пользователь сам добавляет вершины и рёбра (причём в строковом виде, что неприятно, ведь индексы матрицы должны быть числами). Думал как в С++ через вектор векторов сделать, но тут ArrayList, и я не знаю как с ним.

2) Тот же самый граф, но в виде списка смежности. Этот самый список я реализовал как HashMap<String, List<String>>, но это только для невзвешенного подходит, как веса сюда добавить не знаю.

Будет круто, если кинете какие-нибудь кусочки кода.

@xoraxax · 24.02.2020, 23:07

Создай класс edge, в котором будет вес и ссылка на следующую вершину. И гуглить научись - примеров навалом

@Сет · 24.02.2020, 23:57

Сделать свои модели для edges, vertices. Таким образом, ты сможешь добавлять веса.

Например:

Java
1
2
3
4
5
6
7
8
public class Vertex<T> {
    private T value;
}
public class Edge<T> {
    private final Vertex<T> from;
    private final Vertex<T> to;
    private final int weight;
}

Соответственно ты вообще отвяжешься от типов.

@XSasha · 25.02.2020, 01:59 **[ТС]**

xoraxax и Сет, а по матрице смежности что скажете?

@Сет · 25.02.2020, 19:10

Сделай матрицу смежности из созданной модели вершин и отдельно храни рёбра.

Java
1
2
protected final Map<Vertex<T>, List<Vertex<T>>> vertexes = new HashMap<>(); // твоя матрица смежности
protected final List<Edge<T>> edges = new ArrayList<>(); // рёбра с весами

Как вариант.

Новые блоги и статьи Все статьи Все блоги /
10 пpимет, которые всегда сбываются Maks 31.03.2026 1. Чтобы, наконец, пришла маршрутка, надо закурить. Если сигарета последняя, маршрутка придет еще до второй затяжки даже вопреки расписанию. 2. Нaдоели зима и снег? Не надо переезжать. Достаточно. . .	Перемещение выделенных строк ТЧ из одного документа в другой Maks 31.03.2026 Реализация из решения ниже выполнена на примере нетипового документа "ВыдачаОборудованияНаСпецтехнику" с единственной табличной частью "ОборудованиеИКомплектующие" разработанного в конфигурации КА2. . . .	Functional First Web Framework Suave DevAlt 30.03.2026 Sauve. IO Апнулись до NET10. Из зависимостей один пакет, работает одинаково хорошо как в режиме проекта так и в интерактивном режиме. из сложностей - чисто функциональный подход. Решил. . .	Автоматическое создание документа при проведении другого документа Maks 29.03.2026 Реализация из решения ниже выполнена на нетиповых документах, разработанных в конфигурации КА2. Есть нетиповой документ "ЗаявкаНаРемонтСпецтехники" и нетиповой документ "ПланированиеСпецтехники". В. . .
Настройка движения справочника по регистру сведений Maks 29.03.2026 Решение ниже реализовано на примере нетипового справочника "ТарифыМобильнойСвязи" разработанного в конфигурации КА2, с целью учета корпоративной мобильной связи в коммерческом предприятии. . . .	Автозаполнение реквизита при выборе элемента справочника Maks 27.03.2026 Программный код из решения ниже на примере нетипового документа "ЗаявкаНаРемонтСпецтехники" разработанного в конфигурации КА2. При выборе "Спецтехники" (Тип Справочник. Спецтехника), заполняется. . .	Сумматор с применением элементов трёх состояний. Hrethgir 26.03.2026 Тут. https:/ / fips. ru/ EGD/ ab3c85c8-836d-4866-871b-c2f0c5d77fbc Первый документ красиво выглядит, но без схемы. Это конечно не даёт никаких плюсов автору, но тем не менее. . . всё может быть. . .	Автозаполнение реквизитов при создании документа Maks 26.03.2026 Программный код из решения ниже размещается в модуле объекта документа, в процедуре "ПриСозданииНаСервере". Алгоритм проверки заполнения реализован для исключения перезаписи значения реквизита,. . .

@XSasha 1 / 1 / 1 Регистрация: 19.09.2018 Сообщений: 59

	Представление графа в Java 24.02.2020, 21:45. Показов 12850. Ответов 4 Метки arraylist, граф, матрица смежности (Все метки) Всем привет. У меня есть 2 вопроса. Может кто сталкивался с представлением графа в java: 1) Подскажите, как представить взвешенный граф в виде матрицы смежности. Ну то есть я понимаю, что двумерный массив должен быть, но он мне нужен ещё и динамический, потому что в моей программе пользователь сам добавляет вершины и рёбра (причём в строковом виде, что неприятно, ведь индексы матрицы должны быть числами). Думал как в С++ через вектор векторов сделать, но тут ArrayList, и я не знаю как с ним. 2) Тот же самый граф, но в виде списка смежности. Этот самый список я реализовал как HashMap<String, List<String>>, но это только для невзвешенного подходит, как веса сюда добавить не знаю. Будет круто, если кинете какие-нибудь кусочки кода. 0

@xoraxax 3639 / 2971 / 918 Регистрация: 05.07.2013 Сообщений: 14,220
	24.02.2020, 23:07
	Создай класс edge, в котором будет вес и ссылка на следующую вершину. И гуглить научись - примеров навалом 1

@XSasha 1 / 1 / 1 Регистрация: 19.09.2018 Сообщений: 59
	25.02.2020, 01:59 [ТС]
	xoraxax и Сет, а по матрице смежности что скажете? 0