Un graphe orienté possède des arêtes avec une direction définie (A → B), tandis qu'un graphe non-orienté a des arêtes bidirectionnelles (A ↔ B). Cette distinction détermine comment les nœuds peuvent être traversés et influence directement les algorithmes applicables.
Utilité et avantages
Cette distinction permet de modéliser précisément des relations asymétriques (suivre quelqu'un sur Twitter) versus symétriques (amitié Facebook). Elle détermine la complexité des algorithmes de parcours et optimise la représentation mémoire selon le type de relation à modéliser.
Exemple d'utilisation
Graphe orienté : Système de navigation GPS où les rues à sens unique créent des chemins directionnels. Une route de A vers B n'implique pas forcément un retour de B vers A.
Graphe non-orienté : Réseau social d'amis où si Alice est amie avec Bob, alors Bob est automatiquement ami avec Alice. La relation est mutuelle par nature.
Implémentation
# Graphe orienté - liste d'adjacence
graphe_oriente = {
'A': ['B', 'C'], # A peut aller vers B et C
'B': ['C'], # B peut aller vers C
'C': [] # C ne va nulle part
}
# Graphe non-orienté - chaque arête est dupliquée
graphe_non_oriente = {
'A': ['B', 'C'], # A connecté à B et C
'B': ['A', 'C'], # B connecté à A et C
'C': ['A', 'B'] # C connecté à A et B
}Contexte technique
Présent dans tous les langages supportant les structures de données complexes. Les bibliothèques comme NetworkX (Python), JGraphT (Java), ou Boost Graph Library (C++) proposent des implémentations optimisées. Les bases de données orientées graphe (Neo4j, Amazon Neptune) distinguent explicitement ces deux types.
Termes liés: [Matrice d'adjacence], [Liste d'adjacence], [Parcours en profondeur], [Algorithme de Dijkstra]
