Discussion :

[Barbara_04]

Bonjours à tous!

Voilà, pour un devoir j'aimerais représenter un réseau de transport urbain à l'aide d'un graphe pondéré, sur lequel je devrais effectuer des opérations telles que l'ajout ou la suppression de sommets, mais aussi des recherches du chemin le plus court entre deux sommets, des recherches d'itinéraires, etc.

Dans un tutoriel sur la théorie des graphe, il est dit que pour représenter un graphe ayant de nombreux arcs, il vaut mieux utiliser une martice d'adjacence plutôt qu'une liste .

Cependant, il me semble qu'une liste occupe moins de place, en matière de mémoire, qu'une matrice.

Dans ce cas présent, quel vous semble être la meilleure représentation pour ce graphe, sachant que pour un réseau de transport, il y aura évidement un nombre important d'arcs ?

Je vous remercie d'avance pour vos suggestions .

[chtig]

Ca dépend pas mal de ce que tu veux représenter aussi ... Tu es sûr qu'il s'agit purement d'un graphe ? Je m'explique : souvent, dans un réseau de transport, on veut garder la notion de lignes, donc ce n'est plus vraiment un graphe puisque tous les arcs ne sont pas de même nature (et ce indépendamment du poids qui peut être par exemple le temps nécessaire entre deux noeuds).

L'autre question, c'est combien de noeuds tu as... Parce que la taille mémoire d'une matrice d'adjacence oui est plus élevée que celle des listes mais si on parle de 20 noeuds on s'en moque un peu ...

[Barbara_04]

Oui, ce sera un bien un graphe. Car en fait je vais définir les lignes par rapport aux stations et non pas aux arcs... .

En ce qui concerne le nombre de noeuds de mon graphe, par rapport au jeu d'essai que je dois effectuer, il y en aurais environ 250 .
C'est pour cela que j'hésite a utiliser une matrice, car ça commence à faire beaucoup.

En tout cas je te remercie d'avoir répondu.