Structures de données IFT-2000 Abder Alikacem Les graphes Semaine 5 Département dinformatique et de génie logiciel Édition Septembre 2009

Structures de donnéesIFT-2000

Abder AlikacemAbder Alikacem

Les graphes

Semaine 5

Département d’informatique et de génie logiciel

Édition Septembre 2009

Première partie

• Introduction• Nomenclature des graphes• Matrice de connectivité• Clôture transitive: algorithme de Warshall• Plus court chemin: algorithme de Floyd

4

25

3

1

Les graphes

Modélisent quoi au juste ?• cartes géographiques : réseaux routiers, de téléphonie, etc.• trajets d’autobus, de trains, d’avions, de commis voyageurs• circuits électriques, réseaux électriques• Gestion d’une ville (transport, feux tricolore, voies à sens unique

etc..)• Etc..

4

25

3

1

Graphe (orienté) G = (S, A)S ensemble fini des sommetsA S x S ensemble des arcs,

i.e., relation sur S

Graphe non orienté G = (S, A)A ensemble des arêtes, relation symétrique

S = { 1, 2, 3, 4, 5 }A = { (1, 2), (1, 3), (2, 3), (3, 2), (4, 4), (4, 5) }

1

2

3

4

5

1 4

2

3

S = { 1, 2, 3, 4 }A = { {1, 2}, {1, 3}, {1, 4}, {2, 4} }

Les graphes: définitions

Les graphes : définitions

• Graphe G (S,A), un graphe orienté (digraphe)• S = {1,2,3,4,5}, A = {1-5,2-1,2-4,4-1,4-3,5-4}

• adjacence d’un nœud V si 1 arc V-W y est relié• chemin suite d’arcs où le dernier d’une paire est le

premier de la paire suivante (chemins simples)• <2-4> et <2-1,1-5,5-4> = 2 chemins de 2 à 4

• ordre d’un chemin nombre d’arcs le composant

4

25

3

1


• ordre de sortie d’un nœud (arité de sortie)• ordre d’entrée d’un nœud (arité d’entrée) = degré d’un

sommet• circuit chemin où l’origine est égale au dernier nœud

• ex. : <4-1,1-5,5-4>• boucle circuit d’ordre 1• graphe acyclique graphe ne contenant aucun circuit• puits nœud dont l’arité de sortie est 0• source nœud dont l’arité d’entrée est 0• nœud indépendant arité d’entrée = arité de sortie = 0

4

25

3

1


Graphe connexe :• en oubliant le sens des flèches, un graphe est

connexe s’il existe un chemin entre toutes paires de nœuds

• sinon : graphe à composantes connexes

4

25

3

1

4

25

3

1

Graphe fortement connexe : en tenant compte du sens des flèches, un graphe est

fortement connexe s’il existe un chemin entre toutes paires de nœuds

Ce graphe comporte 5 composantes fortement connexes


Points d’articulation

Ce graphe non orienté est connexe, c'est-à-dire formé d'une seule composante.

Ce graphe contient quatre points d'articulation, c'est-à-dire un sommet qui, s'il est éliminé, “ casse ” le graphe en deux ou plusieurs morceaux.

Ces points d’articulation sont :

A qui déconnecte B H qui déconnecte I J qui déconnecte K G qui produit 3 composantes.

Un graphe qui ne possède pas de points d’articulation est appelé bi-connexe (ou 2-connexe)



à chaque arc valeur (numérique)

4

25

3

10.5

0.2

0.8

0.75 1

14

25

3

1type-de

mange

sur

saveurà-côté

près

à chaque arc valeur (nominale)

Graphe pondéré (valué)

Les graphes orientés et pondérés sont appelés des réseaux


• Graphe pondéré : à chaque arc valeur (nominale)• Graphe décoré (étiqueté) : à chaque nœud valeur

lasagne

chattapis

pepperoni

paillassontype-de

mange

sur

saveurà-côté

près

Opérations importantes

Connectivité • Existe-t-il un chemin entre V et W ?

• Quel est le chemin le plus court entre V et W ?

• avec chaque arc valeur de 1 ?• avec un graphe pondéré ?

4

25

3

1

