init: initial commit

1 files changed, 97 insertions, 0 deletions

diff --git a/THEG/Parcours.md b/THEG/Parcours.md
new file mode 100755
index 0000000..56503fc
--- /dev/null
+++ b/THEG/Parcours.md
@@ -0,0 +1,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)
\ No newline at end of file