Article Discussion Modifier Historique Forums Salon IRC

Graphe

Un article de Games Creators Network.

Exemple de graphe orienté composé de 4 sommets.

Les graphes sont des structures de données informatique.

On définit généralement un graphe par le 2-uplet suivant :

S représente une liste finie de sommets,
A un ensemble fini de paires de sommets.

On note habituellement G = <S,A>.

Le graphe peut être également défini comme un triplet G = <S,A,C> où C est une fonction de R dans R appellée fonction de coût.

Un graphe peut être orienté ou non. Si le graphe est orienté, A représente un ensemble fini de paires ordonnées de sommets.

Sommaire

1 Types utilisés
- 1.1 C
- 1.2 CAML
2 Algorithmes sur les graphes
- 2.1 Connexité
- 2.2 Recherche du plus court chemin

[modifier] Types utilisés

[modifier] C

/* TYPE STATIQUE */
typedef struct s_graphe_s t_graphe_s;
typedef float             *t_mat_adj;

struct s_graphe_s {
   t_mat_adj      adj;
   int            estOriente;
   unsigned int   ordre;
};

t_graphe_s init_graphe(int ordre, int estOriente);
void libere_graphe(t_graphe_s g);
void affiche_graphe(t_graphe_s g);
void ajout_arc(t_graphe_s g, unsigned int src, unsigned int dest, float cout);
void ajout_arrete(t_graphe_s g, unsigned int src, unsigned int dest, float cout);

/* TYPE DYNAMIQUE */
typedef struct s_graphe_d t_graphe_d;
typedef struct s_sommet   *t_list_som;
typedef struct s_adj      *t_list_adj;

struct s_sommet {
   t_list_som   suiv;
   t_list_adj   prec, succ;
   unsigned int som;
};

struct s_adj {
   t_list_som   vsom;
   t_list_adj   suiv;
   unsigned int nbLiens;
   float        cout;
};

struct s_graphe_d {
   t_list_som   lsom;
   int          estOriente;
   int          ordre;
};