В чем разница между реализацией неориентированного графа с помощью LinkedList и HashMap? Что лучше для обхода BFS / DFS?

Question

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

Я успешно внедрил DFS / BFS с LinkedList, но не могу заставить DFS работать с HashMaps.

С HashMaps я знаю, что порядок вставки не поддерживается, значит ли это, что вы не можете выполнять какие-либо обходы, такие как DFS? Если это так, разве это не противоречит цели использования HashTable, потому что тогда, как бы вы проходили правильно, не имея порядка вставки?

Как я могу проверить, посещается ли узел в HashMap? В настоящее время я создал новый класс Node с атрибутом посещения. С реализацией LinkedList мне не нужен новый класс, поэтому я напрямую использовал переменную типа <T>. Влияет ли необходимость создания нового класса на общую эффективность использования графиков?

Answer 1

HashMap - это подинтерфейс Collection, и каждая коллекция предоставляет метод iterator(), который позволит вам пройти по коллекции и посетить каждый элемент в ней.

Список смежности теоретически является Set, а не List, поскольку коллекция не должна содержать более одной копии каждого ребра. Это также означает, что порядок не важен.

HashMap использует HashSet для своего набора ключей, что идеально. Затем вы можете использовать объект, представляющий пару для каждого ключа, например, Pair<String, String>, или вы можете просто использовать строку, отформатированную как "A,B", где A и B - имена ваших вершин.

Если вы можете использовать предоставленные классы, лучше сделать это, чем создавать свои собственные. Библиотеки, представленные в JRE, написаны профессионалами. Вы вряд ли улучшите их производительность.