Module 4 : Parcours dans un graphe. 12/7/2006Parcours dans un graphe2 Plan du module Parcours en...

Module 4 : Parcours dans un graphe

12/7/2006 Parcours dans un graphe 2

Plan du module Parcours en profondeur Parcours en largeur Composantes connexes Recherche de cycles Tri topologique Bi-coloriage d’un graphe

12/7/2006 Parcours dans un graphe 3

Parcours en profondeur Utilise l’idée du backtracking Recherche exhaustive de toutes les

possibilités si possible Retour en arrière (backtrack) s’il n’y a

plus de possibilité d’avancement non explorée

12/7/2006 Parcours dans un graphe 4

Parcours en profondeur1. Marquer tous les nœuds comme « non

visités »2. Choisir le nœud de départ et le marquer

comme visité3. À partir de là, effectuer un chemin vers le

bas aussi long que possible en ne traitant que les nœuds non encore « visités » (parcours récursif)

4. Si tous les nœuds ne sont pas encore « visités », choisir un autre nœud « non visité » et recommencer à 3.

12/7/2006 Parcours dans un graphe 5

Parcours en profondeur

1/

u v w

x y z

12/7/2006 Parcours dans un graphe 6

Exemple (DFS)

1/ 2/

u v w

x y z

12/7/2006 Parcours dans un graphe 7

Exemple (DFS)

1/

3/

2/

u v w

x y z

12/7/2006 Parcours dans un graphe 8

Exemple (DFS)

1/

4/ 3/

2/

u v w

x y z

12/7/2006 Parcours dans un graphe 9

Exemple (DFS)

1/

4/ 3/

2/

u v w

x y z

12/7/2006 Parcours dans un graphe 10

Exemple (DFS)

1/

4/5 3/

2/

u v w

x y z

12/7/2006 Parcours dans un graphe 11

Exemple (DFS)

1/

4/5 3/6

2/

u v w

x y z

12/7/2006 Parcours dans un graphe 12

Exemple (DFS)

1/

4/5 3/6

2/7

u v w

x y z

12/7/2006 Parcours dans un graphe 13

Exemple (DFS)

1/

4/5 3/6

2/7

u v w

x y z

12/7/2006 Parcours dans un graphe 14

Exemple (DFS)

1/8

4/5 3/6

2/7

u v w

x y z

12/7/2006 Parcours dans un graphe 15

Exemple (DFS)

1/8

4/5 3/6

2/7 9/

u v w

x y z

12/7/2006 Parcours dans un graphe 16

Exemple (DFS)

1/8

4/5 3/6

2/7 9/

u v w

x y z

12/7/2006 Parcours dans un graphe 17

Exemple (DFS)

1/8

4/5 3/6 10/

2/7 9/

u v w

x y z

12/7/2006 Parcours dans un graphe 18

Exemple (DFS)

1/8

4/5 3/6 10/

2/7 9/

u v w

x y z

12/7/2006 Parcours dans un graphe 19

Exemple (DFS)

1/8

4/5 3/6 10/11

2/7 9/

u v w

x y z

12/7/2006 Parcours dans un graphe 20

Exemple (DFS)

1/8

4/5 3/6 10/11

2/7 9/12

u v w

x y z

12/7/2006 Parcours dans un graphe 21

Parcours en profondeur PROCEDURE dfs(VAR g : graph; v : integer); BEGIN IF NOT finished THEN BEGIN discovered[v] := true; process_vertex(v); FOR i := 0 TO g.degree[v]-1 DO BEGIN y := g.edges[v][i]; IF NOT discovered[y] THEN BEGIN dfs(g,y) END ELSE IF NOT processed[y] THEN process_edge(v,y); IF finished THEN exit END; processed[v] := true END END;

Extrait partiel du programme Pascal

12/7/2006 Parcours dans un graphe 22

Parcours en largeur

1. Marquer tous les nœuds comme « non visités »2. Choisir un nœud v de départ et le marquer « visité »3. À partir de v:

a) Visiter tous les nœuds non encore visités adjacents à vb) Visiter tous les nœuds accessibles depuis v en suivant 2 arêtesc) Visiter tous les nœuds accessibles depuis v en suivant n arêtesEn utilisant une file !

4. Si tous les nœuds n’ont pas encore été visités, choisir un nœud non encore visité et recommencer à 3.

12/7/2006 Parcours dans un graphe 23

Parcours en largeur Placer le nœud de départ dans la file Tant que la file n’est pas vide

soit n le premier nœud de la filetraiter nenlever n de la fileplacer tous les nœuds adjacents à n et non encore traités dans la file

Fin tant que

12/7/2006 Parcours dans un graphe 24

Parcours en largeur Une file est une structure de données

