Choisir une structure pour des données sous forme de graphe

Problème

Vous avez des données sous forme de graphe et vous souhaitez connaître les structures de données les plus appropriées pour les stocker.

Solution

Un graphe peut être codé sous forme de structure contenant une liste chaînée des nœuds pères et une autre des nœuds fils :


typedef struct list_t 
{ 
  void *node; 
  struct list_t *next; 
  struct list_t *prev; 
} list_t; 
 
typedef struct node_t 
{ 
  void *data; 
  list_t *parent; 
  list_t *child; 
}
 

Les arbres sont un cas particulier de graphes où le nombre de parents est 0 pour le nœud dit racine, et 1 pour tous les autres. Plusieurs bibliothèques proposent une implémentation de structure d’arbre et de fonctions utiles pour travailler avec, en particulier glib et libxml2.

Discussion

Les graphes forment un outil très utile pour résoudre des problèmes mathématiques parfois complexes. Chaque problème donne lieu à la création d’outils particuliers. Nous indiquerons seulement ici que pour parcourir un graphe quelconque, nous choisissons un nœud et nous parcourons récursivement ses fils en marquant ceux que nous avons déjà vus. Pour parcourir un graphe orienté quelconque, inventez un nœud père de tous les nœuds n’ayant pas de nœud parent, puis parcourez les nœuds récursivement...

Pour consulter la suite, découvrez le livre suivant :
couv_EI3CACT.png
60-signet.svg
En version papier
20-ecran_lettre.svg
En version numérique
41-logo_abonnement.svg
En illimité avec l'abonnement ENI
130-boutique.svg
Sur la boutique officielle ENI
Précédent
Choisir une structure pour des données sous forme clé-valeur
Suivant
Coder un tableau dont l'index est une chaîne de caractères