{
 "cells": [
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "96ce94bc",
   "metadata": {},
   "outputs": [],
   "source": [
    "def DFS_rec(G, s, parcouru):\n",
    "\n",
    "    print(s)\n",
    "    parcouru[s] = True\n",
    "    for u in G[s]:\n",
    "        if not parcouru[u]:\n",
    "            DFS_rec(G, u, parcouru)\n",
    "    \n",
    "def DFS(G, s):\n",
    "\n",
    "    parcouru = {u:False for u in G}\n",
    "    DFS_rec(G, s, parcouru)\n",
    "\n",
    "G = {0:[1,2], 1:[0,2], 2:[0,1]}\n",
    "DFS(G, 0)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "id": "63347514",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "on est dans DFS_rec(G, 0)\n",
      "on est dans DFS_rec(G, 0), on appelle DFS_rec(G, 2)\n",
      "on est dans DFS_rec(G, 2)\n",
      "on est dans DFS_rec(G, 2), on appelle DFS_rec(G, 1)\n",
      "on est dans DFS_rec(G, 1)\n",
      "DFS_rec(G, 1) retourne\n",
      "on est dans DFS_rec(G, 2), on appelle DFS_rec(G, 4)\n",
      "on est dans DFS_rec(G, 4)\n",
      "on est dans DFS_rec(G, 4), on appelle DFS_rec(G, 6)\n",
      "on est dans DFS_rec(G, 6)\n",
      "DFS_rec(G, 6) retourne\n",
      "DFS_rec(G, 4) retourne\n",
      "DFS_rec(G, 2) retourne\n",
      "on est dans DFS_rec(G, 0), on appelle DFS_rec(G, 3)\n",
      "on est dans DFS_rec(G, 3)\n",
      "DFS_rec(G, 3) retourne\n",
      "DFS_rec(G, 0) retourne\n"
     ]
    }
   ],
   "source": [
    "# avec des prints \n",
    "\n",
    "def DFS_rec(G, s, parcouru):\n",
    "\n",
    "    print(\"on est dans DFS_rec(G, \", s, \")\", sep=\"\")\n",
    "    parcouru[s] = True\n",
    "    for u in G[s]:\n",
    "        if not parcouru[u]:\n",
    "            print(\"on est dans DFS_rec(G, \", s, \"), on appelle DFS_rec(G, \", u, \")\", sep = \"\")\n",
    "            DFS_rec(G, u, parcouru)\n",
    "    print(\"DFS_rec(G, \", s, \") retourne\", sep=\"\")\n",
    "    \n",
    "def DFS(G, s):\n",
    "\n",
    "    parcouru = {u:False for u in G}\n",
    "    DFS_rec(G, s, parcouru)\n",
    "\n",
    "G = {0:[2,3], 1:[0], 2:[1,4], 3:[], 4:[6], 5:[4,6], 6:[], 7:[], 8:[7]}\n",
    "DFS(G, 0)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "id": "b24c7f1f",
   "metadata": {},
   "outputs": [],
   "source": [
    "from collections import deque\n",
    "\n",
    "def BFS(G, s):\n",
    "    \n",
    "    a_parcourir = deque([s])\n",
    "    vu = {u:False for u in G}\n",
    "    vu[s] = True\n",
    "        \n",
    "    while a_parcourir:\n",
    "        sommet = a_parcourir.popleft()\n",
    "        for u in G[sommet]:\n",
    "            if not vu[u]:\n",
    "                a_parcourir.append(u)\n",
    "                vu[u] = True\n",
    "        print(sommet)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "id": "8d85b201",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "{0: [2, 0], 1: [2, 1], 2: [2], 3: [2, 0, 3], 4: [2, 4], 5: [2, 4, 5], 6: [2, 4, 6], 7: [], 8: []}\n"
     ]
    }
   ],
   "source": [
    "from collections import deque\n",
    "\n",
    "def BFS_chemins(G, s):\n",
    "    \n",
    "    a_parcourir = deque([s])\n",
    "    vu = {u:False for u in G}\n",
    "    vu[s] = True\n",
    "    chemin = {u:[] for u in G}\n",
    "    chemin[s] = [s]\n",
    "        \n",
    "    while a_parcourir:\n",
    "        sommet = a_parcourir.popleft()\n",
    "        for u in G[sommet]:\n",
    "            if not vu[u]:\n",
    "                a_parcourir.append(u)\n",
    "                vu[u] = True\n",
    "                chemin[u] = chemin[sommet] + [u]\n",
    "                \n",
    "    return chemin\n",
    "\n",
    "\n",
    "G = {0:[1,2,3], 1:[2,0], 2:[0, 1, 4], 3:[0], 4:[2, 6, 5], 5:[4,6], 6:[4,5], 7:[8], 8:[7]}\n",
    "print(BFS_chemins(G,2))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "id": "d560c8ed",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "{0: [2, 3], 1: [2], 2: [0, 1, 4], 3: [0], 4: [2, 5, 6], 5: [4], 6: [4], 7: [], 8: []}\n"
     ]
    }
   ],
   "source": [
    "from collections import deque\n",
    "\n",
    "def BFS_arbre(G,s):\n",
    "\n",
    "    a_parcourir = deque([s])\n",
    "    vu = {u:False for u in G}\n",
    "    vu[s] = True\n",
    "    T = {u:[] for u in G}\n",
    "    while a_parcourir:\n",
    "        sommet = a_parcourir.popleft()\n",
    "        for u in G[sommet]:\n",
    "            if not vu[u]:\n",
    "                a_parcourir.append(u)\n",
    "                vu[u] = True\n",
    "                T[sommet].append(u) \n",
    "                T[u].append(sommet)   \n",
    "    return T\n",
    "\n",
    "G = {0:[1,2,3], 1:[0,2], 2:[0, 1, 4], 3:[0], 4:[2, 5, 6], 5:[4,6], 6:[4,5], 7:[8], 8:[7]}\n",
    "print(BFS_arbre(G,2))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 8,
   "id": "8ec970b9",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "{0: [1, 3], 1: [0, 2], 2: [1, 4], 3: [0], 4: [2, 5], 5: [4, 6], 6: [5], 7: [], 8: []}\n"
     ]
    }
   ],
   "source": [
    "def DFS_arbre_rec(G, s, parcouru, T):\n",
    "  \n",
    "    parcouru[s] = True\n",
    "    for u in G[s]:\n",
    "        if not parcouru[u]:\n",
    "            T[s].append(u)\n",
    "            T[u].append(s)\n",
    "            DFS_arbre_rec(G, u, parcouru, T)\n",
    "\n",
    "def DFS_arbre(G, s):\n",
    "    parcouru = {u:False for u in G}\n",
    "    T = {u:[] for u in G}\n",
    "    DFS_arbre_rec(G, s, parcouru, T)\n",
    "    return T\n",
    "    \n",
    "G = {0:[1,2,3], 1:[0,2], 2:[0, 1, 4], 3:[0], 4:[2, 5, 6], 5:[4,6], 6:[4,5], 7:[8], 8:[7]}\n",
    "print(DFS_arbre(G, 0))\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "d71e27e1",
   "metadata": {},
   "outputs": [],
   "source": []
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3 (ipykernel)",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.14.2"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 5
}