4

25

3

1

4

25

3

1

•Est-ce qu’un graphe g’ est inclus dans un autre graphe g ?

Explorations Parcours en profondeur, en largeur Tri topologique Composantes fortement connexes, ...

Recherche de chemins Clôture transitive (algorithme de Warshall) Chemin de coût minimal (algorithme de Floyd, Dijkstra,

Bellman-Ford) ...

Arbres recouvrants : Algorithmes de Kruskal et Prim

Réseaux de transport Flot maximal (algorithme de Ford-Fulkerson)

Divers Coloration d'un graphe ...

Algorithmique des graphes

En général, il existe 2 manières pour mettre un graphe en mémoire:

Par chaînage Listes des successeurs

Dans une matrice Matrice de nœuds adjacents

Implantation

1

1

2

2 3123

1

1

22

2

3

28 35123

1

2 3

2

5

2

83

1

2 3

S = { 1, 2, 3 }A = { (1,1), (1, 2), (1, 3), (2, 1), (3, 2)}

Listes des successeurs

Exemple

S = { 1, 2, 3 }A = { (1,1), (1, 2), (1, 3), (2, 1), (3, 2)}

0 1 1M = 1 0 0 0 1 0

V = 0 8 53 0 2 0

M [ i, j ] = 1 ssi j adjacent à i

1

2 3

5

2

83

1

2 3

Matrices d’adjacences

Exemple


• graphe orienté

4

25

3

1

1

1 1

1 1

1

1 2 3 4 51

2

3

4

5

Matrice d’adjacence

• graphe non orienté

4

25

3

1

1

1 1

1 1

1

1 2 3 4 51

2

3

4

5 1

1 1

1

1

1


• arité de sortie

4

25

3

1

1

1 1

1 1

1

1 2 3 4 51

2

3

4

5

1

2

0

2

1


• arité d’entrée

1

1 1

1 1

1

1 2 3 4 51

2

3

4

52 0 1 2 1


• puits

1

1 1

1 1

1

1 2 3 4 51

2

3

4

5

1

2

0

2

1

4

25

3

1


• source

1

1 1

1 1

1

1 2 3 4 51

2

3

4

52 0 1 2 1


• boucle

4

25

3

1

1

1 1

1 1

1

1 2 3 4 51

2

3

4

5



• chemins de longueur 1 = A

4

25

3

1

1

1 1

1 1

1

1 2 3 4 51

2

3

4

5



• chemins de longueur 2 ?

4

25

3

1

1

1 1

1 1

1

1 2 3 4 51

2

3

4

5

1

1 1

1 1

1

1 2 3 4 51

2

3

4

5



• chemins de longueur 2 ?

4

25

3

1

1

1 1

1 1

1

1 2 3 4 51

2

3

4

5

1

1 1

1 1

1

1 2 3 4 51

2

3

4

5


1

1 1

1 1

1

1 2 3 4 51

2

3

4

5

1

1 1

1 1

1

1 2 3 4 51

2

3

4

5

1 2 3 4 51

2

3

4

5

4

25

3

1

Chemins de longueur 2

1

1 1

1 1

1

1 2 3 4 51

2

3

4

5

1

1 1

1 1

1

1 2 3 4 51

2

3

4

5

1 2 3 4 51

2

3

4

5

4

25

3

1 1

1 1 1

1

1 1

Chemins de longueur 2 = A2

1

1 1

1 1

1

1 2 3 4 51

2

3

4

5

1

1 1

1 1

1

1 2 3 4 51

2

3

4

5

1 2 3 4 51

2

3

4

5

4

25

3

1 1

1 1 1

1

1 1

xChemins de longueur 3

1

1 1

1 1

1

1 2 3 4 51

2

3

4

5

1 2 3 4 51

2

3

4

5

4

25

3

1

1 2 3 4 51

2

3

4

5

1

1 1 1

1

1 1

1 1

1 1

1

1

Chemins de longueur 3 = A3

Fermeture transitive des graphes

Définition

Soit G un graphe orienté de n noeuds.

Soit A la matrice de nœuds adjacents correspondant.

Soit Bn-1 = A + A2 + A3 … + An-1

