Graphes

C

Nous allons utiliser des matrices d'adjacence pour implémenter des graphes en C. Voici le programme initial auquel il faudra ajouter des fonctions :

#include <stdio.h>
#include <stdbool.h>
#include <stdlib.h>

#define N 5

typedef int graphe_m[N][N];

int main() {
	graphe_m g = {{0,1,0,0,1},
				{0,0,1,0,0},
				{0,0,0,1,0},
				{0,0,0,1,1},
				{0,1,1,0,0}};
	return 0;
}

1) Dessiner le graphe implémenté ci-dessus. Est-il orienté ou non-orienté ?

2) Implémenter la primitive existe_arc

bool existe_arc(graphe_m g, int i, int j){
	return (g[i][j] == 1);
}

3) Implémenter la primitive ajouter_arc

void ajouter_arc(graphe_m g, int i, int j){
	g[i][j] = 1;
}

4) Implémenter la primitive ajouter_arete

void ajouter_arete(graphe_m g, int i, int j) {
	g[i][j] = 1;
	g[j][i] = 1;
}

5) Implémenter la primitive supprimer_arc

void supprimer_arc(graphe_m g, int i, int j) {
	g[i][j] = 0;
}

6) Implémenter la primitive supprimer_arete

void supprimer_arete(graphe_m g, int i, int j) {
	g[i][j] = 0;
	g[j][i] = 0;
}

7) Implémenter la primitive deg_entrant

int deg_entrant(graphe_m g, int j) {
	int d = 0;
	for (int i = 0; i < N; i++) {
		d = d + g[i][j];
	}
	return d;
}

8) Implémenter la primitive deg_sortant

int deg_sortant(graphe_m g, int i) {
	int d = 0;
	for (int j = 0; j < N; j++) {
		d = d + g[i][j];
	}
	return d;
}

9) Implémenter une procédure affiche_graphe qui affiche la matrice d'adjacence du graphe.

void affiche_graphe(graphe_m g) {
	for (int i = 0; i < N; i++) {
		for (int j = 0; j < N; j++) {
			printf("%d ", g[i][j]);
		}
		printf("\n");
	}
}

Les listes d'adjacence n'apportant pas d'intérêt particulier en C, nous utiliserons le langage OCaml pour cette implémentation.

OCaml

Nous allons utiliser ici des listes d'adjacence pour représenter un graphe. Nous avons besoin donc d'un tableau de listes d'entiers :

type graphe = int list array;;

let (g:graphe) = [|[1;4];[2];[3];[3;4];[1;2]|];;

10) Implémenter la primitive existe_arc

let existe_arc (g:graphe) i j = List.mem j g.(i);;

11) Implémenter la primitive ajouter_arc

let ajouter_arc (g:graphe) i j =
	if not (existe_arc g i j) then g.(i) <- j::g.(i);;

12) Implémenter la primitive supprimer_arc

let supprimer_arc (g:graphe) i j =
g.(i) <- List.filter ((<>) j) g.(i);;

13) Implémenter la primitive deg_sortant

let deg_s (g:graphe) i = List.length g.(i);;

14) Implémenter la primitive deg_entrant

let int_of_bool = function
|true -> 1
|false -> 0;;

let deg_e (g:graphe) j =
let s = ref 0 in
for i = 0 to (Array.length g -1) do
s := !s + int_of_bool (List.mem j g.(i))
done;
!s;;

15) Implémenter la primitive deg_sortant2 en utilisant une fonction somme qui fait la somme des éléments d'un tableau et la fonction Array.map qui applique une fonction à tous les éléments d'un tableau.

let somme t =
let s = ref 0 in
for i = 0 to Array.length t - 1 do
	s := !s + t.(i)
done;
!s;;

let deg_e2 (g:graphe) j =
	somme (Array.map (fun l -> int_of_bool (List.mem j l)) g);;

16) Implémenter une procédure affiche_graphe qui affiche les listes d'adjacence du graphe.