Я не понимаю, что такое список смежности и что такое очередь приоритетов. - Ява

Я немного смущен тем, что такое список смежности и что такое очередь приоритетов.

Я собираюсь составить список смежности с помощью Arraylist. Что меня смущает, так это то, что содержится в списке смежности.

Используется ли список смежности, чтобы показать, на что указывает?

Например, у вас есть следующие данные:

u v weight
1 4   6
2 5   7
3 7   1
1 3   2
1 2   5
2 2   9

Итак, для списка смежности это будет выглядеть примерно так:

1 --->4---->3---->2
2 --->5---->2
3 --->7

Где каждый одинаковый «u» (т. е. три единицы в столбце u) указывает на соответствующий «v»


java adjacency-list
person KoolAid    schedule 12.11.2013    source источник
comment
en.wikipedia.org/wiki/Adjacency_list, en.wikipedia.org/wiki/Priority_queue   -  person Oliver Charlesworth    schedule 13.11.2013

Ответы (2)


arrow_upward
1
arrow_downward

Список смежности узла в графе дает вам все узлы, которые являются соседями этого узла. По сути, список смежности — это способ узла сказать: «Я могу добраться до этих других узлов, начиная с себя» или «Вот узлы, к которым я подключен». Более конкретный пример: представьте себе город (назовем его Графвилль), в котором есть дороги, ведущие в соседние города. Тогда Graphville является узлом, и список всех городов, в которые можно добраться напрямую (т. е. не проезжая через другие города) из Graphville, будет в списке смежности Graphville.

Очередь с приоритетом — это структура данных, похожая на обычную очередь, за исключением того, что каждый элемент имеет связанный с ним «приоритет». Как правило, элементы с более высоким приоритетом обрабатываются раньше элементов с более низким приоритетом в очереди приоритетов.

person Vivin Paliath    schedule 12.11.2013
comment
Так, например, на этой картинке: upload.wikimedia.org/wikipedia /commons/0/03/ 3 точки на 10 и 3 точки на 8, поэтому, если бы я реализовал это с помощью массива, на третьей позиции в списке массивов, я бы получил 3 ----› 10 ----›8 - person KoolAid; 13.11.2013

arrow_upward
0
arrow_downward

В теории графов и информатике представление графа в виде списка смежности представляет собой набор неупорядоченных списков, по одному для каждой вершины графа. Каждый список описывает множество соседей своей вершины.

Означает, что он просто хранит соседей узла. Таким образом, мы можем хранить соседей в linkedList или Array или ArrayList.

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

В Java у вас есть PriorityQueue, PriorityBlockingQueue.

Из вики

person Trying    schedule 12.11.2013
comment
Под соседями узла вы подразумеваете все узлы, на которые указывает узел в ориентированном графе? - person KoolAid; 13.11.2013