de type FIFO (First In First Out) Enqueue(x,q) insère l’item x à la fin de q Dequeue(q) renvoie et enlève l’item en tête

de la file Empty(q) indique si la file est pleine, ne

peut plus accepter d’ajouts Initialize_queue(q) crée une file vide

12/7/2006 Parcours dans un graphe 25

Parcours en largeur

0

r s t u

v w x y

Q: s 0

12/7/2006 Parcours dans un graphe 26

Exemple (BFS)

1 0

1

r s t u

v w x y

Q: w r 1 1

12/7/2006 Parcours dans un graphe 27

Exemple (BFS)

1 0

1 2

2

r s t u

v w x y

Q: r t x 1 2 2

12/7/2006 Parcours dans un graphe 28

Exemple (BFS)

1 0

1 2

2

2

r s t u

v w x y

Q: t x v 2 2 2

12/7/2006 Parcours dans un graphe 29

Exemple (BFS)

1 0

1 2

2 3

2

r s t u

v w x y

Q: x v u 2 2 3

12/7/2006 Parcours dans un graphe 30

Exemple (BFS)

1 0

1 2 3

2 3

2

r s t u

v w x y

Q: v u y 2 3 3

12/7/2006 Parcours dans un graphe 31

Exemple (BFS)

1 0

1 2 3

2 3

2

r s t u

v w x y

Q: u y 3 3

12/7/2006 Parcours dans un graphe 32

Exemple (BFS)

1 0

1 2 3

2 3

2

r s t u

v w x y

Q: y 3

12/7/2006 Parcours dans un graphe 33

Exemple (BFS)

1 0

1 2 3

2 3

2

r s t u

v w x y

Q:

12/7/2006 Parcours dans un graphe 34

Exemple (BFS)

1 0

1 2 3

2 3

2

r s t u

v w x y

BF Tree

12/7/2006 Parcours dans un graphe 35

Parcours en largeur PROCEDURE bfs(VAR g : graph; start : integer); VAR q : queue; { queue of vertices to visit } BEGIN FOR i := 0 TO g.nvertices-1 DO BEGIN processed[i] := false; discovered[i] := false; END;

init_queue(q); enqueue(q, start); discovered[start] := true;

WHILE NOT empty(q) DO BEGIN v := dequeue(q); process_vertex(v); processed[v] := true; FOR i := 0 TO g.degree[v]-1 DO BEGIN IF NOT discovered[g.edges[v][i]] THEN BEGIN enqueue(q,g.edges[v][i]); discovered[g.edges[v][i]] := true; END; IF NOT processed[g.edges[v][i]] THEN process_edge(v,g.edges[v][i]) END END END;

Extrait partiel du programme Pascal

12/7/2006 Parcours dans un graphe 36

DéfinitionsChemin (de longueur n): Une séquence de

nœuds v0, v1, …, vn avec une arête de vi à vi+1 pour chaque 0 <= i < n.

Un chemin est simple si tous les nœuds dans le chemin sont distincts.

Un cycle est un chemin de longueur 1 ou plus reliant un nœud vi à lui même.

Un cycle est simple si le chemin est simple, sauf que les premiers et derniers nœuds sont les même.

12/7/2006 Parcours dans un graphe 37

Composantes connexes Une composante connexe d’un graphe

non orienté est l’ensemble maximal de nœuds tel qu’il existe un chemin entre toutes les paires de nœuds de cet ensemble

Elles se déterminent par un parcours (ici DFS)

12/7/2006 Parcours dans un graphe 38

Composantes connexes c := 0; FOR i := 0 TO g.nvertices-1 DO IF NOT discovered[i] THEN BEGIN c := c+1; write('Component ',c,': '); dfs(g,i); writeln END

12/7/2006 Parcours dans un graphe 39

Recherche de cycles Une arête arrière (u,v) est telle que v

est un père de u dans l’arbre DFS construit pour un graphe.

Toute arête arrière allant de u vers son père v crée un cycle dans le chemin de v à u.

12/7/2006 Parcours dans un graphe 40

Recherche de cycles PROCEDURE process_edge(x,y : integer); BEGIN IF parent[x] <> y THEN BEGIN write('Cycle from ',y, ' to ', x, ' : '); find_path(y,x); writeln { finished := true} END END

12/7/2006 Parcours dans un graphe 41

Recherche de cycles PROCEDURE find_path(start, endv : integer); BEGIN IF (start = endv) OR (endv = -1) THEN write(start:3) ELSE BEGIN find_path(start, parent[endv]); write(endv:3) END END;

12/7/2006 Parcours dans un graphe 42

Tri topologique Le tri topologique d'un graphe orienté

sans circuit est une numérotation des sommets dans laquelle les descendants d'un sommet de numéro k sont nécessairement de numéro supérieur à k.

12/7/2006 Parcours dans un graphe 43

