{
 "cells": [
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "\n",
    "\n",
    "# Creating a dictionary to store the adjacency list for each city\n",
    "graph = {\n",
    "    'Arad': ['Zerind', 'Sibiu', 'Timisoara'],\n",
    "    'Zerind': ['Arad', 'Oradea'],\n",
    "    'Oradea': ['Zerind', 'Sibiu'],\n",
    "    'Sibiu': ['Arad', 'Oradea', 'Fagaras', 'Rimnicu Vilcea'],\n",
    "    'Timisoara': ['Arad', 'Lugoj'],\n",
    "    'Lugoj': ['Timisoara', 'Mehadia'],\n",
    "    'Mehadia': ['Lugoj', 'Drobeta'],\n",
    "    'Drobeta': ['Mehadia', 'Craiova'],\n",
    "    'Craiova': ['Drobeta', 'Rimnicu Vilcea', 'Pitesti'],\n",
    "    'Rimnicu Vilcea': ['Sibiu', 'Craiova', 'Pitesti'],\n",
    "    'Fagaras': ['Sibiu', 'Bucharest'],\n",
    "    'Pitesti': ['Rimnicu Vilcea', 'Craiova', 'Bucharest'],\n",
    "    'Bucharest': ['Fagaras', 'Pitesti', 'Giurgiu', 'Urziceni'],\n",
    "    'Giurgiu': ['Bucharest'],\n",
    "    'Urziceni': ['Bucharest', 'Hirsova', 'Vaslui'],\n",
    "    'Hirsova': ['Urziceni', 'Eforie'],\n",
    "    'Eforie': ['Hirsova'],\n",
    "    'Vaslui': ['Urziceni', 'Iasi'],\n",
    "    'Iasi': ['Vaslui', 'Neamt'],\n",
    "    'Neamt': ['Iasi']\n",
    "}\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "#Implementing the BFS algorithm\n",
    "def bfs(graph, start, goal):\n",
    "    queue = [[start]]\n",
    "    visited = set()\n",
    "\n",
    "    while queue:\n",
    "        path = queue.pop(0)\n",
    "        current_node = path[-1]\n",
    "\n",
    "        if current_node == goal:\n",
    "            return path\n",
    "\n",
    "        elif current_node not in visited:\n",
    "            for neighbor in graph[current_node]:\n",
    "                new_path = list(path)\n",
    "                new_path.append(neighbor)\n",
    "                queue.append(new_path)\n",
    "\n",
    "            visited.add(current_node)\n",
    "            \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "print(bfs(graph, 'Mehadia', 'Bucharest'))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "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.9.7"
  },
  "vscode": {
   "interpreter": {
    "hash": "31f2aee4e71d21fbe5cf8b01ff0e069b9275f58929596ceb00d14d90e3e16cd6"
   }
  }
 },
 "nbformat": 4,
 "nbformat_minor": 4
}