# 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)