BFS / DFS
Representation traditionnelle:
: ensemble des sommets
: ensemble des aretes
Interdit les doublons
Ne peut pas representer tous les graphes
Exemple:
Si le graphe est non-oriente :
Sur machine, on a plusieurs facons de representer un graphe :
Representation | Tester | Trouver | Cout de la boucle |
---|---|---|---|
edges = liste(paire()) | |||
Liste d’adjacence | (retourne la liste) | ||
Matrice d’adjacence |
:::info Notes :
Decouverte d’un nouveau succ : forme un arbre couvrant si le graphe est connexe
Decouverte d’un succ connu
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 : 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 }