[THEG] Theorie des graphes (2)

BFS / DFS

Representation des graphes

Representation mathematique

Representation traditionnelle:

: ensemble des sommets
: ensemble des aretes

Interdit les doublons
Ne peut pas representer tous les graphes

Exemple:







G



A

A



B

B



A->B





A->B





C

C



A->C





B->C





D

D



B->D





B->D





C->D





Si le graphe est non-oriente :


Representation sur machine

Sur machine, on a plusieurs facons de representer un graphe :

Cout des operations sur les graphes

Representation Tester Trouver Cout de la boucle
edges = liste(paire())
Liste d’adjacence (retourne la liste)
Matrice d’adjacence
/* Cout de la boucle */
for x in V : 
    for y in succ(x): // Cout de cette ligne pour tout x
        // ...

:::info Notes :

Parcours d’un graphe

DFS (Depth First Search)







G



0

0



1

1



0--1




2

2



0--2




1--2




5

5



1--5




3

3



2--3




3--5




4

4



5--4










G



0

0



1

1



0->1


15



2

2



0->2


2



1->0


6



1->2


7



5

5



1->5


8



2->0


13



2->1


14



3

3



2->3


3



3->2


12



3->5


4



5->1


5



5->3


11



4

4



5->4


9



4->5


10



Decouverte d’un nouveau succ : forme un arbre couvrant si le graphe est connexe
Decouverte d’un succ connu


BFS (Breadth-First Search)







G



0

0



1

1



0->1


3



2

2



0->2


2



1->0


9



1->2


6



5

5



1->5


7



2->0


5



2->1


8



3

3



2->3


4



3->2


12



3->5


13



5->1


14



5->3


10



4

4



5->4


12



4->5


15




Code

def adjlist(n, edges):
    succ = [[] for i in range(n)]
    for (a,b) in edges:
        succ[a].append(a)
        succ[b].append(b)
    return succ
    
def dfs(n, edges, start):
    succ = adjlist(n, edges)
    seen = set()
    def rec(x):
        if x in seen:
            return
        print(x)
        for y in succ[x]:
            rec(y)
        rec(start)
def dfsi(n, edges, start):
    succ = adjlist(n, edges)
    seen = set()
    todo = [start]
    while(todo):
        x = todo.pop()
        if x not in seen:
            seen.add(x)
            print(x)
            for y in succ[x]:
                todo.append(y)

Parcours profondeur :

def bfsi(n, edges, start):
    succ = adjlist(n, edges)
    seen = set()
    todo = [start]
    while(todo):
        x = todo.pop(0)
        if x not in seen:
            seen.add(x)
            print(x)
            for y in succ[x]:
                todo.append(y)

Cycle Eulerien

Cycle : Chemin qui revient a son point de depart

Cycle Eulerien : Cycle qui visite toutes les aretes une fois exactement

Un graphe est eulerien ssi il existe un cycle eulerien

Conditions necessaires:

graph G
{
    layout=circo
    A--B
    A--C
    C--B
    C--D
    D--B
    B--E
    D--E
    D--F
    E--F
    E--G
    C--G
    H
}
A : ABCA
B : BDCGEB
D : DEFD

|ABDEFDCGEBC|A

Algorithme

  1. Choisir un sommet qui touche une arete
  2. Faire un DFS “sans backtrack” depuis ce sommet X. On s’axe necessairement sur X
  3. Chercher sur le cycle construit des sommets avec aretes non vues
  4. Repeter 3 jusqu’a ce qu’on ait vu toutes les aretes