Quelle est la façon la plus efficace de stocker un graphique non dirigé?

Question

Comme le dit le titre .. Quelle est la façon la plus efficace de stocker un graphique connecté en Java?

Par exemple, disons que j'ai plusieurs emplacements qui se connectent les uns aux autres de diverses manières et je dois traverser le graphique pour voir s'il est connecté. Toute aide / commentaire serait utile merci!

Answer 1

Une représentation souvent utilisée est une matrice (tableau bidimensionnel) indexée par tous les nœuds du graphique, où M[i,j] == true S'il y a un bord dirigé à partir du nœud i à j. Une variation du thème consiste à stocker la longueur / poids du bord entre les deux nœuds (où un bord manquant peut être représenté par la valeur -1).

Answer 2

Utiliser un matrice d'adjacence sans symétrie, représentant ainsi la direction au lieu d'une simple contiguïté.

Answer 3

En utilisant un incidence ou proximité Matrix fera l'affaire.

Si vous utilisez une matrice d'adjacence, un matrice clairsemée pourrait être efficace à utiliser si vous avez beaucoup de nœuds. Poulain Fournit une implémentation de matrice clairsemée. Informations tirées de ce poste donc.

Aussi, j'ai utilisé Jung Avant avec succès, vous voudrez peut-être jeter un coup d'œil sous le capot pour voir comment ils ont implémenté des graphiques dirigés.

Answer 4

Pour l'efficacité de la recherche - utilisez une matrice booléenne (true s'il y a un arc reliant les nœuds, faux si ce n'est pas le cas). Pour l'efficacité de la mémoire, définissez l'une de vos propriétés d'objet en tant que liste (dynamique) d'objets qui pointent vers. Remarque Ce dernier ne vous aidera que si vous avez beaucoup de nœuds dans votre graphique.

Answer 5

Est-ce que je manque quelque chose? Les données sont déjà un graphique, sérialisez simplement. Pour la question car la conversation écrite des matrices est complètement prématurée.