DataAlgo2020_004(BFS).ipynb

{
  "nbformat": 4,
  "nbformat_minor": 0,
  "metadata": {
    "colab": {
      "name": "DataAlgo2020-004(BFS)",
      "provenance": [],
      "authorship_tag": "ABX9TyO/t14G5NXsKG26YsjdRFI/",
      "include_colab_link": true
    },
    "kernelspec": {
      "name": "python3",
      "display_name": "Python 3"
    }
  },
  "cells": [
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "view-in-github",
        "colab_type": "text"
      },
      "source": [
        "<a href=\"https://colab.research.google.com/github/kameda-yoshinari/DataAlgo2020/blob/master/DataAlgo2020_004(BFS).ipynb\" target=\"_parent\"><img src=\"https://colab.research.google.com/assets/colab-badge.svg\" alt=\"Open In Colab\"/></a>"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "yRmydXneMgT8",
        "colab_type": "text"
      },
      "source": [
        "# 3.2. 幅優先探索\n",
        "\n",
        "ここでは幅優先探索(Breadth first search; BFS)について学ぶ．  \n",
        "幅優先探索によって，グラフに即した形で全頂点の列挙を行う．\n",
        "\n",
        "\n",
        "**いつもの約束**  \n",
        "１つのコードセルだけの実行は Ctrl + Enter．  \n",
        "エディタで「インデント幅（スペース）は4で表示」「行番号を表示」「インデントガイドを表示」．  \n",
        "内部では日本語はUTF-8で表現されている．\n"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "CdQdV_MJIlce",
        "colab_type": "text"
      },
      "source": [
        "# 準備\n",
        "\n",
        "インスタンスに接続し起動する．  \n",
        "下記の手順でGoogle Driveをマウントする．  \n",
        "マウント先に移動し，作業フォルダとする．  \n",
        "これによって，インスタンスがリセットされてもGoogle Drive内にファイルが保存されるようにする．"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "DMtqXRXJIPMR",
        "colab_type": "code",
        "colab": {}
      },
      "source": [
        "!echo \"Google Driveをマウントします\"\n",
        "from google.colab import drive \n",
        "drive.mount('/content/drive')"
      ],
      "execution_count": 0,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "SABzmuELIaj2",
        "colab_type": "code",
        "colab": {}
      },
      "source": [
        "!echo \"今回の作業用フォルダを作成しそこに移動します\"\n",
        "%cd /content/drive/My\\ Drive/202004_DataAlgo\n",
        "%mkdir -p DA2020_004\n",
        "%cd DA2020_004\n",
        "!ls\n",
        "!echo \"日本時間表示\"\n",
        "!rm /etc/localtime\n",
        "!ln -s /usr/share/zoneinfo/Japan /etc/localtime\n",
        "!date"
      ],
      "execution_count": 0,
      "outputs": []
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "QTSCrxILiWsC",
        "colab_type": "text"
      },
      "source": [
        "ここでは，グラフ3を利用する．  \n",
        "頂点数は8．無向グラフ．連結．\n"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "NINxYWNgOSaw",
        "colab_type": "text"
      },
      "source": [
        "![image.png](data:image/png;base64,iVBORw0KGgoAAAANSUhEUgAAAP8AAABtCAYAAABupreCAAAbEUlEQVR4Ae2dCdRVUxvH31KhyCoqVkiEopCSBvlEGaIMoZRGUUsaNK2FkKJQhorKUmSOTLU0qNBoaBEqaVCRUIlKkkz7W7/9fc+1733vPffcfW/3nM6791rn3nP2PufsZ//389/Pnk9BmTJlVPXq1dXJJ5+sTjzxxMAP5Fm2bJkKizvvvPNUz5491dChQ9WQIUPUPffck/eDeOVo2LChmjBhQljg0XJcdNFFqnv37hqjIPAx4wSnc889V40ZM0bL9s8//wSO1SeffKI5FpT+JOKDHIcffrgqgPhhcldccYVauHBhaERCsTdv3hwaee644w716KOPhkYeBLn00kvVxo0bQyMTBfXw4cO1PGEgP/p87bXXhgYfBIH3BVj8MLnLL788VOS/8MIL1erVqzVEf/zxh/5HofJ97N27V8fdv39/NWrUqDBlmWrevLn67LPPtEx///133rEx8wIhbrvtNvXAAw9oecJA/kWLFin0GvfXX3+pIDHSQiila/gFVPXD5MJG/mbNmqk1a9ZoiIJUJIm7b9++oSP/JZdcEqqm2u233x468rds2TJwHTJ5Du8d+U1Ekpyb5E8SnHcvR/70kIeZ/Omlz88djvw+cHbkTw+Ss/zeGFHtF8vvfWf+Qh35fWDtyJ8eJEd+b4wc+b3xiYWGuc0fEzLAE1ftTw++q/anx8hZ/vQYKWf504PkLL83RpGy/NLzTJLNc28I/IVGyfLnGhsQLAqWP1vcioLlByM5/DEr/i5ryy/jlIxZitu5c6ec6nFMwmwyMQrkJ90yngtWprPBxHw+KuQXjCRtXP/+++9yqf9N/YoLSHMRFfL/+eefikMccz1kvgd+nNvyzJr8RChCrVy5Uk/tbNKkierQoYN6/vnntay2QkWF/FJASiaNHz8+NutMMtPmPyrkl0IRwj/zzDPq9NNPV8cdd5xiUtWMGTM0NNwj92WCVVTIL4XfunXrVNeuXVXFihVV1apV1S233KJ++uknDQk8tDEoWZGfmN944w1VqlQpde+996rt27erSZMmqYKCAvXII49kkldx90aF/GTKrl271MSJE9Upp5yicWnXrl1cWm0uokJ+FBadOeusszQ2pUuX1v/oD0fnzp018Ysy+dGPjz/+WB166KHqtNNOU/Xq1YthxBqPLVu2WBGf91qTn4e/++47deSRR6q6devG6XDbtm3VAQccoFatWhXn7/ciCuSXtO7Zs0dPVWaqKQp9ww03SJD1f1TIDwB9+vTRSo2Cb9q0Sc+khPRSALz++utWOEXF8oMJBmPmzJkxHFgnUKFCBY3R448/HvPP9CQr8g8YMEAL8MQTT+h4pYqydu1aVbJkSetJDVEiv2QIFg6F7tixo3hZ/0eF/FRb27Rpo3788cdCWDB6AF6k1cZFhfwslvr88881BGYN6P7779f4sIDJ1lmTnyrtqaeeqgVYv369jl8WvWDtKJnKli2rtm3blrFsUSQ/mejIH68K1Azfeecd7Yli0wyQzqzJkydrvDAwNi4q5Je0wzezn2369OkanyVLluS/2j9//nxt3WnvC/lFUHr9aQ6g7NL5J2Gp/sl4KdmuueaaWGmX6v58+rNiTdJo07GCrN9++60jf4pMk7wn/0UHli5dqvHq3bt3iqcKe8t7CLn77rtj6/kL35l/H/ansJneCx6Qnn/SJ/pHh1/r1q11QqTGnWmqrC3/2LFjdeaUKFFCUc033Y4dO1SVKlV0eL9+/cyglOeScVSPa9eurSjxaU6MGzdO0Uue70PiRYYaNWqot99+W8su4KdMSIoA+kcoDDt16pTiDv/eUan2mykGV6yb1B7vvPNOjdfs2bPN2zzPRYe4iXbyVVddFagOmTqLPlOjzdQJJibBsfq1atVSu3fv1q8zwzJ5vzX52UkGZa5Zs2ZsyIGIyQCEad++vQ5n4wk/juc46L2sVq2aatWqlerVq5fq0aOHHtagpAviYAefY489Vr366qs6Gcho4xz506MmVo4769Spo/7zn//oh/xizn1iIVu0aKEaNWqkd2AKWofQW/TZhvxwiQKApvScOXP0pinwjoNhddJr66zJz/BVKkv266+/xiy/kD9dBkrGkRB2PFm+fLltmnL+HLvUbNiwQb83XTpSRe7InwqZf/1Fkal1Va5cWff+E+oXc1OHBg8erB577LF/Xx7w2YoVK6yr/eCClccAjR49WhdqUgBQ9YdvNs6a/FSHEYBhPqr5pkMYafNLby2ll99MjGKHnyO/qSGFz0U3KGQPOugg9dprr+mbsHxSKBR+KrVP1Dr8ElM6ZcoUPb8GDtrud2lNfsZfixcvrguAxDY/5K9UqZIOmzZtmpabDJQMTkxI4rUjfyIi8ddRbPOTQvSGyVBYfhwGIxO9MVGKIvnhjxyklX4NyC9DgWb6/Zxbk9+07lg105FpMgmBXm4cJbgjv+vwM/Uk8ZyefamqQ3r0yNZFlfxSIILLfffdp8nPzsA2zpr8REaHAyXP1KlTddwQHMfYIzP86OQQPx3g8yeKll/G+bt16+YThdS3RcXym8YAsorFT0w5I0CZuqiQ38SIAhE+SaFIGjGyNnNpwDMr8n/00Ufq4IMPVldffbXOGxFq4MCBulCQ3Vwzzbgokv+HH37QzST2BrApEE0Mo0J+SRO98WzXjmORDweTfag1Uliy6CdTFxXyk256+pO5Y445RjHTz9ZZk19KJD4GgPWfO3euluHdd99VxYoV07UCW6GiSH4KQnDikG3AbfGJCvlR6ptvvlljwsIVVqzxIYny5ctriyZ9Slu3bs0YqqiQ/6WXXlLlypVTF198sR7q+/TTT/WsyOuvv17XrMGQGoGNy5r8RPrcc8+pCy64QJfe559/vt5WmsJBCohMBYsC+SX9zF+nOstkJ6x+06ZNFTWjWbNmxXXeZIJRVMjPxClWpoEJX0ViXP6cc87R/5w3btxY3XXXXZlAE7s3KuRnbB9MxHCAC0PhTPQRZ8sza/JLxPLPlN558+bJpf63LZGiQH4AoHrPjLXffvstDhcyixKbcBuMokJ+v0rr9z4T5CiQ30w3tUWsfrZNRhOjnJDfFBLhROnpAzDDzIi9zqNAftItWCQSnDD8CE8M88JFwqJCfklPsn9wEYxsdCgK5AcXdCQx/bZ6k4hzzshPRolSyznXiYInCpDsOgrkJ10mDonpNLFKDEt3XZTID4Y2LirkJ/2iR+Ag1zaYJD6TE/InvjTb66iQP1scUj1fFMifKu1+/aNCfr/ptbnPkd8Ham7r7vQgua27vTGK1Nbd3knNLtRZfm/8nOX3xodQZ/nTY6Qt/0knnaTvlHaotNXz/S/iho387CYrX+mV9eb5xob4JG73ie5/57gnywf0KIyf6JbNPKQTL5ns+fATnmnys5giTI5pwQsWLAiNSJCfjRTD4lDsUaNGhUUcLQfLntleOiyOJb0y+w1CBe3YdFNmwgYti8R/8sknqwK2TH7zzTf1Ntxsxc15pge7izLLL9PnEu9nnQA759BGCotj2TLrqJEtUd58XyMDfRDspxAmx2SdESNGaIxsdQgs2dOPPfuzwRWM6IMYNmyYhigM5F+8eLGqXr161vgwMYrdjbLFB4yYml/AxwBYHpjN0aBBA73jDdMOs3kPz7J1M/O6pQoUhJJL3Ayt8E2CXKQrW1x4HjnY47B+/fpq8+bNGhoZ95X/IPAaOXJk1hixUIz56sxoyxZvdkmm9ij5GAQmZpzff/+96tKlS9bcYOcsCpFc6BLbyBeYQtqeU5J0797d9vFCz5ntokKBefBAaZBB2tl5iDKjKNiymRqSFABMqGIxDIXV/uwwRJns25cureYYebp794fwhx9+WBujXMlaIKWj7T+CvPDCC7pk49z2PfIcGQbxpADIVUIzeQ8yQHxkEAUS+YL+l3Swnpt2GysGcSKnhOf7P1tckJcNTmk24LJ9n+gQuITBZZse0kCeDxo0SCcn2/fxfE4sP6uPqNbkyiFYkMqcCGyu0pWr9yAfjnYtozVUK3FgJrjJPTpgP/mhui/kz1bkoHUoW/mTPQ/52dk4Vy6U5M9V4qL6HiE46aNPghqANAGweFJr2d/Sn0vy729p9yOvafn93J/uHkf+dAiFMJw2PgQX6863ACkAZEs1aa6EUHRPkRz5PeGJq/Z73+kv1JHfH06huUuqs2YVH+EY1+abB2HpA7ABzJHfGzVn+b3xKXKhYv1J+PDhw/XebNIHQA2AWoLt8up8g+nI7424I783PkUulBqA2cZ/8MEHdRNAdk6G+BQC+4Nz5PfOJUd+b3yKXKhYd7OdTx8Ac7elD4ACYn9wjvzeueTI741PkQ6lCSDNAAoA+gDYNhxH4SCH3BM2sBz5vXPEkd8bnyIfSjVfLD3z7ZkHIDUAwsxRgrCB5cjvnSOO/N74FOlQaf+bBQDz7k844QT1zTffaGykYAgjUI783rniyO+NT5EOleq8VP/lmgLg+OOPjzUBKAA45L6wgObI750Tjvze+LhQAwEhOV4UAPQByCgA7X+aAGGqCTjyG5mX5NSRPwkozqswAlj1xDb+I488omsAX3/9tX6AAkBqB4XfkH8fR35vzB35vfFxof9HQKr0Yv2F5BQAVatWjdUApPofBuAc+b1zwZHfGx8XmgIBKQwIfuihh3QBIJ2A0gSgpiCFRIrX7FNvR35veB35vfFxoSkQEILzj2NrMkYBpAkA8SUsxSv2ubcjvzfEjvze+LjQFAhQvYfcZjWfjUCPO+64WAFghqV4zT71duT3hteR3xsfF+oDAbMJQAFAH4DUACgg5Mh3E8CR3zvzHPm98XGhPhCA1OZEoDFjxugmwIYNG/TThAXR/nfk9848R35vfFyoDwSo3ksbX9r59AHQBFi7dq1+A/fk2znyeyPuyO+NjwvNEAGzCSAFgNQApI+AgiAfhYEjv3fmOfJ74+NCLRCA2FIDoAlAH8D69ev1m/DP10xAR37vzHPk98bHhWaIAJYfcptt/HHjxukmwFdffaXfRuGQj84/R37vzHPk98bHhWaIgFT7+TdJPnbsWP0FHbMAkPB9VRA48ntnniO/Nz4uNEsEhOC8hhpAlSpVYh/hlCaANBGyjKrQ4478hSCJ83Dkj4PDXeQaAar/Zht//PjxcaMAEJ8CYl84R35vVB35vfFxoVkiALE5ILlU76kB8BFNcxhQwrKMLu5xR/44OApdOPIXgsR57CsEILiQnBrAscceq6QPgMKBWoLZUZitHI783gg68nvj40JziAA1AJoA0sZ/4okndBNg9erVOhYhf66idOT3RtKR3xsfF5pDBCA/BDfb+U8++aRuAqxatUrHxD25co783kg68nvjk5NQafPyn0vlzoVwVMMhoxxSLc/Fu9O9Q+KiCUAfgBQAUjjIf7r3pAp35E+FzP/8Ib/7Sq83RlmHQniZ+JL1y/bRC0Q+IeQ+iibutVLg4DlhwgQ9DGg2AcxRgrgHfV448nsDxfcYBw8e7H1TBqE5+VDntGnTVPfu3TOINty3QigpALZu3aqnutLRFYaDDTh37doVVxXPB5pgIgWO1IYmTpyojj76aLVy5cqciNClSxc1Z86cnLwrTC+h0OT7idnoz7p161TPnj1V165d9byLbN7Fs3zSvaBbt26qQ4cOqn379oqSt127dhkfDRo00NVAm2cTn0EB5EOTQWWgaU0vuugidc4556gLL7xQNWvWTDVt2jTvB/HKwUc4XnzxRQ2NKWe+sJKCUQqAp59+Wp1yyimqY8eOWn9sdQg9qFy5ssY6UScyve7UqZNavHhxYBgl5sWKFSt0LUny0EaHePbcc8/VB+c27+AZkaFixYqq4JBDDlFY7qlTp6o33nhDvfnmmxkfM2fOVHPnzs34ucS4kKF69epq0aJFifgFdn3++eerL7/8MrD4EyPu3bu3YhPOoB3kl8LnggsuUA8//LDWo8Q8zeT6nXfeUTNmzMhKj9ChSy65RA0bNkxDJDIGidfChQvVpZdeGhp5EITl2wU1atQIEpdCcbdq1UotWLCgkH9QHlj8NWvW6OjF2gUhC73uuP79+yt23wnamcN8KDbV0rA42sW0j3FhID/G7MorrwyNPAjCh1wL+BGQACrIAzkuv/xyRUkZFmeSn7ZbEI48kbj79esXOPmRx7T8WNrPP/9cQxOk/hA37vbbb1d8qBQnfvoioB/I37JlSx27iVtA4uho48gfpCBm3GEjP20ksfymnEGd9+3bN3DyJ6Yd8i9btizRO7DrMJM/MFASInbkTwAk2aUjfzJU4v0c+ePxSLwyLX9iWFDXjvw+kHfkTw+SI783Ro783vjEQl21PwZF0hNX7U8KS5ynq/bHwZH0wln+pLDEezrLH49Hsitn+ZOh8q+fs/z/YuF55iy/JzzKWX5vfAh1lj89Rjmx/AxdyGEOq+Bn46JAfnAQTGSILhkWJl7JwpP5RZH84CCHrd6YWEWF/Db6YeLgdZ4T8iOgLPvknC/AMlPLVvCokB9MmAuP+/XXX/W8bnbC4WBCDCvibBQ9quSXSUzgBTZM0unTp09s9yAvRU4Miwr5weT333/XuoPOJDv4zJqNHuWM/BL5gw8+qAoKCtTdd9+t88OmAIgC+Uk8mAgutInBxTxYD2EqfKICp7qOKvlJL3PgWRtwxhlnqLvuuks99dRTehFTKixS+UeF/KSP/RNMvUk8P+KII9TOnTtTQZHSP2fkJ4aPP/5YlS5dWgtKIWDrokR+MGCuOhlWoUIFxWIKMqtSpUp6HYUNRlEhP4aBwlEMxHvvvadKliypevXqpX788UcbaGLPRIn8Z599tipTpoxePAU2cqAHrKisVauWrh3EEu/zJCfkJ65ffvlFNW7cWB166KGO/P8Hn7Y+yo2FnzRpktq9e7cuoXfs2KHx8plHhW6LCvnBRmo+8+bNU8WLF9fLVQsl2MIjKuRnkVKTJk0Uy7j37NlTCAk2VBk6dGghfz8eOSM/i3Fuu+02xYozrJyz/P+Df8qUKeq0005LWi1D+b06A1NlYFTILxZ/yZIl2rJVq1ZNsXeC+KdKvx//qJCf1babNm2KJRl9kX6k6dOna67Zrji1Jj8ZJJnE2nKW4VKK9+jRI2vyX3HFFer999+PJTjoExb2yJbVmchCSV2nTh1t0ajyX3bZZWr+/PmxV0jNIObh8wTy8z29MLnmzZtbz+1njTkG49VXX81Zku644w41YsSInL0v2xd98MEHsYU9Nu8SQ2HqzHXXXaebAjYGBBmsyS/VNTbdOOqoo2K7r9xwww1W5JfE8c/y0FmzZimqxz///LPavn173g8zXqpdy5cv13kmBZ6fDKREpj1GO9bspGFpp1g40pupY0nv8OHDA8VH8oQ84mAilGCUSXoYFSpWrJhq2LChfg+7A/ONgOeee0598803+lV+Mec+IcKAAQPUPffco9/5008/5V1/BB/+wQd9llV9meBj3iscIZ2//fabKlu2rHWVn/dak18ypHXr1mrkyJExGdliyKbaz/s4Nm7cqI488khtMbEIEI/NNII6kKF8+fKK3Wpwku5Ygj1OyCy222J4hk4/ahBSCFxzzTX6SRvys1adjGMDjaDxkXzBAMhXfT0gKRRE5y6Y0HbFklGwUTjiB+7PPvtsoWdSeYgO8X/eeecpmhFgJDIG+X/mmWfqpeqpZPfjT7rQF/7feustdeCBB6ovvvjCz6NJ77EmP2+jZAVkKZHwy4b8UqWhejx79mzdKUapSWdivg+GTiROlIYhKBzA+3XJ7h09enSsAJg8ebLfV8XdB0EYA0c+5DRlFZnz/U/BZmP5pcrP3nRm25adiigA6EA2/eOASLgAb7H8AwcO1FYRHILSITMP0OdcWH4xFm3atFE1a9ZMQCCzS2vyM6zHvm3btm2Li5FMJNMef/zxmL+UVjGPNCdRafOnSibEBSOsnihrqnuT+Uelzc8mkocddpjGgs4r00Hk+vXr6zC+FoxDj0T5zXuTnUetzS/pBxeaEocffrgaMmSITrpfTBJxsiY/7fKqVauqzp07680+27ZtqydnsLkkbbjatWvratzLL7+s40TJk1nCRIG4jso4f7K04UdvLTixd+LevXtT3ZbSPyq9/ez8QyHI8corrxRK70033aTDqHnhMiF/VHr7TVCE5NLLLzsmS/+bea+fc2vy09akzUHGQXb5Z6xWDvzIBBzk92vlok5+8GDsv169erFxbj+ZJfdEhfzMe2A0JBX5adcSVrduXZ30ok5+jCcH/WwMH2NE4JQUCqIffv+tyU87ih5rqv3mwRbgZBidUvjT4YUTwf0IFjXyS9r5F0cHED32Ni4q5CfttF3RF3b4xZkEp4ecMPo4cCZ+2sPjJ4qWn+TCJ2bRmjsTZ4KLCZk1+c2XmOd8uIMMYxtnWxcF8qPEDMewKANnZtBLL72k+0sYJjX9/eIVJfIz/o2+UAjgwE1qiCwQoxbJJKBMXVTJz6SfUqVKxT6Tliku5v05J7+M88vOqWZkfs+jQH7S2qJFCz3cxPcMxPGJKz5MsXTpUu0lii7hfv6jQn4p+KS2+OGHH8aST2dgiRIl9Kq+mGcGJ1ElP0PEzB3JhcsZ+SUjb7zxRl2Su+m9SrfNsGocfPGHfhLa+rLLLZjZtNeiRH7B4Nprr9VftIG01IxoFvHVHWpPNi6K5N+yZYvWJenlt8HFfCYn5JcMxIoxK4sxcQSVAsGM0M95FCw/aWcNP9OUb731Vt0Moopri4mJW1TIb6aJc7a6wnjQF2LOGbDBLIrk54OofLOBRT42mCTinTPy0/OYOORgU6VFwKiQPxFsrsHExtqb74oq+c00ClYouY2iR5H8Jj623DLfkRPyo8wQH4FEuckwzm0yLgrkB2RwkUNwAScbTMxMiyL5wUSw4pxD9MkGryiSPxEjUydsznNCfpuIvZ6JCvm90phNWBTJnw0eyZ6NIvmTpTMbP0d+H+i5rbvTg+S27vbGyG3d7Y1PLNRZ/hgUSU+c5U8KS5yns/xxcCS9iLP80tZKemcePcNGfveV3vSZj+U3v9Kb/ol9e0eYyU/fhk0/Rq4R0+RnF54wuTCTn4wLytEBhmO666hRo4ISI2m8LPQyh+eS3pRHzzCSn30KwuRCSX6W9C5cuDA0ONlu47WvEhBW8sueB/sq3Zm8d9CgQUpmmYbBytLmR6/D5FhZWsDqPEqBsBxsUyyz4MIAVqNGjfTsM8AKA0blypXT21yFARuRgU052I0nDPggAxix3z0uDOSnVsQS7rDggxxsL/df5N+7npPR7xwAAAAASUVORK5CYII=)"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "rz4_9z4rOQu4",
        "colab_type": "code",
        "colab": {}
      },
      "source": [
        "%%writefile graph3.h\n",
        "// 8 nodes, undirected, no-weight.\n",
        "#define N 8\n",
        "int edge[N][N] = {\n",
        "//   0 1 2 3 4 5 6 7\n",
        "\t{0,1,0,0,1,0,0,0}, // 0\n",
        "\t{1,0,0,0,0,0,1,0}, // 1\n",
        "\t{0,0,0,1,0,0,1,0}, // 2\n",
        "\t{0,0,1,0,0,0,0,1}, // 3\n",
        "\t{1,0,0,0,0,1,0,0}, // 4\n",
        " \t{0,0,0,0,1,0,1,0}, // 5\n",
        "\t{0,1,1,0,0,1,0,1}, // 6\n",
        "\t{0,0,0,1,0,0,1,0}  // 7\n",
        "};"
      ],
      "execution_count": 0,
      "outputs": []
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "SgrerkN-Ox0L",
        "colab_type": "text"
      },
      "source": [
        "# 幅優先探索の概要\n",
        "\n",
        "Rogueのようなダンジョン型RPGにおいて，最初の部屋（開始頂点）から近い部屋から制圧していくの幅優先探索である．慎重な戦略とも言える．\n",
        "\n",
        "より正確には，開始頂点からの道が近い頂点から先に列挙していく探索が幅優先探索である．ここで，全ての辺は同じ長さを持つとする．（道において同一頂点は高々１回しか現れないことに注意．）\n",
        "\n",
        "幅優先探索のアルゴリズムの記述においては，キュー(First-In-First-Out)を利用する．大雑把に言えば，開始頂点から近い頂点から調査を行って列挙していく．このとき，その頂点に隣接している未列挙頂点は後回しにする（キューに繋ぐ）．ある頂点について調査が終わった時，次に調査に取り掛かるのはキューに繋いだ中で一番古いものである（First-In-First-Out）．これは，後から繋いだものほど開始頂点から遠い頂点ということになるからである．\n",
        "\n",
        "参考までに，グラフG3について頂点0からBFSを実施した場合，幅優先による頂点列挙の結果は次のようになる．  \n",
        "ただし，同じ優先度の頂点が複数あったときは，番号の小さい方の頂点を選択するものとする．\n",
        "\n",
        "BFS result: 0 1 4 6 5 2 7 3"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "0_o0avWIHZqC",
        "colab_type": "text"
      },
      "source": [
        "# 幅優先探索プログラム\n",
        "\n",
        "**目標**\n",
        "\n",
        "キューを用いた幅優先探索によって，与えられたグラフの頂点を列挙する．\n",
        "\n",
        "**説明**\n",
        "\n",
        "開始頂点は指定されるものとする．  \n",
        "  \n",
        "キューは，スーパーのレジで人が並ぶのと同じものだと思えばよい．  \n",
        "キュー（行列）の先頭を head と呼ぶことにする．  \n",
        "キュー（行列）の末尾を tail と呼ぶことにする．  \n",
        "新しくオブジェクトを追加するときは，それをキューの末尾に繋ぐ．  \n",
        "キューに追加する操作を enqueueと呼ぶ．  \n",
        "（人が行列の最後尾に並ぶのと同じことである．）  \n",
        "キューから削除する操作を dequeueと呼ぶ．  \n",
        "（人が行列の先頭から進んでレジのところに移動するのと同じことである．）  \n",
        "\n",
        "**コード**\n",
        "\n",
        "下記の通り．  \n",
        "グラフが無向で連結である限り，幅優先探索は必ず成功する．  \n",
        "そのため，bfs()はvoidとしている．\n",
        "\n",
        "**備考**\n",
        "\n",
        "なし．"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "Sfxsc_02JNc1",
        "colab_type": "code",
        "colab": {}
      },
      "source": [
        "%%writefile bfs_simple_J.c\n",
        "// Breadth First Search.\n",
        "// 2020/05 kameda[at]ccs.tsukuba.ac.jp\n",
        "#include <stdio.h> // printf()\n",
        "#include \"graph3.h\"\n",
        "\n",
        "// 幅優先探索本体\n",
        "void bfs(int StartingRoom){\n",
        "\tint listed[N]; // 0 未, 1 済\n",
        "\tint queue[N];\n",
        "\tint qhead = 0; // queue head\n",
        "\tint qtail = 0; // queue tail\n",
        "    \n",
        "    int CurrentRoom;\n",
        "    int RoomToCheck;\n",
        "\n",
        "\tfor (RoomToCheck = 0; RoomToCheck < N; RoomToCheck++)\n",
        "\t\tlisted[RoomToCheck] = 0;\n",
        "\t\n",
        "\tprintf(\"幅優先探索を 頂点%d から開始します．\\n\", StartingRoom);\n",
        "    // StartingRoomをキューに追加する\n",
        "    queue[qtail] = StartingRoom;\n",
        "    qtail++;\n",
        "\n",
        "    // キューに追加したということは訪れる対象として計上（列挙）済みということ\n",
        "\tprintf(\"頂点 %d をこれ以降は列挙済として扱います．\\n\", StartingRoom);\n",
        "    listed[StartingRoom] = 1;\n",
        " \n",
        "    // キューに処理対象がある限り作業を継続\n",
        "\twhile (qhead < qtail) {\n",
        "\t\tprintf(\"現在のキュー： 長さ %d, 先頭の頂点は %d, 末尾の頂点は %d\\n\", qtail - qhead, queue[qhead], queue[qtail - 1]);\n",
        "    \t{int i; printf(\"現在のキュー： \"); for (i = qhead; i < qtail; i++) printf(\"%d \", queue[i]); printf(\"\\n\");}\n",
        "\n",
        "        // キュー先頭から１つ呼んで作業開始（キューからは削除）\n",
        "        printf(\"キュー先頭の頂点 %d をキューから外して処理を開始します．\\n\", queue[qhead]);\n",
        "\t\tCurrentRoom = queue[qhead];\n",
        "        qhead++;\n",
        "\n",
        "        // ※ここで何かしらの作業を行うのかも．\n",
        "\n",
        "        // 次にどの頂点を列挙していくか検討\n",
        "\t\tfor (RoomToCheck = 0; RoomToCheck < N; RoomToCheck++) {\n",
        "            if (edge[CurrentRoom][RoomToCheck] == 0) {\n",
        "\t\t\t\tprintf(\"  (頂点 %d にて) 頂点 %d は隣接していませんでした‥\\n\", CurrentRoom, RoomToCheck);\n",
        "            } else if (listed[RoomToCheck] != 0) {\n",
        "\t\t\t\tprintf(\"  (頂点 %d にて) 頂点 %d は隣接はしてますがすでに処理済でした‥\\n\", CurrentRoom, RoomToCheck);\n",
        "            } else {         \n",
        "\t\t\t\tprintf(\"  (頂点 %d にて) 頂点 %d は隣接でかつキューに繋いだことがないので、キューの最後尾に追加します。\\n\", CurrentRoom, RoomToCheck);\n",
        "                // RoomToCheckをキューに追加する\n",
        "\t\t\t\tqueue[qtail] = RoomToCheck;\n",
        "                qtail++;\n",
        "\n",
        "                // キューに追加したということは訪れる処理対象として計上（列挙）済みということ\n",
        "                printf(\"  (頂点 %d にて) 頂点 %d をこれ以降は列挙済として扱います．\\n\", CurrentRoom, RoomToCheck);\n",
        "\t\t\t\tlisted[RoomToCheck] = 1;\n",
        "\t\t\t}\n",
        "\t\t}\n",
        "\t}\n",
        "\tprintf(\"何も残っていないので幅優先探索を終了します．\\n\");\n",
        "\n",
        "\tprintf(\"幅優先探索による頂点の列挙．\\n\");\n",
        "\tfor (CurrentRoom = 0; CurrentRoom < N; CurrentRoom++)\n",
        "\t\tprintf(\"%d \", queue[CurrentRoom]);\n",
        "    printf(\"\\n\");\n",
        "\n",
        "\treturn;\n",
        "}\n",
        "\n",
        "int main(int argc, char *argv[]){\n",
        "\tbfs(0); // 開始頂点番号を引数にしてbfs関数を呼び出す\n",
        "\treturn 0;\n",
        "}"
      ],
      "execution_count": 0,
      "outputs": []
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "8y6NIDJEd6EF",
        "colab_type": "text"
      },
      "source": [
        "コンパイルしてエラーが無いことを確認．"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "1fDHcZ_kw6w8",
        "colab_type": "code",
        "colab": {}
      },
      "source": [
        "!gcc -Wall -o bfs_simple_J bfs_simple_J.c"
      ],
      "execution_count": 0,
      "outputs": []
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "s8waNgg-d_Ke",
        "colab_type": "text"
      },
      "source": [
        "実行．"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "22ZwJ5yzCWKl",
        "colab_type": "code",
        "colab": {}
      },
      "source": [
        "!./bfs_simple_J"
      ],
      "execution_count": 0,
      "outputs": []
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "tPNqfN0aFChg",
        "colab_type": "text"
      },
      "source": [
        "# 拡張（引数の利用）\n",
        "\n",
        "**目標**\n",
        "\n",
        "引数にて開始頂点を指定できるようにする．  \n",
        "\n",
        "**説明**\n",
        "\n",
        "引数を数値にするためにはatoi()関数を用いる．  \n",
        "（atoi()関数ではエラーハンドリングができないため，エラーハンドリングができるstrtol()関数のほうが頑健なプログラム作成には望ましい．  ）\n",
        "\n",
        "**コード**\n",
        "\n",
        "次はatoi()関数を引数の解釈に用いる例である．   \n",
        "main()関数内で引数の確認を行っている．  \n",
        "\n",
        "**備考**\n",
        "\n",
        "bfs()関数部分には変更を加えていない．  \n",
        "\n"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "tQ1hSFbGFKlQ",
        "colab_type": "code",
        "colab": {}
      },
      "source": [
        "%%writefile bfs_xtraCommandLine_J.c\n",
        "// Breadth First Search.\n",
        "// 2020/05 kameda[at]ccs.tsukuba.ac.jp\n",
        "// -- Extra --\n",
        "//    Accept command line option\n",
        "#include <stdio.h> // printf()\n",
        "#include <stdlib.h> // atoi()\n",
        "#include \"graph3.h\"\n",
        "\n",
        "// 幅優先探索本体\n",
        "void bfs(int StartingRoom){\n",
        "\tint listed[N]; // 0 未, 1 済\n",
        "\tint queue[N];\n",
        "\tint qhead = 0; // queue head\n",
        "\tint qtail = 0; // queue tail\n",
        "    \n",
        "    int CurrentRoom;\n",
        "    int RoomToCheck;\n",
        "\n",
        "\tfor (RoomToCheck = 0; RoomToCheck < N; RoomToCheck++)\n",
        "\t\tlisted[RoomToCheck] = 0;\n",
        "\t\n",
        "\tprintf(\"幅優先探索を 頂点%d から開始します．\\n\", StartingRoom);\n",
        "    // StartingRoomをキューに追加する\n",
        "    queue[qtail] = StartingRoom;\n",
        "    qtail++;\n",
        "\n",
        "    // キューに追加したということは訪れる対象として計上（列挙）済みということ\n",
        "\tprintf(\"頂点 %d をこれ以降は列挙済として扱います．\\n\", StartingRoom);\n",
        "    listed[StartingRoom] = 1;\n",
        " \n",
        "    // キューに処理対象がある限り作業を継続\n",
        "\twhile (qhead < qtail) {\n",
        "\t\tprintf(\"現在のキュー： 長さ %d, 先頭の頂点は %d, 末尾の頂点は %d\\n\", qtail - qhead, queue[qhead], queue[qtail - 1]);\n",
        "    \t{int i; printf(\"現在のキュー： \"); for (i = qhead; i < qtail; i++) printf(\"%d \", queue[i]); printf(\"\\n\");}\n",
        "\n",
        "        // キュー先頭から１つ呼んで作業開始（キューからは削除）\n",
        "        printf(\"キュー先頭の頂点 %d をキューから外して処理を開始します．\\n\", queue[qhead]);\n",
        "\t\tCurrentRoom = queue[qhead];\n",
        "        qhead++;\n",
        "\n",
        "        // ※ここで何かしらの作業を行うのかも．\n",
        "\n",
        "        // 次にどの頂点を列挙していくか検討\n",
        "\t\tfor (RoomToCheck = 0; RoomToCheck < N; RoomToCheck++) {\n",
        "            if (edge[CurrentRoom][RoomToCheck] == 0) {\n",
        "\t\t\t\tprintf(\"  (頂点 %d にて) 頂点 %d は隣接していませんでした‥\\n\", CurrentRoom, RoomToCheck);\n",
        "            } else if (listed[RoomToCheck] != 0) {\n",
        "\t\t\t\tprintf(\"  (頂点 %d にて) 頂点 %d は隣接はしてますがすでに処理済でした‥\\n\", CurrentRoom, RoomToCheck);\n",
        "            } else {         \n",
        "\t\t\t\tprintf(\"  (頂点 %d にて) 頂点 %d は隣接でかつキューに繋いだことがないので、キューの最後尾に追加します。\\n\", CurrentRoom, RoomToCheck);\n",
        "                // RoomToCheckをキューに追加する\n",
        "\t\t\t\tqueue[qtail] = RoomToCheck;\n",
        "                qtail++;\n",
        "\n",
        "                // キューに追加したということは訪れる処理対象として計上（列挙）済みということ\n",
        "                printf(\"  (頂点 %d にて) 頂点 %d をこれ以降は列挙済として扱います．\\n\", CurrentRoom, RoomToCheck);\n",
        "\t\t\t\tlisted[RoomToCheck] = 1;\n",
        "\t\t\t}\n",
        "\t\t}\n",
        "\t}\n",
        "\tprintf(\"何も残っていないので幅優先探索を終了します．\\n\");\n",
        "\n",
        "\tprintf(\"幅優先探索による頂点の列挙．\\n\");\n",
        "\tfor (CurrentRoom = 0; CurrentRoom < N; CurrentRoom++)\n",
        "\t\tprintf(\"%d \", queue[CurrentRoom]);\n",
        "    printf(\"\\n\");\n",
        "\n",
        "\treturn;\n",
        "}\n",
        "\n",
        "int main(int argc, char *argv[]){\n",
        "    int startnode = 0;\n",
        "    if (argc == 1) {\n",
        "        printf(\"指定がなかったので頂点0を開始頂点にします．\");\n",
        "        startnode = 0;\n",
        "    } else if (argc == 2) {\n",
        "        startnode = atoi(argv[1]);\n",
        "        if (startnode < 0 || startnode >= N) {\n",
        "            printf(\"不正な頂点指定だったので終了します．\");\n",
        "            return -1;\n",
        "        }\n",
        "    }\n",
        "\n",
        "\tbfs(startnode); // 開始頂点番号を引数にしてbfs関数を呼び出す\n",
        "\treturn 0;\n",
        "}"
      ],
      "execution_count": 0,
      "outputs": []
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "QD7n0zqyeDgm",
        "colab_type": "text"
      },
      "source": [
        "コンパイルしてエラーが無いことを確認．"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "W4ShaOLyKaAt",
        "colab_type": "code",
        "colab": {}
      },
      "source": [
        "!gcc -Wall -o bfs_xtraCommandLine_J bfs_xtraCommandLine_J.c"
      ],
      "execution_count": 0,
      "outputs": []
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "PpEZbIIseIB1",
        "colab_type": "text"
      },
      "source": [
        "実行．"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "eES9GPwVLg4z",
        "colab_type": "code",
        "colab": {}
      },
      "source": [
        "!./bfs_xtraCommandLine_J 2"
      ],
      "execution_count": 0,
      "outputs": []
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "lZXa6FVXIzoI",
        "colab_type": "text"
      },
      "source": [
        "# 拡張（関数の利用）\n",
        "\n",
        "**目標**\n",
        "\n",
        "キューへ繋ぐことと，キューから外すことを，それぞれユーザ定義関数化する．\n",
        "\n",
        "**説明**\n",
        "\n",
        "ユーザ定義関数は別ソースファイルに記述する．  \n",
        "これによって，将来ライブラリにすることができる．\n",
        "\n",
        "**コード**\n",
        "\n",
        "３つのファイルに分割する．\n",
        "* キュー操作のヘッダファイル\n",
        "* キュー操作を集めたソースファイル\n",
        "* 幅優先探索を行うプログラム\n",
        "\n",
        "**備考**\n",
        "\n",
        "分割コンパイルで実行ファイルを生成する．"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "5jU5gpnlYoAy",
        "colab_type": "code",
        "colab": {}
      },
      "source": [
        "%%writefile QueueLib_J.h\n",
        "// Queue management\n",
        "// 2020/05 kameda[at]ccs.tsukuba.ac.jp\n",
        "\n",
        "// キューの初期化\n",
        "int *initqueue(int );\n",
        "\n",
        "// キューへの追加\n",
        "int enqueue(int );\n",
        "\n",
        "// キューからの削除\n",
        "int dequeue(void);\n",
        "\n",
        "// キューの状態表示\n",
        "int showqueue(void);\n",
        "\n",
        "// キューの全表示\n",
        "int showallqueue(void);\n"
      ],
      "execution_count": 0,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "Iotxsvy8MktG",
        "colab_type": "code",
        "colab": {}
      },
      "source": [
        "%%writefile QueueLib_J.c\n",
        "// Queue management\n",
        "// 2020/05 kameda[at]ccs.tsukuba.ac.jp\n",
        "#include <stdio.h> // printf()\n",
        "#include <stdlib.h> // calloc()\n",
        "#include \"QueueLib_J.h\" // プロトタイプ宣言の整合確認\n",
        "\n",
        "int *queue = NULL; // キューの本体（初期化してから使う）\n",
        "int qsize = 0; // キューのサイズ\n",
        "int qhead = 0; // キューの先頭\n",
        "int qtail = 0; // キューの末尾\n",
        "\n",
        "// キューの初期化\n",
        "int *initqueue(int n) {\n",
        "    queue = calloc(n, sizeof(*queue));\n",
        "    if (queue == NULL) {\n",
        "        printf(\"【失敗】 %d要素分のキュー領域を確保できませんでした．\\n\", n);\n",
        "    }\n",
        "    qsize = n;\n",
        "    return queue;\n",
        "}\n",
        "\n",
        "// キューへの追加\n",
        "int enqueue(int v) {\n",
        "    if (queue == NULL) {\n",
        "        printf(\"【失敗】 キューが用意できていません．\\n\");\n",
        "        return -1;\n",
        "    } else if (qtail >= qsize) {\n",
        "        printf(\"【失敗】 %d要素確保してあったキュー領域を使い果たしてしまいました．\\n\", qsize);\n",
        "        return -2;\n",
        "    }\n",
        "    queue[qtail] = v;\n",
        "    qtail++;\n",
        "    return 0;\n",
        "}\n",
        "\n",
        "// キューからの削除\n",
        "int dequeue(void) {\n",
        "    int v;\n",
        "    if (queue == NULL) {\n",
        "        printf(\"【失敗】 キューが用意できていません．\\n\");\n",
        "        return -1;\n",
        "    } else if (qhead >= qtail) {\n",
        "        printf(\"【報告】 キューに処理対象がありません．\\n\");\n",
        "        return -2;\n",
        "    }\n",
        "    v = queue[qhead];\n",
        "    qhead++;\n",
        "    return v;\n",
        "}\n",
        "\n",
        "// キューの状態表示\n",
        "int showqueue(void) {\n",
        "    int i;\n",
        "\n",
        "    if (queue == NULL) {\n",
        "        printf(\"【失敗】 キューが用意できていません．\\n\");\n",
        "        return -1;\n",
        "    }\n",
        "\n",
        "    printf(\"qsize = %d, qhead = %d, qtail = %d\\n\", qsize, qhead, qtail);\n",
        "    for (i = qhead; i < qtail; i++) {\n",
        "        printf(\"%d \", queue[i]);\n",
        "    }\n",
        "    printf(\"\\n\");\n",
        "\n",
        "    return qtail - qhead;\n",
        "}\n",
        "\n",
        "// キューの全表示\n",
        "int showallqueue(void) {\n",
        "    int i;\n",
        "\n",
        "    if (queue == NULL) {\n",
        "        printf(\"【失敗】 キューが用意できていません．\\n\");\n",
        "        return -1;\n",
        "    }\n",
        "\n",
        "    printf(\"qsize = %d, qhead = %d, qtail = %d\\n\", qsize, qhead, qtail);\n",
        "    for (i = 0; i < qsize; i++) {\n",
        "        printf(\"%d \", queue[i]);\n",
        "    }\n",
        "    printf(\"\\n\");\n",
        "\n",
        "    return qsize;\n",
        "}\n",
        "\n"
      ],
      "execution_count": 0,
      "outputs": []
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "ih41_eQXePu8",
        "colab_type": "text"
      },
      "source": [
        "分割したキュー関係のソースファイルのみコンパイル．  \n",
        "（ライブラリの作成に相当）"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "OpW_zclrVXLi",
        "colab_type": "code",
        "colab": {}
      },
      "source": [
        "!gcc -Wall -c QueueLib_J.c"
      ],
      "execution_count": 0,
      "outputs": []
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "m9m4DOyLe5bz",
        "colab_type": "text"
      },
      "source": [
        "キュー関係の関数は外部のを用いるので，それに合わせて書き直す．   \n",
        "\"QueueLib_J.h\"の内容のみ参照して書き直せればよい．   \n",
        "（この辺りの内容はプログラミング序論Dで学習済み）  \n",
        "\n",
        "外部関数等を使いながらmain()関数などを書く場合，ユーザプログラムと呼ぶことがある．  "
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "QrR5OCVkNG2o",
        "colab_type": "code",
        "colab": {}
      },
      "source": [
        "%%writefile bfs_xtraFuncCalls_J.c\n",
        "// Breadth First Search.\n",
        "// 2020/05 kameda[at]ccs.tsukuba.ac.jp\n",
        "// -- Extra --\n",
        "//    Accept command line option\n",
        "//    Call functions for enqueue and dequeue\n",
        "#include <stdio.h> // printf()\n",
        "#include <stdlib.h> // atoi()\n",
        "#include \"QueueLib_J.h\"\n",
        "#include \"graph3.h\"\n",
        "\n",
        "// 幅優先探索本体\n",
        "void bfs(int StartingRoom){\n",
        "    int listed[N]; // 0 未, 1 済\n",
        "    \n",
        "    int CurrentRoom;\n",
        "    int RoomToCheck;\n",
        "\n",
        "\tfor (RoomToCheck = 0; RoomToCheck < N; RoomToCheck++)\n",
        "\t\tlisted[RoomToCheck] = 0;\n",
        "\n",
        "    // キューの初期化\n",
        "    initqueue(N);\n",
        "\t\n",
        "\tprintf(\"幅優先探索を 頂点%d から開始します．\\n\", StartingRoom);\n",
        "    // StartingRoomをキューに追加する\n",
        "    enqueue(StartingRoom);\n",
        "\n",
        "    // キューに追加したということは訪れる対象として（列挙）計上済みということ\n",
        "    printf(\"頂点 %d をこれ以降は列挙済として扱います．\\n\", StartingRoom);\n",
        "    listed[StartingRoom] = 1;\n",
        "\n",
        "    // キューの状態表示\n",
        "    // while()文のところでキュー操作が行われるため，その直前状態を表示するため表示タイミングを移動\n",
        "    showqueue();\n",
        "\n",
        "    // キューに処理対象がある限り作業を継続\n",
        "\twhile ((CurrentRoom = dequeue()) >= 0) {\n",
        "        // キュー先頭から１つ呼んで作業開始（キューからは削除）\n",
        "\t\tprintf(\"キュー先頭の頂点 %d をキューから外して処理を開始します．\\n\", CurrentRoom);\n",
        "        \n",
        "        // ※ここで何かしらの作業を行うのかも．\n",
        "\n",
        "        // 次にどの頂点を列挙していくか検討\n",
        "\t\tfor (RoomToCheck = 0; RoomToCheck < N; RoomToCheck++) {\n",
        "            if (edge[CurrentRoom][RoomToCheck] == 0) {\n",
        "\t\t\t\tprintf(\"  (頂点 %d にて) 頂点 %d は隣接していませんでした‥\\n\", CurrentRoom, RoomToCheck);\n",
        "            } else if (listed[RoomToCheck] != 0) {\n",
        "\t\t\t\tprintf(\"  (頂点 %d にて) 頂点 %d は隣接はしてますがすでに処理済でした‥\\n\", CurrentRoom, RoomToCheck);\n",
        "            } else {     \n",
        "\t\t\t\tprintf(\"  (頂点 %d にて) 頂点 %d は隣接でかつキューに繋いだことがないので、キューの最後尾に追加します。\\n\", CurrentRoom, RoomToCheck);\n",
        "                // RoomToCheckをキューに追加する\n",
        "\t\t\t\tenqueue(RoomToCheck);\n",
        "                \n",
        "                // キューに追加したということは訪れる処理対象として計上（列挙）済みということ\n",
        "                printf(\"  (頂点 %d にて) 頂点 %d をこれ以降は列挙済として扱います．\\n\", CurrentRoom, RoomToCheck);\n",
        "\t\t\t\tlisted[RoomToCheck] = 1;\n",
        "\t\t\t}\n",
        "\t\t}\n",
        "        // キューの状態表示\n",
        "        // while()文のところでキュー操作が行われるため，その直前状態を表示するため表示タイミングを移動\n",
        "        showqueue();\n",
        "\t}\n",
        "\tprintf(\"何も残っていないので幅優先探索を終了します．\\n\");\n",
        "\n",
        "\tprintf(\"幅優先探索による頂点の列挙．\\n\");\n",
        "    showallqueue();\n",
        "\n",
        "\treturn;\n",
        "}\n",
        "\n",
        "int main(int argc, char *argv[]){\n",
        "    int startnode = 0;\n",
        "    if (argc == 1) {\n",
        "        printf(\"指定がなかったので頂点0を開始頂点にします．\");\n",
        "        startnode = 0;\n",
        "    } else if (argc == 2) {\n",
        "        startnode = atoi(argv[1]);\n",
        "        if (startnode < 0 || startnode >= N) {\n",
        "            printf(\"不正な頂点指定だったので終了します．\");\n",
        "            return -1;\n",
        "        }\n",
        "    }\n",
        "\n",
        "\tbfs(startnode); // 開始頂点番号を引数にしてbfs関数を呼び出す\n",
        "\treturn 0;\n",
        "}"
      ],
      "execution_count": 0,
      "outputs": []
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "RIzCCG_HefwJ",
        "colab_type": "text"
      },
      "source": [
        "ユーザプログラムのコンパイル（のみ）．"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "4FjvSOZuZhy4",
        "colab_type": "code",
        "colab": {}
      },
      "source": [
        "!gcc -Wall -c bfs_xtraFuncCalls_J.c"
      ],
      "execution_count": 0,
      "outputs": []
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "el5mxVABeoT4",
        "colab_type": "text"
      },
      "source": [
        "リンカを実行して，実行ファイルを作成．"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "mzRyl1IDZyrF",
        "colab_type": "code",
        "colab": {}
      },
      "source": [
        "!gcc -o bfs_xtraFuncCalls_J bfs_xtraFuncCalls_J.o QueueLib_J.o"
      ],
      "execution_count": 0,
      "outputs": []
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "KUi66tQ9ezAc",
        "colab_type": "text"
      },
      "source": [
        "実行．"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "cnqUOVDEaAvA",
        "colab_type": "code",
        "colab": {}
      },
      "source": [
        "!./bfs_xtraFuncCalls_J 0"
      ],
      "execution_count": 0,
      "outputs": []
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "zWc0IUeckVCy",
        "colab_type": "text"
      },
      "source": [
        "# 節末課題\n",
        "\n",
        "1. アルゴリズムの記述  \n",
        "キューを用いた幅優先探索のアルゴリズムを日本語を用いて記述せよ．  \n",
        "本講義資料に即した説明であること．   \n",
        "キューの図も用いること．\n",
        "\n",
        "2. アルゴリズムの完全性  \n",
        "連結な無向グラフが与えられている限り，本節で示した幅優先探索アルゴリズムは必ず全頂点を列挙して終わることを示せ．これは本来は証明問題である．そういう文献等を探してきて読解しそれを説明するだけでも良い．\n",
        "\n",
        "3. 計算量  \n",
        "各プログラムの時間計算量と空間計算量を議論せよ．\n",
        "\n",
        "4. queue[]使用量  \n",
        "どのような無向で連結なグラフが指定されても，queue[]に必要な領域が頂点数を超えないことを示せ．\n",
        "\n",
        "5. queue[]限界使用量  \n",
        "どのような無向で連結なグラフが指定されると，queue[]の使用量が（一時的にとはいえ）最大となるか理由と共に示せ．ここでいう「最大」とは，qtail-qhead の値，すなわち待ち行列が最長になることを言う．また，逆に最小になるようなグラフとその理由を示せ．\n",
        "\n",
        "6. 遠さの表示  \n",
        "結果の列挙表示において，各頂点が開始頂点からどれだけ遠いかを数字で示すようなプログラムを示せ．遠さは開始頂点からの辺数で示すものとする．プログラムのベースには「拡張（引数の利用）」を用いよ．  \n",
        "(例) BFS result: 0(0) 1(1) 4(1) 6(2) 5(2) 2(3) 7(3) 3(4)\n",
        "\n",
        "7. atoi()関数について  \n",
        "* atoi()関数に数値と解釈できない文字列を渡したら何が起きるか述べよ．\n",
        "* atoi()関数に数値と解釈できない文字列を渡したら何が起きるか確認せよ．\n",
        "\n",
        "8. strtol()関数について  \n",
        "* strtol()関数でエラートラップする仕組みを述べよ．\n",
        "* strtol()関数でエラートラップする簡単なプログラムを作成せよ．  \n",
        "（ヒント：stortol()関数ではerrnoを用いてエラー処理を実施する．）\n",
        "\n",
        "9. queue[]前詰め  \n",
        "queue[]から処理単位を削除した後，queue[]の内容を前詰めするプログラムを示せ．（言い換えれば queue[0] が常にキューの先頭であるようにすること．）\n",
        "\n",
        "10. グラフの指定  \n",
        " \"graph3.h\"をインクルードする代わりに，グラフの隣接行列を記述したテキストファイルを読み込み，それを利用することが考えられる．そうできるプログラムを示せ．\n",
        "\n",
        "\n",
        "# 出典\n",
        "\n",
        "筑波大学工学システム学類  \n",
        "データ構造とアルゴリズム  \n",
        "担当：亀田能成  \n",
        "2020/05/19.\n",
        "\n",
        "\n",
        "\n"
      ]
    }
  ]
}