Список смежности Java

Question

У меня возникли проблемы с пониманием того, как сканировать в списке смежности к графику. Я понимаю, как работают таблицы смежности и их отображение друг на друга, но я не понимаю, в каком типе данных их хранить. Мое назначение - взять входной файл, который сообщает число вершин G=(V,E) и дает ребра другим числам на графике.

Так, например:

3
010
101
110

так:

0 maps to 1
1 maps to 0
2 maps to 0
2 maps to 1

Оттуда я должен осуществить поиск дыхания и поиск глубины на них. Будет ли хэш-таблица моей лучшей ставкой?

Answer 1

Разница в использовании BFS и DFS заключается в том, в какой структуре данных вы храните данные: одна - "очередь", другая - "стек" (ваш ответ). Если вы используете список Java, вы можете получить их с начала или с конца, но вы также можете использовать "настоящий" стек и очередь.

Так что в вашем случае создайте список и сохраните в нем источник поиска.

Через некоторое время, пока у вас есть элементы в вашем списке, продолжайте.

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

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

Но у меня есть сомнения, если вы хотите знать, где хранить список смежности. Массив списков будет делать. Каждая вершина, вершина [i] имеет Список со всеми вершинами, с которыми она связана.