Java Реализация списка смежности графа с направленными взвешенными ребрами

Я пытаюсь реализовать направленный взвешенный граф ребер в Java, используя списки смежности. Он состоит из массива с размером, равным количеству вершин, каждый элемент массива является LinkedList преемников каждого конкретного Vertex.

Я хочу добавить вес каждому ребру, я думал сделать это, добавив метку веса к каждому successor объекту в LinkedList, кроме того, я хочу добавить другие переменные для каждого Vertex для будущего использования. Если я захочу это сделать, мне придется создать новую структуру данных для вершин и отдельную структуру в виде списков смежности. Каким был бы эффективный дизайн для объединения обоих в единую структуру данных?


java graph adjacency-list linked-list
person Abubakar Siddique    schedule 28.10.2016    source источник

Ответы (1)


arrow_upward
2
arrow_downward

Вы должны представить свой граф как HashMap, где ключ — это метка вершин, а значение — объекты вершин.

HashMap<String,Vertex> graph = new HashMap<String,Vertex>();

Vertex — это класс, инкапсулирующий атрибуты вершин. Будет атрибут HashMap для смежных вершин с весами.

HashMap<Vertex,Integer> adjListWithWeights = new HashMap<Vertex,Integer>();

Вы можете добавить дополнительные функции и атрибуты к вашему графику с помощью класса Vertex.

person R. Mittal    schedule 28.10.2016