Topological Sort: DFS

F

C

G A B

D E

H Un ordre topologique: C G B A D E F H8

32

1

7

65

4

12/7/2006 Parcours dans un graphe 44

Tri topologique Soit le graphe orienté acyclique suivant

12/7/2006 Parcours dans un graphe 45

Tri topologique La table indique pour chacun des

nœuds (1 à 6) le nombre d’arêtes entrantes (indegree) 1 0

2 1

3 3

4 3

5 2

6 0

12/7/2006 Parcours dans un graphe 46

Tri topologique

1 0

2 1

3 3

4 3

5 2

6 0

1 6file

12/7/2006 Parcours dans un graphe 47

Tri topologique La valeur en tête de file est enlevée (ici

1). La valeur indegree de chaque nœud

adjacent au nœud enlevé de la file est décrémentée de 1. Le(s) nœud(s) dont l’indegree passe à 0 sont mis dans la file (ici 2).

12/7/2006 Parcours dans un graphe 48

Tri topologique

1 0

2 0

3 3

4 2

5 2

6 06 2file

Résultat1

12/7/2006 Parcours dans un graphe 49

Tri topologique

1 0

2 0

3 2

4 2

5 1

6 02file

Résultat1, 6

12/7/2006 Parcours dans un graphe 50

Tri topologique

1 0

2 0

3 1

4 1

5 0

6 05file

Résultat1, 6, 2

12/7/2006 Parcours dans un graphe 51

Tri topologique

1 0

2 0

3 0

4 1

5 0

6 03file

Résultat1, 6, 2, 5

12/7/2006 Parcours dans un graphe 52

Tri topologique

1 0

2 0

3 0

4 0

5 0

6 04file

Résultat1, 6, 2, 5, 3

12/7/2006 Parcours dans un graphe 53

Tri topologique

1 0

2 0

3 0

4 0

5 0

6 0file

Résultat1, 6, 2, 5, 3, 4

12/7/2006 Parcours dans un graphe 54

Tri topologique La file est vide est le résultat du tri

topologique est 1, 6, 2, 5, 3, 4

12/7/2006 Parcours dans un graphe 55

Tri topologique compute_indegrees(g, indegree); init_queue(zeroin); FOR i := 0 TO g.nvertices-1 DO IF indegree[i]=0 THEN enqueue(zeroin,i);

j := 0; WHILE NOT empty(zeroin) DO BEGIN x := dequeue(zeroin); sorted[j] := x; j := j+1; FOR i := 0 TO g.degree[x]-1 DO BEGIN y := g.edges[x][i]; indegree[y] := indegree[y] - 1; IF indegree[y] = 0 THEN enqueue(zeroin,y) END END;

Extrait partiel du programme Pascal

12/7/2006 Parcours dans un graphe 56

Bi-coloriage d’un graphe Énoncé:

Réalisez un programme Pascal qui indique s’il est possible de repeindre n gares d’un réseau ferré de manière à ce que deux gares reliées directement ne soient jamais peintes de la même couleur.

On ne dispose que de deux couleurs.

12/7/2006 Parcours dans un graphe 57

Bi-coloriage d’un graphe In 1976 the ``Four Color Map Theorem" was proven with the

assistance of a computer. This theorem states that every map can be colored using only four colors, in such a way that no region is colored using the same color as a neighbor region. Here you are asked to solve a simpler similar problem. You have to decide whether a given arbitrary connected graph can be bicolored. That is, if one can assign colors (from a palette of two) to the nodes in such a way that no two adjacent nodes have the same color. To simplify the problem you can assume:

no node will have an edge to itself. the graph is nondirected. That is, if a node a is said to be

connected to a node b, then you must assume that b is connected to a.

the graph will be strongly connected. That is, there will be at least one path from any node to any other node.

12/7/2006 Parcours dans un graphe 58

Bi-coloriage d’un graphe Input 

The input consists of several test cases. Each test case starts with a line containing the number n ( 1 < n < 200) of different nodes. The second line contains the number of edges l. After this, l lines will follow, each containing two numbers that specify an edge between the two nodes that they represent. A node in the graph will be labeled using a number a (0≤a<n).

An input with n = 0 will mark the end of the input and is not to be processed.

Output  You have to decide whether the input graph can be

bicolored or not, and print it as shown below.

12/7/2006 Parcours dans un graphe 59

Bi-coloriage d’un graphe Sample Input 

3 3 0 1 1 2 2 0 9 8 0 1 0 2 0 3 0 4 0 5 0 6 0 7 0 8 0

Sample Output  NOT BICOLORABLE. BICOLORABLE.

12/7/2006 Parcours dans un graphe 60

Bi-coloriage d’un graphe Problème 10004 http://online-judge.uva.es/problemset/