Liste d'adjacence de graphes Comment implémenter O (1) recherche de nœuds/vertex. Array?

Question

J'ai lu dans les spécifications des graphiques implémentés avec la liste d'adjacence que l'ajout d'arêtes est fait en temps constant. MAIS cela nécessiterait une recherche de nœud avec O (1). Je voudrais la meilleure performance possible. La question ici est quel type de données me donnerait cela. Hashmap a été considéré, le pire des cas avec hashmap est toujours O (n). Puis-je utiliser un tableau pour cela?

Les nœuds peuvent être de n'importe quel type de données, génériques. Cela pourrait-il être fait avec une fonction de hachage générant des valeurs d'index basées sur le nœud seul? Cela me donnerait O (1). Bien sûr, je peux juste capitaliser et utiliser LinkedList avec indexOf. Le temps constant est le meilleur.

Answer 1

Quelque chose avec une étape de hachage vous courez le risque de collision, donc le pire des cas (mais peu probable) est Omega (N).

La meilleure performance asymptotique garantie pour l'insertion et la récupération simultanées lorsque vous travaillez avec des listes est O (log N). Vous obtiendrez cela si vous stockez vos noeuds dans quelque chose comme un tas ou un arbre équilibré. Vous ne pouvez pas faire mieux sur les deux opérations car cela vous permettrait de violer le O (N log N) prouvable lié au tri.