1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
|
# DFS
## Algorithme
On utilise une file.
```pcode
\begin{algorithm}
\caption{Quicksort}
\begin{algorithmic}
\PROCEDURE{Quicksort}{$A, p, r$}
\IF{$p < r$}
\STATE $q = $ \CALL{Partition}{$A, p, r$}
\STATE \CALL{Quicksort}{$A, p, q - 1$}
\STATE \CALL{Quicksort}{$A, q + 1, r$}
\ENDIF
\ENDPROCEDURE
\PROCEDURE{Partition}{$A, p, r$}
\STATE $x = A[r]$
\STATE $i = p - 1$
\FOR{$j = p$ \TO $r - 1$}
\IF{$A[j] < x$}
\STATE $i = i + 1$
\STATE exchange
$A[i]$ with $A[j]$
\ENDIF
\STATE exchange $A[i]$ with $A[r]$
\ENDFOR
\ENDPROCEDURE
\end{algorithmic}
\end{algorithm}
```
## Implémentation
```python
def adjlist(n, edges, directed=False):
lst = [[] for _ in range(n)]
for (s,d) in edges:
lst[s].append(d)
if not directed:
lst[d].append(s)
return lst
def dfs(n, edges, start):
succ = adjlist(n, edges)
seen = [False] * n
tree = []
def rec(s):
seen[s] = True
for d in succ[s]:
if not seen[d]:
tree.append((s,d))
rec(d)
print(s)
rec(start)
return tree
def dfsi(n, edges, start):
seen = [False] * n
todo = [(start,start)] # Pile d'arêtes
succ = adjlist(n, edges)
tree = []
while todo:
(x,s) = todo.pop() # sans (0)
if seen[s]:
continue
seen[s] = True
if x != s:
tree.append((x,s))
for d in succ[s]:
todo.append((s,d))
return tree
```
# BFS
```python
def bfs(n, edges, start):
seen = [False] * n
seen[start] = True
todo = [start] # File
succ = adjlist(n, edges)
tree = []
while todo:
s = todo.pop(0) # retire la 1re valeur
for d in succ[s]:
if not seen[d]:
seen[d] = True
todo.append(d)
tree.append((s,d))
return tree
```
# Circuits & chemins eulériens
**Conditions nécessaires et suffisantes** :
- Toutes les arrêtes du graphe doivent être dans la même composante
- Le nombre de sommets de degré impair doit être 0 (pour un cycle eulérien) ou 2 (pour un chemin eulérien)
|