la matrice P est appelée fermeture ou clôture transitive du graphe G (dans notre cas, on a une clôture par produits de matrices).

Complexité ?

Bn-1 P : matrice de booléens qui indique s’il existe un chemin entre toutes paires de nœuds

Exemple

graphe G graphe H

1 2

3

4

1 2

3

4

Fermeture transitive des graphes

H : la fermeture transitive de A.

Algorithme de Warshall{Soit A, un graphe orienté}

1. [Initialisation]P A

2. [Boucle sur tous les sommets intermédiaires]Pour k = 1, 2, ..., n répéter jusqu'à l'étape 4.

3. [Boucle sur les sommets de départ]Pour i = 1, 2, ..., n répéter l'étape 4.

4. [Boucle sur les sommets adjacents]Pour j = 1, 2, ..., n répéterPij Pij ou (Pik et Pkj)

5. [Fin de l'algorithme]Stop

Algorithme de Warshall

Complexité ?

P0 = 0 1 0 1 0 0 1 0 0 1 0 1 1 1 0 0

P1 =

P2 =

P3 =

P4 =

34

1 2

0 1 0 1 0 0 1 0 0 1 0 1 1 1 0 1

0 1 1 1 0 0 1 0 0 1 1 1 1 1 1 1

0 1 1 1 0 1 1 1 0 1 1 1 1 1 1 1

1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1

Algorithme deWarshall

34

1 2

34

1 2

34

1 2

34

1 2

pour k = 1 à n faire

pour i = 1 à n faire

pour j = 1 à n faire

C [i, j] MIN { C [i, j] , C [i, k] + C [k, j] } ;

k c

i b a

k j

MIN { a, b + c }Ck =

i ja

kb c

Algorithme de Floyd

P0 = 0 1 0 1 0 0 1 0 0 1 0 1 1 1 0 0

P1 =

P2 =

P3 =

P4 =

34

1 2 0 1 0 1 0 0 1 0 0 1 0 1 1 1 0 1

0 1 1 1 0 0 1 0 0 1 1 1 1 1 1 1

0 1 1 1 0 1 1 1 0 1 1 1 1 1 1 1

1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1

Warshall

P0 = 1 1 1 1 1 1 1

P1 =

P2 =

P3 =

P4 =

1 1 1 1 1 1 1 2 1 2 1 1 1 2 1 1 1 2 2

1 2 1 2 1 2 1 2 1 1 1 2 2

2 1 2 1 3 2 1 2 2 1 2 1 1 1 2 2

Floyd

P 1 =

P 2 =

P 3 =

P 4 =

0 1 0 1 0 0 1 0 0 1 0 1 1 1 0 0

1 1 1 0 0 1 0 1 1 1 1 0 0 1 1 1

0 2 1 2 1 1 1 0 0 2 1 2 1 2 1 1

2 3 2 1 0 2 1 2 2 3 2 1 1 3 2 2

1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1

2 1 2 1 3 2 1 2 2 1 2 1 1 1 2 2

C

A

L

C

U

L

M

A

T

R

I

C

I

E

L

Algorithme de Floyd{Soit A, un graphe orienté.}

1. [Initialisation]C A

2. [Boucle sur les sommets intermédiaires]Pour k = 1, 2, ..., n répéter jusqu'à l'étape 4.

3. [Boucle sur les sommets de départ]Pour i = 1, 2, ..., n répéter l'étape 4.

4. [Boucle sur les sommets adjacents]Pour j = 1, 2, ..., n répéterCij MIN (Cij , Cik + Ckj)

5. [Fin de l'algorithme]Stop

Algorithme de Floyd

Complexité ?

C0 = W =

9

240 78

1

0 1 8 0 4 7 0 9 0 2 0

C1 = 0 1 8 0 4 7 0 9 0 1 0

C2 = 0 1 5 8 0 4 7 0 9 0 1 5 0

C3 = 0 1 5 8 0 4 13 7 0 9 0 1 5 0

C4 = 0 1 5 8 13 0 4 13 9 7 0 9 0 1 5 0

34

1 2

Matrice des poids :

W [i,j] = 0 si i = jv((i,j)) si (i, j) A sinon

Algorithme de Floyd et les distances

C0 = W =

0 1 8 0 4 7 0 9 0 2 0

C1 = 0 1 8 0 4 7 0 9 0 1 0

C2 = 0 1 5 8 0 4 7 0 9 0 1 5 0

C3 = 0 1 5 8 0 4 13 7 0 9 0 1 5 0

C4 = 0 1 5 8 13 0 4 13 9 7 0 9 0 1 5 0

- 1 - 1 - - 2 - - 3 - 3 4 4 - -

P1 =

P2 =

P3 =

P4 =

P0 =

- 1 - 1 - - 2 - - 3 - 3 4 1 - -

- 1 2 1 - - 2 - - 3 - 3 4 1 2 -

- 1 2 1 - - 2 3 - 3 - 3 4 1 2 -

- 1 2 1 4 - 2 3 4 3 - 3 4 1 2 -

9

240 78

1

34

1 2

Matrice des prédécesseurs Pk [i, j] = prédécesseur de j sur un plus court chemin de i à j dont les sommets intermédiaires sont tous k

Algorithme de Floyd et les chemins

C4 = 0 1 5 8 13 0 4 13 9 7 0 9 0 1 5 0

P4 =

- 1 2 1 4 - 2 3 4 3 - 3 0 1 2 -

Exemple de chemin

distance de 2 à 1 = C4[2,1] = 13

P4[2,1] = 4 ; P4[2,4] = 3 ; P4[2,3] = 2 ;

2 34

49

10

9

240 7

8

1

34

1 2

Algorithme de Floyd

Deuxième partie

• Parcours d’un graphe par contagion (ou largeur)• Parcours d’un graphe par sondage (ou profondeur)• Description d’un graphe en terme de type abstrait• Implantation

4

2

5

3

1

De nombreux algorithmes relatifs aux graphes nécessitent une procédure qui permet l'examen systématique des noeuds et des arêtes (arcs) d'un graphe G donné, une et une seule fois.

La procédure consiste à classer les sommets en 3 catégories:

• La catégorie A des sommets déjà visités.• La catégorie B des sommets adjacents à ceux de la catégorie

A mais pas encore visités (sommets qui peuvent être atteints).• La catégorie C des sommets invisibles qui n'ont pas encore

été rencontrés du tout (qui ne peuvent pas être atteints depuis un sommet déjà visité).

Défilement d’un graphe

Les différentes variantes de parcours dépendront de la manière dont on fait passer les sommets de la catégorie C à la catégorie B et de la B dans la A.

On construit l'état initial en plaçant le sommet de départ dans la catégorie B et tous les autres dans la catégorie C.

On répète alors :

faire passer un sommet x de la catégorie B à la catégorie A; mettre dans la catégorie B tous les sommets de catégorie C

adjacents à x.

Marquer les nœuds (Petit-Poucet)

Il existe deux manières standard d'exécuter ces opérations: Parcours par contagion ou par largeur Breadth-First Search

ou BFS Parcours par sondage ou en profondeur(Depth-First Search

ou DFS)

Au cours de l'exécution de nos algorithmes, chaque noeud N de G sera dans l'un des trois états suivants :

STATUS = 1 : (Prêt) État initial du noeud N

STATUS = 2 : (Attente) Le noeud N est soit empilé, soit dans la file d'attente, en attente d'être traité.

STATUS = 3 : (Traité) Le noeud N a été traité.

Marquer les nœuds (Petit-Poucet)

Noter qu’au lieu de marquer les nœuds par 1, 2 ou 3, peut simplement le faireen utilisant un booléen:

•vrai : le nœud est soit traité soit en attente d’être traité (status =1 ou 2)•Faux: le nœud n’a pas été parcouru (status = 1)

A

BCF

D

J K

GE

Exemple

Défilement d’un graphe

Parcours par contagion

Questions • Est-ce que tout graphe peut être parcouru par

cet algorithme ?

4

2

5

3

1

4

2

5

3

1

• Comment modifier l’algorithme pour que tout graphe soit parcouru ?

• Comment est-ce que l’algorithme s’arrêtera ?

• Pourquoi est-ce que ça marche bien pour trouver le chemin le plus court ?

• Quelle est la complexité de l’algorithme de parcours par largeur?L’algorithme prend un temps O(n+m)

Parcours par sondage

Questions

• Peut-on parcourir tout un graphe avec ce type de parcours ?

• Est-ce que ce parcours peut être utilisé pour trouver le chemin le plus court ?

• Quelle est la complexité de l’algorithme de parcours en profondeur?

L’algorithme prend un temps O(n+m)

Spécifications de l’interface du type Graphe

Description en termes de types abstraits

1. ajouter un sommet à un graphe 2. ajouter un arc/arête à un graphe3. ôter un sommet du graphe et tous les arcs/arêtes associés4. ôter un arc/arête 5. consulter un sommet 6. voir si un chemin existe entre 2 sommets7. trouver le chemin le plus court (# arêtes/arcs, distance)8. trouver tous les chemins entre 2 sommets• Etc..

Implantation

Il existe deux principales méthodes de modélisation des graphes en tant que type abstrait:

les matrices et les listes dites de connectivité ou d'adjacence.

Le choix entre elles se fera en fonction de la densité du graphe. Par densité, on entend la proportion d'arcs effectifs par rapport au nombre maximum d'arcs ou d’arêtes possibles:

NbArcs / NbSommets2 dans le cas de graphe orienté.NbAretes / (NbSommets(NbSommets-1)/2) dans le cas d’un graphe non orienté

Interface

template <typename T>class Graphe {public:/** Constructeur (graphe vide)*/ Graphe(); /** Constructeur à partir des sommets et arcs/arêtes*/ Graphe(vector<T> sommets, vector<Arete> aretes); Graphe (const Graphe&); Graphe(const Graphe&g, const std::vector<T>&sommets); ~Graphe (); Graphe& operator = (const Graphe&); void ajouterSommet(const T& s); void ajouterArc (const T& s1, const T& S2); void enleverArc (const T& s1, const T& s2); void enleverSommet ( const T& s); bool sommetExiste(const T& s) const; int nbSommets() const; // etc... private: //…

class Arete{public: int u; int v; Arete(int u, int v) {this->u = u; this->v = v; }}

class Sommet{public: …getData(); void setData(..); //etc..

private: … data; int no; int tag; bool pres;}

Classe Graphe

template <typename T>class Graphe {public: //..private:

int nbSommets;T* sommets;

int **mat; //implémentation dans une matrice} // de sommets adjacents

4

25

3

1

Cas d’un graphe orienté

Implantation dans une matrice d’adjacence

Classe Graphe



int **mat; // trop de perte mémoire!!

}

Cas d’un graphe non orienté

4

25

3

1


Linéariser la matrice

Classe Graphe



int *mat; // tableau à une dimension

}


4

25

3

1


1

1 1

1 1

1

0

1

2

3

4 1

1 1

1

1

1

11 11 11

( i + 1 ) * i / 2 + j

STL : Standard Template Library

Conteneurs: En C++, une classe contenant un ensemble d’éléments d'un certain type est appelée conteneur. Ce sont donc eux qui contiendront les informations que l’on veut stocker.

Itérateurs: utilisés pour parcourir les items qui se retrouvent dans les conteneurs, ils jouent un peu le rôle de pointeurs sur des éléments d’un conteneur.

Algorithmes: utilisés pour faire des traitements sur les éléments qui se retrouvent dans les conteneurs.

http://www.sgi.com/tech/stl/

Conteneurs Séquentiels

vector: tableau dynamique - extensible

- accès direct en O(1)- insertions et retraits à la fin en O(1)- insertions et retraits lents au milieu

list: liste doublement chaînée- insertions et retraits n’importe où en O(1)

- accès au début et à la fin en O(1)- accès lent aux autres éléments

STL : Standard Template Library

http://www.sgi.com/tech/stl/

Liste (list) et vecteur (vector)

Méthodes communes à vector et listpush_back():Ajoute x à la fin du conteneur. pop_back(): Enlève le dernier objet du conteneurback(): Retourne l'objet situé à la fin du conteneurfront(): Retourne l'objet situé au début du conteneur

Pour les conteneurs de type list seulementpush_front(): Ajoute x au début du conteneurpop_front(): Enlève le premier objet du conteneur

Pour les conteneurs de type vector seulement

operator[] : Retourne l'objet situé à la position i du conteneurat (): Comme le précédent mais déclenche une exception out of range lorsqu'un indice est incorrect.resize(): Redéfini la taille du conteneurcapacity(): Retourne la capacité du conteneurreserve(): Redéfini la capacité du conteneu

Les itérateurs

Un itérateur peut être vu comme un pointeur sur un élément d’un conteneur.

Chaque conteneur fourni un type d’itérateur.

Exemple le type list<int> donne un itérateur de type :

list<int> :: iterator.

Tous les conteneurs offrent les mêmes fonctions de base permettant aux itérateurs d’accéder aux éléments:

begin() retourne un itérateur pointant au premier élément du conteneur

end() retourne un itérateur pointant après le dernier élément du conteneur

Les itérateurs

#include <list>#include <iostream> using namespace std;

int main( ) { list <int> list1;

for (int i = 1; i<=40; i++) list1.push_back(i+i);

list <int> :: iterator i; //reverse_iterator //const_iterator

for (i = list1.begin( ); i!=list1.end( ); i++) cout <<*i << “ “ ; return 0 ;}

Les principaux opérateurs sont * donnant accès à la valeur, ++ et -- pour incrémenter et décrémenter une valeur.

-Opérateur * : Retourne l’élément de la position courante

-Opérateur ++ : Fait pointer l’itérateur à l’élément suivant

-Opérateur == : Indique si 2 itérateurs pointent sur le même élément

-Opérateur = : Assigne un itérateur

Retour à la classe Graphe


vector<T> sommets; // Les sommets vector< vector<int> > voisins; // Les sommets adjacents

}


Utilisation de vector de la STL

Classe Graphe

template <typename T>class Graphe { public: //.. private:

private:class Noeud{ public:

T data; /* au lieu de T data, on peut avoir T* ou int */Noeud * suivant; /* chaînage des sommets adjacents */

};/* le noeud typique du graphe */int nbSommet; /* nombre de sommets dans le graphe */int nbSommetMax; /* nombre total possible de sommets */T * sommet; /* tableau représentant les sommets*/Noeud** listeSommet; /* les listes de sommets adjacents*/

}

Implantation dans une liste de sommets adjacents

2 3123

1

1

2

1

2 3

Classe Graphe


class Noeud { public: T data; //données

// dans un sommet list<int> voisins; };

vector<Noeud> listeSommets;}


Utilisation de vector et list de la STL

Classe Graphe



La liste des sommets adjacents

soufre de la même redondance que

nous avons rencontrer avec les matrices de sommets adjacents.

Classe Graphe


class AreteNode { public:

int sommet[2]; AreteNode * lien[2];

}; typedef AreteNode * AretePtr;

class Noeud { public: T data; AretePtr first; };vector<Noeud> listeSommets;

}


Solution: liste des arêtes

BB

4

2 3123

1

2 3

Laboratoire #5

template <typename T>class Graphe {public:

//Les méthodes publiques

private:

class Noeud { public:

T sommet; /*!< l'étiquette d'un sommet */Noeud * suivant; /*!< pour le chaînage dans les listes de noeuds adjacents */

};

int nbNoeud; /*!< nombre de sommets dans le graphe */ int nbNoeudMax; /*!< nombre total possible de sommets */ T * tableauSommet; /*!< tableau représentant les sommets (i.e. les étiquettes)*/ Noeud** listeNoeud; /*!< structure pour les listes de noeuds adjacents*/

};

1

1

2

Exercice

Gestion d’une seule file• insertion se fait selon la priorité• éléments toujours triés selon leur priorité

in

file

41 84 1in

file

11 44 8

Files prioritaires

Exercice

p1

pile

debutcpt

cpt

tab

suiv

nœud... en-tête(header)

114 4 3

Pile, modèle hybride

Documents

Structures de données IFT-2000 Abder Alikacem Les graphes Semaine 5 Département dinformatique et de génie logiciel Édition Septembre 2009