DataAlgo2020_005(DFS).ipynb

{
  "nbformat": 4,
  "nbformat_minor": 0,
  "metadata": {
    "colab": {
      "name": "DataAlgo2020-005(DFS) ",
      "provenance": [],
      "collapsed_sections": [],
      "authorship_tag": "ABX9TyM2mbLnuMBRGvx2BPgOT/EY",
      "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_005(DFS).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.3. 深さ優先探索\n",
        "\n",
        "ここでは深さ優先探索(Depth first search; DFS)について学ぶ．  \n",
        "深さ優先探索によって，グラフに即した形で全頂点の列挙を行う．\n",
        "\n",
        "**いつもの約束**  \n",
        "１つのコードセルだけの実行は Ctrl + Enter．  \n",
        "エディタで「インデント幅（スペース）は4で表示」「行番号を表示」「インデントガイドを表示」．  \n",
        "内部では日本語はUTF-8で表現されている．"
      ]
    },
    {
      "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\n",
        "%mkdir -p 202004_DataAlgo/DA2020_005\n",
        "%cd       202004_DataAlgo/DA2020_005\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": "227hkF2NhgRF",
        "colab_type": "text"
      },
      "source": [
        "ここでは，グラフ3を利用する．  \n",
        "頂点数は8．無向グラフ．連結．"
      ]
    },
    {
      "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-Last-Out = Last-In-First-Out)を利用する．大雑把に言えば，開始頂点から見てできるだけ遠いch頂点から調査を行って列挙していく．このとき，その頂点に隣接している未列挙頂点があれば，それをすぐ次に調査する．つまり最後に見つかった頂点から調査することになる(Last-In-First-Out)．これをスタックに積むという．ある頂点からさらに先に（遠くに）頂点が見つからない場合，頂点を一つ戻って（スタックの一番を取り去って，そこに現れるひとつ前の）頂点の調査を続行する．\n",
        "\n",
        "グラフに閉路がある場合，開始頂点からある頂点への道が２つ以上あることがある．最初に到達するのに用いた道より次に到達するのに使った道がより短い，ということが起きうる．最初に到達した時点で当該頂点が開始頂点から見て一番遠い頂点だった場合，（後でそれほど遠い頂点でないとわかることになるにしても）その時点で列挙することは深さ優先探索の定義に合致する．（あとでより短い道が見つかったとしても列挙順を訂正したりはしない．）\n",
        "\n",
        "参考までに，グラフG3について頂点0からDFSを実施した場合，深さ優先による頂点列挙の結果は次のようになる．  \n",
        "ただし，同じ優先度の頂点が複数あったときは，番号の小さい方の頂点を選択するものとする．\n",
        "\n",
        "DFS result: 0 1 6 2 3 7 5 4"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "0_o0avWIHZqC",
        "colab_type": "text"
      },
      "source": [
        "# 深さ優先探索プログラム\n",
        "\n",
        "**目標**\n",
        "\n",
        "スタックを用いた深さ優先探索によって，与えられたグラフの頂点を列挙する．\n",
        "\n",
        "**説明**\n",
        "\n",
        "開始頂点は指定されるものとする．  \n",
        "  \n",
        "スタックは机の上に積んでいく宿題だと思えばよい．   \n",
        "スタックの一番上を stacktop と呼ぶことにする．    \n",
        "新しくオブジェクトを追加するときは，それをスタックの一番上に積む．  \n",
        "（宿題を上に積み重ねるのと同じことである．）  \n",
        "積み上げる動作のことを push と呼ぶ．  \n",
        "詰み上がった一番上のオブジェクトを取り去る動作のことを pop と呼ぶ．  \n",
        "（一番上の宿題を取って，自分の前に拡げるのと同じことである）  \n",
        "\n",
        "**コード**\n",
        "\n",
        "下記の通り．  \n",
        "グラフが無向で連結である限り，深さ優先探索は必ず成功する．  \n",
        "そのため，dfs()はvoidとしている．\n",
        "\n",
        "**備考**\n",
        "\n",
        "なし．"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "Sfxsc_02JNc1",
        "colab_type": "code",
        "colab": {}
      },
      "source": [
        "%%writefile dfs_simple_J.c\n",
        "// Depth First Search.\n",
        "// 2020/05 kameda[at]ccs.tsukuba.ac.jp\n",
        "#include <stdio.h> // printf()\n",
        "#include \"graph3.h\"\n",
        "\n",
        "// 深さ優先探索本体\n",
        "void dfs(int StartingRoom){\n",
        "\tint listed[N];  // 0 未, 1 済\n",
        "\tint stack[N*N];\n",
        "\tint stacktop = 0;\n",
        "    \n",
        "    int CurrentRoom;\n",
        "    int RoomToCheck;\n",
        "\n",
        "\tint visited[N]; // 列挙順を記録するための配列\n",
        "\tint num_visited = 0; // 記録済の頂点数\n",
        "\n",
        "\tfor (RoomToCheck = 0; RoomToCheck < N; RoomToCheck++)\n",
        "\t\tlisted[RoomToCheck] = 0;\n",
        "\t\n",
        "\tprintf(\"深さ優先探索を 頂点%d から開始します．\\n\", StartingRoom);\n",
        "    // StartingRoomをスタックに積む\n",
        "    stack[stacktop] = StartingRoom;\n",
        "    stacktop++;\n",
        "\n",
        "\t// スタックに処理対象がある限り作業を継続\n",
        "\twhile (stacktop > 0) {\n",
        "\t\tprintf(\"現在のスタック： 長さ %d, スタックトップは %d\\n\", stacktop, stack[stacktop - 1]);\n",
        "\t\t{int i; for (i = 0; i < stacktop; i++) printf(\"%d \", stack[i]); printf(\"\\n\");}\n",
        "\n",
        "        // スタックから１つ降ろして処理開始（スタックからは削除）\n",
        "\t\tprintf(\"スタックトップの頂点 %d をスタックから降ろして処理を開始します．\\n\", stack[stacktop - 1]);\n",
        "\t\tCurrentRoom = stack[stacktop - 1];\n",
        "        stacktop--;\n",
        "\n",
        "\t\tif (listed[CurrentRoom] == 0) {\n",
        "\t\t\t// ※ここで何かしらの作業を行うのかも．\n",
        "\n",
        "\t\t\t// 処理済みであることを記録\n",
        "\t\t\tprintf(\"頂点 %d をこれ以降は列挙済として扱います．\\n\", CurrentRoom);\n",
        "\t\t\tlisted[CurrentRoom] = 1;\n",
        "\t\t\t// 計上（列挙）順を記録\n",
        "\t\t\tvisited[num_visited] = CurrentRoom;\n",
        "\t\t\tnum_visited++;\n",
        "\n",
        "    \t\t// 次にどの頂点を列挙していくか検討\n",
        "\t\t\t//   次のfor文の変数が降順（小さくしていく）になっているのは\n",
        "\t\t\t//  「同じ優先度の頂点が複数あったときは，番号の小さい方の頂点を選択」を遵守するため\n",
        "\t\t\tfor (RoomToCheck = N-1; RoomToCheck >= 0; RoomToCheck--) {\n",
        "   \t    \t\tif (edge[CurrentRoom][RoomToCheck] == 0) {\n",
        "\t\t\t\t\tprintf(\"  (頂点 %d にて) 頂点 %d は隣接していませんでした‥\\n\", CurrentRoom, RoomToCheck);\n",
        "\t\t\t\t} else if (listed[RoomToCheck] != 0) {\n",
        "\t\t\t\t\tprintf(\"  (頂点 %d にて) 頂点 %d は隣接はしていますがすでに処理済でした‥\\n\", CurrentRoom, RoomToCheck);\n",
        "        \t\t} else {         \n",
        "\t\t\t\t\tprintf(\"  (頂点 %d にて) まだ処理したことのない頂点 %d が隣接しているので、スタックに積み上げます．\\n\", CurrentRoom, RoomToCheck);\n",
        "               \t\t// RoomToCheckをスタックに積む\n",
        "\t\t\t\t\tstack[stacktop] = RoomToCheck;\n",
        "               \t\tstacktop++;\n",
        "\t\t\t\t}\n",
        "\t\t\t}\n",
        "\t\t}\n",
        "\t}\n",
        "\tprintf(\"処理待ち行列に何も残っていないので深さ優先探索を終了します．\\n\");\n",
        "\n",
        "\tprintf(\"深さ優先探索による頂点の列挙．\\n\");\n",
        "\tfor (CurrentRoom = 0; CurrentRoom < num_visited; CurrentRoom++)\n",
        "\t\tprintf(\"%d \", visited[CurrentRoom]);\n",
        "    printf(\"\\n\");\n",
        "\n",
        "\treturn;\n",
        "}\n",
        "\n",
        "int main(int argc, char *argv[]){\n",
        "\tdfs(0); // 開始頂点番号を引数にしてdfs関数を呼び出す\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 dfs_simple_J dfs_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": [
        "!./dfs_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",
        "\n",
        "次はatoi()関数を引数の解釈に用いる例である．   \n",
        "main()関数内で引数の確認を行っている．  \n",
        "\n",
        "**備考**\n",
        "\n",
        "dfs()関数部分には変更を加えていない．  \n",
        "\n"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "tQ1hSFbGFKlQ",
        "colab_type": "code",
        "colab": {}
      },
      "source": [
        "%%writefile dfs_xtraCommandLine_J.c\n",
        "// Depth 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 dfs(int StartingRoom){\n",
        "\tint listed[N];  // 0 未, 1 済\n",
        "\tint stack[N*N];\n",
        "\tint stacktop = 0;\n",
        "    \n",
        "    int CurrentRoom;\n",
        "    int RoomToCheck;\n",
        "\n",
        "\tint visited[N]; // 列挙順を記録するための配列\n",
        "\tint num_visited = 0; // 記録済の頂点数\n",
        "\n",
        "\tfor (RoomToCheck = 0; RoomToCheck < N; RoomToCheck++)\n",
        "\t\tlisted[RoomToCheck] = 0;\n",
        "\t\n",
        "\tprintf(\"深さ優先探索を 頂点%d から開始します．\\n\", StartingRoom);\n",
        "    // StartingRoomをスタックに積む\n",
        "    stack[stacktop] = StartingRoom;\n",
        "    stacktop++;\n",
        "\n",
        "\t// スタックに処理対象がある限り作業を継続\n",
        "\twhile (stacktop > 0) {\n",
        "\t\tprintf(\"現在のスタック： 長さ %d, スタックトップは %d\\n\", stacktop, stack[stacktop - 1]);\n",
        "\t\t{int i; for (i = 0; i < stacktop; i++) printf(\"%d \", stack[i]); printf(\"\\n\");}\n",
        "\n",
        "        // スタックから１つ降ろして処理開始（スタックからは削除）\n",
        "\t\tprintf(\"スタックトップの頂点 %d をスタックから降ろして処理を開始します．\\n\", stack[stacktop - 1]);\n",
        "\t\tCurrentRoom = stack[stacktop - 1];\n",
        "        stacktop--;\n",
        "\n",
        "\t\tif (listed[CurrentRoom] == 0) {\n",
        "\t\t\t// ※ここで何かしらの作業を行うのかも．\n",
        "\n",
        "\t\t\t// 処理済みであることを記録\n",
        "\t\t\tprintf(\"頂点 %d をこれ以降は列挙済として扱います．\\n\", CurrentRoom);\n",
        "\t\t\tlisted[CurrentRoom] = 1;\n",
        "\t\t\t// 計上（列挙）順を記録\n",
        "\t\t\tvisited[num_visited] = CurrentRoom;\n",
        "\t\t\tnum_visited++;\n",
        "\n",
        "        \t// 次にどの頂点を列挙していくか検討\n",
        "\t\t\tfor (RoomToCheck = N-1; RoomToCheck >= 0; RoomToCheck--) {\n",
        "   \t\t\t\tif (edge[CurrentRoom][RoomToCheck] == 0) {\n",
        "\t\t\t\t\tprintf(\"  (頂点 %d にて) 頂点 %d は隣接していませんでした‥\\n\", CurrentRoom, RoomToCheck);\n",
        "\t\t\t\t} else if (listed[RoomToCheck] != 0) {\n",
        "\t\t\t\t\tprintf(\"  (頂点 %d にて) 頂点 %d は隣接はしていますがすでに処理済でした‥\\n\", CurrentRoom, RoomToCheck);\n",
        "        \t\t} else {         \n",
        "\t\t\t\t\tprintf(\"  (頂点 %d にて) まだ処理したことのない頂点 %d が隣接しているので、スタックに積み上げます．\\n\", CurrentRoom, RoomToCheck);\n",
        "               \t\t// RoomToCheckをスタックに積む\n",
        "\t\t\t\t\tstack[stacktop] = RoomToCheck;\n",
        "               \t\tstacktop++;\n",
        "\t\t\t\t}\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 \", visited[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\");\n",
        "        startnode = 0;\n",
        "    } else if (argc == 2) {\n",
        "        startnode = atoi(argv[1]);\n",
        "        if (startnode < 0 || startnode >= N) {\n",
        "            printf(\"不正な頂点指定だったので終了します．\\n\");\n",
        "            return -1;\n",
        "        }\n",
        "    }\n",
        "\n",
        "\tdfs(startnode); // 開始頂点番号を引数にしてdfs関数を呼び出す\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 dfs_xtraCommandLine_J dfs_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": [
        "!./dfs_xtraCommandLine_J 0"
      ],
      "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 StackLib_J.h\n",
        "// Stack management\n",
        "// 2020/05 kameda[at]ccs.tsukuba.ac.jp\n",
        "\n",
        "// スタックの初期化\n",
        "int *initstack(int );\n",
        "\n",
        "// スタックへの追加\n",
        "int stackpush(int );\n",
        "\n",
        "// スタックからの削除\n",
        "int stackpop(void);\n",
        "\n",
        "// スタックの状態表示\n",
        "int showstack(void);\n",
        "\n",
        "// スタックの全表示（通常意味はない）\n",
        "int showallstack(void);\n"
      ],
      "execution_count": 0,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "Iotxsvy8MktG",
        "colab_type": "code",
        "colab": {}
      },
      "source": [
        "%%writefile StackLib_J.c\n",
        "// Stack management\n",
        "// 2020/05 kameda[at]ccs.tsukuba.ac.jp\n",
        "#include <stdio.h> // printf()\n",
        "#include <stdlib.h> // calloc()\n",
        "#include \"StackLib_J.h\" // プロトタイプ宣言の整合確認\n",
        "\n",
        "int *stack = NULL; // スタックの本体（初期化してから使う）\n",
        "int stacksize = 0; // スタックのサイズ\n",
        "int stacktop = 0; // スタックトップ\n",
        "\n",
        "// スタックの初期化\n",
        "int *initstack(int n) {\n",
        "    stack = calloc(n, sizeof(*stack));\n",
        "    if (stack == NULL) {\n",
        "        printf(\"【失敗】 %d要素分のスタック領域を確保できませんでした．\\n\", n);\n",
        "    }\n",
        "    stacksize = n;\n",
        "    return stack;\n",
        "}\n",
        "\n",
        "// スタックへの追加\n",
        "int stackpush(int v) {\n",
        "    if (stack == NULL) {\n",
        "        printf(\"【失敗】 スタックが用意できていません．\\n\");\n",
        "        return -1;\n",
        "    } else if (stacktop >= stacksize) {\n",
        "        printf(\"【失敗】 %d要素確保してあったスタック領域を使い果たしてしまいました．\\n\", stacksize);\n",
        "        return -2;\n",
        "    }\n",
        "    printf(\"--stack:push %d (stacktop=%d)\\n\", v, stacktop);\n",
        "    stack[stacktop] = v;\n",
        "    stacktop++;\n",
        "    return 0;\n",
        "}\n",
        "\n",
        "// スタックからの削除\n",
        "int stackpop(void) {\n",
        "    int v;\n",
        "    if (stack == NULL) {\n",
        "        printf(\"【失敗】 スタックが用意できていません．\\n\");\n",
        "        return -1;\n",
        "    } else if (stacktop <= 0) {\n",
        "        printf(\"【報告】 スタックに処理対象がありません．\\n\");\n",
        "        return -2;\n",
        "    }\n",
        "    printf(\"--stack:pop    (stacktop=%d)\\n\", stacktop);\n",
        "    v = stack[stacktop - 1];\n",
        "    stacktop--;\n",
        "    printf(\"--stack:pop %2d (stacktop=%d)\\n\", v, stacktop);\n",
        "    return v;\n",
        "}\n",
        "\n",
        "// スタックの状態表示\n",
        "int showstack(void) {\n",
        "    int i;\n",
        "\n",
        "    if (stack == NULL) {\n",
        "        printf(\"【失敗】 スタックが用意できていません．\\n\");\n",
        "        return -1;\n",
        "    }\n",
        "\n",
        "    printf(\"showstack : stacksize = %d, stacktop = %d\\n\", stacksize, stacktop);\n",
        "    printf(\"showstack : \");\n",
        "    for (i = 0; i < stacktop; i++) {\n",
        "        printf(\"%d \", stack[i]);\n",
        "    }\n",
        "    printf(\"\\n\");\n",
        "\n",
        "    return stacktop;\n",
        "}\n",
        "\n",
        "// スタックの全表示（通常意味はない）\n",
        "int showallstack(void) {\n",
        "    int i;\n",
        "\n",
        "    if (stack == NULL) {\n",
        "        printf(\"【失敗】 スタックが用意できていません．\\n\");\n",
        "        return -1;\n",
        "    }\n",
        "\n",
        "    printf(\"showallstack: stacksize = %d, stacktop = %d\\n\", stacksize, stacktop);\n",
        "    printf(\"showallstack: \");\n",
        "    for (i = 0; i < stacksize; i++) {\n",
        "        printf(\"%d \", stack[i]);\n",
        "    }\n",
        "    printf(\"\\n\");\n",
        "\n",
        "    return stacksize;\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 StackLib_J.c"
      ],
      "execution_count": 0,
      "outputs": []
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "m9m4DOyLe5bz",
        "colab_type": "text"
      },
      "source": [
        "スタック関係の関数は外部のを用いるので，それに合わせて書き直す．   \n",
        "\"StackLib_J.h\"の内容のみ参照して書き直せればよい．   \n",
        "（この辺りの内容はプログラミング序論Dで学習済み）  \n",
        "\n",
        "外部関数等を使いながらmain()関数などを書く場合，ユーザプログラムと呼ぶことがある．  "
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "QrR5OCVkNG2o",
        "colab_type": "code",
        "colab": {}
      },
      "source": [
        "%%writefile dfs_xtraFuncCalls_J.c\n",
        "// Depth First Search.\n",
        "// 2020/05 kameda[at]ccs.tsukuba.ac.jp\n",
        "// -- Extra --\n",
        "//    Accept command line option\n",
        "//    Call functions for stackpush and stackpop\n",
        "#include <stdio.h> // printf()\n",
        "#include <stdlib.h> // atoi()\n",
        "#include \"StackLib_J.h\"\n",
        "#include \"graph3.h\"\n",
        "\n",
        "// 深さ優先探索本体\n",
        "void dfs(int StartingRoom){\n",
        "\tint listed[N];  // 0 未, 1 済\n",
        "    \n",
        "    int CurrentRoom;\n",
        "    int RoomToCheck;\n",
        "\n",
        "\tint visited[N]; // 列挙順を記録するための配列\n",
        "\tint num_visited = 0; // 記録済の頂点数\n",
        "\n",
        "\tfor (RoomToCheck = 0; RoomToCheck < N; RoomToCheck++)\n",
        "\t\tlisted[RoomToCheck] = 0;\n",
        "\n",
        "    // スタックの初期化\n",
        "    initstack(N*N);\n",
        "\t\n",
        "\tprintf(\"深さ優先探索を 頂点%d から開始します．\\n\", StartingRoom);\n",
        "    // StartingRoomをスタックに積む\n",
        "    stackpush(StartingRoom);\n",
        "\n",
        "    // スタックの状態表示\n",
        "    // while()文のところでスタック操作が行われるため，その直前状態を表示するため表示タイミングを移動\n",
        "    showstack();\n",
        "\n",
        "\t// スタックに処理対象がある限り作業を継続\n",
        "\twhile ((CurrentRoom = stackpop()) >= 0) {\n",
        "        // スタックから１つ降ろして処理開始（スタックからは削除）\n",
        "\t\tprintf(\"スタックトップの頂点 %d をスタックから降ろして処理を開始します．\\n\", CurrentRoom);\n",
        "\n",
        "\t\tif (listed[CurrentRoom] == 0) {\n",
        "\t\t\t// ※ここで何かしらの作業を行うのかも．\n",
        "\n",
        "\t\t\t// 処理済みであることを記録\t  \n",
        "\t\t\tprintf(\"頂点 %d をこれ以降は列挙済として扱います．\\n\", CurrentRoom);\n",
        "\t\t\tlisted[CurrentRoom] = 1;\n",
        "\t\t\t// 計上（列挙）順を記録\n",
        "\t\t\tvisited[num_visited] = CurrentRoom;\n",
        "\t\t\tnum_visited++;\n",
        "\n",
        "        \t// 次にどの頂点を列挙していくか検討\n",
        "\t\t\tfor (RoomToCheck = N-1; RoomToCheck >= 0; RoomToCheck--) {\n",
        "   \t        \tif (edge[CurrentRoom][RoomToCheck] == 0) {\n",
        "\t\t\t\t\tprintf(\"  (頂点 %d にて) 頂点 %d は隣接していませんでした‥\\n\", CurrentRoom, RoomToCheck);\n",
        "\t\t\t\t} else if (listed[RoomToCheck] != 0) {\n",
        "\t\t\t\t\tprintf(\"  (頂点 %d にて) 頂点 %d は隣接はしていますがすでに処理済でした‥\\n\", CurrentRoom, RoomToCheck);\n",
        "        \t\t} else {         \n",
        "\t\t\t\t\tprintf(\"  (頂点 %d にて) まだ処理したことのない頂点 %d が隣接しているので、スタックに積み上げます．\\n\", CurrentRoom, RoomToCheck);\n",
        "               \t\t// RoomToCheckをスタックに積む\n",
        "\t\t\t\t\tstackpush(RoomToCheck);\n",
        "\t\t\t\t}\n",
        "\t\t\t}\n",
        "\t\t}\n",
        "\t\t\n",
        "\t    // スタックの状態表示\n",
        "    \t// while()文のところでスタック操作が行われるため，その直前状態を表示するため表示タイミングを移動\n",
        "        showstack();\n",
        "\t}\n",
        "\tprintf(\"何も残っていないので深さ優先探索を終了します．\\n\");\n",
        "\n",
        "\tprintf(\"深さ優先探索による頂点の列挙．\\n\");\n",
        "\tfor (CurrentRoom = 0; CurrentRoom < N; CurrentRoom++)\n",
        "\t\tprintf(\"%d \", visited[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\");\n",
        "        startnode = 0;\n",
        "    } else if (argc == 2) {\n",
        "        startnode = atoi(argv[1]);\n",
        "        if (startnode < 0 || startnode >= N) {\n",
        "            printf(\"不正な頂点指定だったので終了します．\\n\");\n",
        "            return -1;\n",
        "        }\n",
        "    }\n",
        "\n",
        "\tdfs(startnode); // 開始頂点番号を引数にしてdfs関数を呼び出す\n",
        "\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 dfs_xtraFuncCalls_J.c\n",
        "\n",
        "!gcc -Wall -c StackLib_J.c\n",
        "!gcc -o dfs_xtraFuncCalls_J dfs_xtraFuncCalls_J.o StackLib_J.o\n",
        "!./dfs_xtraFuncCalls_J 0 2>&1 "
      ],
      "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 dfs_xtraFuncCalls_J dfs_xtraFuncCalls_J.o StackLib_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": [
        "!./dfs_xtraFuncCalls_J 0 2>&1 "
      ],
      "execution_count": 0,
      "outputs": []
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "oVlm1UA8X1Z2",
        "colab_type": "text"
      },
      "source": [
        "# 拡張（再帰呼出の利用）\n",
        "\n",
        "**目標**\n",
        "\n",
        "C言語の再帰呼出を利用することで深さ優先探索を実現する．\n",
        "\n",
        "\n",
        "**説明**\n",
        "\n",
        "C言語には，スタックを利用した言語構造がある．  \n",
        "それは関数呼び出しである．  \n",
        "C言語では，関数を呼び出すとき，その引数と内部変数はスタック領域に確保される．  \n",
        "再帰呼出関数を利用してプログラムを書くことで，スタック操作を明示的に行わないまま深さ優先探索が実現できる．  \n",
        "\n",
        "C言語特有の言語構造を利用することで，ユーザプログラムの記述が簡素になっていることに注意すること．  \n",
        "\n",
        "なお，C言語特有の言語構造にキューはないので，幅優先探索をこれと同じような形で簡素に記述することはできない．\n",
        "\n",
        "**コード**\n",
        "\n",
        "再帰呼出中にも利用するため，listed[] と visited[] を大域変数として確保する．  \n",
        "大域変数の初期化は main() 関数で行う．  \n",
        "深さ優先探索の結果である列挙の表示も main() 関数で行う．  \n",
        "\n",
        "**備考**\n",
        "\n",
        "例えば，日本語では２人称を表す単語に，あなた，おまえ，貴様，など幾つかある．  \n",
        "英語では２人称を表す単語はyouだけである．  \n",
        "愛を込めて相手を呼ぶとき，日本語なら「あなた」だけで含意することができるが，英語では \"my sweet honey\"のように言い換えたり単語数を増やすことが必要になる．  \n",
        "C言語はプログラミング言語であり人工言語ではあるが，やはり言語ではあるので，似たようなことが生じるのである．"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "Eo2CM8EqZi97",
        "colab_type": "code",
        "colab": {}
      },
      "source": [
        "%%writefile dfs_recursive_J.c\n",
        "// Depth First Search by recursive call\n",
        "// 2020/05 kameda[at]ccs.tsukuba.ac.jp\n",
        "#include <stdio.h> // printf()\n",
        "#include <stdlib.h> // atoi()\n",
        "#include \"graph3.h\"\n",
        "\n",
        "int listed[N];  // 0 未, 1 済\n",
        "\n",
        "int visited[N]; // 列挙順を記録するための配列\n",
        "int num_visited = 0; // 記録済の頂点数\n",
        "\n",
        "\n",
        "// 深さ優先探索本体 / 再帰呼出\n",
        "void dfs(int CurrentRoom){\n",
        "    int RoomToCheck;\n",
        "\n",
        "    // スタック領域に積み上がった状態で処理開始\n",
        "\tprintf(\"頂点 %d について処理を開始します．\\n\", CurrentRoom);\n",
        "\n",
        "\t// ※ここで何かしらの作業を行うのかも．\n",
        "\n",
        "\t// 処理済みであることを記録\n",
        "\tprintf(\"頂点 %d をこれ以降は列挙済として扱います．\\n\", CurrentRoom);\n",
        "\tlisted[CurrentRoom] = 1;\n",
        "\t// 計上（列挙）順を記録\n",
        "\tvisited[num_visited] = CurrentRoom;\n",
        "\tnum_visited++;\n",
        "\n",
        "    // 次にどの頂点を列挙していくか検討\n",
        "\tfor (RoomToCheck = 0; RoomToCheck < N; RoomToCheck++) {\n",
        "        if (edge[CurrentRoom][RoomToCheck] == 0) {\n",
        "\t\t\tprintf(\"  (頂点 %d にて) 頂点 %d は隣接していませんでした‥\\n\", CurrentRoom, RoomToCheck);\n",
        "\t\t} else if (listed[RoomToCheck] != 0) {\n",
        "\t\t\tprintf(\"  (頂点 %d にて) 頂点 %d は隣接はしていますがすでに処理済でした‥\\n\", CurrentRoom, RoomToCheck);\n",
        "       \t} else {         \n",
        "\t\t\tprintf(\"  (頂点 %d にて) まだ処理したことのない頂点 %d が隣接しているので、すぐに取り掛かります．\\n\", CurrentRoom, RoomToCheck);\n",
        "           \t// RoomToCheckの処理へ進む（再帰呼出）\n",
        "\t\t\tdfs(RoomToCheck);\n",
        "\t\t}\n",
        "\t}\n",
        "\n",
        "\treturn;\n",
        "}\n",
        "\n",
        "int main(int argc, char *argv[]){\n",
        "    int RoomToCheck;\n",
        "\n",
        "    int startnode = 0;\n",
        "    if (argc == 1) {\n",
        "        printf(\"指定がなかったので頂点0を開始頂点にします．\\n\");\n",
        "        startnode = 0;\n",
        "    } else if (argc == 2) {\n",
        "        startnode = atoi(argv[1]);\n",
        "        if (startnode < 0 || startnode >= N) {\n",
        "            printf(\"不正な頂点指定だったので終了します．\\n\");\n",
        "            return -1;\n",
        "        }\n",
        "    }\n",
        "\n",
        "\tfor (RoomToCheck = 0; RoomToCheck < N; RoomToCheck++)\n",
        "\t\tlisted[RoomToCheck] = 0;\n",
        "\n",
        "\tdfs(startnode); // 開始頂点番号を引数にしてdfs関数を呼び出す\n",
        "\n",
        "   \tprintf(\"深さ優先探索による頂点の列挙．\\n\");\n",
        "\tfor (RoomToCheck = 0; RoomToCheck < N; RoomToCheck++)\n",
        "\t\tprintf(\"%d \", visited[RoomToCheck]);\n",
        "    printf(\"\\n\");\n",
        "\n",
        "\treturn 0;\n",
        "}"
      ],
      "execution_count": 0,
      "outputs": []
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "zhechXUNbvva",
        "colab_type": "text"
      },
      "source": [
        "\n",
        "コンパイルしてエラーが無いことを確認．"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "5gxNiHT-bvEd",
        "colab_type": "code",
        "colab": {}
      },
      "source": [
        "!gcc -Wall -o dfs_recursive_J dfs_recursive_J.c"
      ],
      "execution_count": 0,
      "outputs": []
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "CxBI4UbEcB9L",
        "colab_type": "text"
      },
      "source": [
        "実行．"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "O3zzVD4tcA3h",
        "colab_type": "code",
        "colab": {}
      },
      "source": [
        "!./dfs_recursive_J"
      ],
      "execution_count": 0,
      "outputs": []
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "MpROEk5Zr51r",
        "colab_type": "text"
      },
      "source": [
        "# 再帰呼出の利用による最小構成\n",
        "\n",
        "前のプログラムは実行が確認しやすいように各部にprintf()を挿入していたが，実行に必要な部分のみでdfs()関数を構成すると次のようになる．再帰呼出の他は代入文１行，printf文１行，for文１行，if文１行しかない．\n",
        "\n",
        "如何にプログラムが簡潔に書けるかがよくわかるであろう．"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "eUJKZIidr4pi",
        "colab_type": "code",
        "colab": {}
      },
      "source": [
        "%%writefile dfs_recursive-short_J.c\n",
        "// Depth First Search by recursive call\n",
        "// 2020/05 kameda[at]ccs.tsukuba.ac.jp\n",
        "#include <stdio.h> // printf()\n",
        "#include <stdlib.h> // atoi()\n",
        "#include \"graph3.h\"\n",
        "\n",
        "int listed[N];  // 0 未, 1 済\n",
        "\n",
        "// 深さ優先探索本体 / 再帰呼出\n",
        "void dfs(int CurrentRoom){\n",
        "    int RoomToCheck;\n",
        "\n",
        "\t// 処理済みであることを記録\n",
        "\tlisted[CurrentRoom] = 1;\n",
        "\t// 計上（列挙）を表示\n",
        "    printf(\"★★列挙： %d\\n\", CurrentRoom);\n",
        "\n",
        "    // 次にどの頂点を列挙していくか検討\n",
        "\tfor (RoomToCheck = 0; RoomToCheck < N; RoomToCheck++) {\n",
        "        if (edge[CurrentRoom][RoomToCheck] != 0 && listed[RoomToCheck] == 0) \n",
        "\t\t\tdfs(RoomToCheck);\n",
        "\t}\n",
        "\treturn;\n",
        "}\n",
        "\n",
        "int main(int argc, char *argv[]){\n",
        "    int RoomToCheck;\n",
        "\n",
        "    int startnode = 0;\n",
        "    if (argc == 1) {\n",
        "        printf(\"指定がなかったので頂点0を開始頂点にします．\\n\");\n",
        "        startnode = 0;\n",
        "    } else if (argc == 2) {\n",
        "        startnode = atoi(argv[1]);\n",
        "        if (startnode < 0 || startnode >= N) {\n",
        "            printf(\"不正な頂点指定だったので終了します．\\n\");\n",
        "            return -1;\n",
        "        }\n",
        "    }\n",
        "\n",
        "\tfor (RoomToCheck = 0; RoomToCheck < N; RoomToCheck++)\n",
        "\t\tlisted[RoomToCheck] = 0;\n",
        "\n",
        "\tdfs(startnode); // 開始頂点番号を引数にしてdfs関数を呼び出す\n",
        "\n",
        "\treturn 0;\n",
        "}"
      ],
      "execution_count": 0,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "BVfu0aXytnqc",
        "colab_type": "code",
        "colab": {}
      },
      "source": [
        "!gcc -Wall -o dfs_recursive-short_J dfs_recursive-short_J.c\n",
        "!./dfs_recursive-short_J 0"
      ],
      "execution_count": 0,
      "outputs": []
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "DY_MbwoPf_9h",
        "colab_type": "text"
      },
      "source": [
        "# 節末課題\n",
        "\n",
        "1. アルゴリズムの記述  \n",
        "スタックを用いた深さ優先探索のアルゴリズムを日本語を用いて記述せよ． \n",
        "本講義資料に即した説明であること．   \n",
        "スタックの図も用いること．\n",
        "\n",
        "2. アルゴリズムの完全性  \n",
        "連結な無向グラフが与えられている限り，本節で示した深さ優先探索アルゴリズムは必ず全頂点を列挙して終わることを示せ．これは本来は証明問題である．そういう文献等を探してきて読解しそれを説明するだけでも良い．\n",
        "\n",
        "3. 計算量  \n",
        "各プログラムの時間計算量と空間計算量を議論せよ．\n",
        "\n",
        "4. スタック使用量  \n",
        "プログラム dfs_recursive_J においては，どのような無向で連結なグラフが指定されても，スタックに必要な領域が頂点数（の常数倍）を超えないことを示せ．\n",
        "\n",
        "5. スタック一時使用量  \n",
        "プログラム dfs_recursive_J においては，どのような無向で連結なグラフが指定されると，スタックの使用量が一時的にとはいえ最大となるか理由と共に示せ．ここでいう最大とは，スタックが一番高く積み上がる状態を言う．\n",
        "\n",
        "6. 再帰呼出利用による構造の簡素化  \n",
        "本節で挙げたプログラムのうち，再帰呼出を用いたプログラムが，その前のプログラムと比べてどう構造的に簡素化されているのか自分なりに説明せよ．\n",
        "\n",
        "7. 再帰呼出利用におけるスタックの見える化  \n",
        "再帰呼出を用いたプログラムにおいて，dfs()関数内の CurrentRoom, RoomToCheck 変数，および大域変数の変化を示しながら，グラフG3の開始頂点0における実行の様子を丁寧に示せ．特にスタック領域におけるCurrentRoom, RoomToCheckの確保のされ方については明確に示すこと．\n",
        "\n",
        "8. スタックの内容の違い  \n",
        "ここで示した２つのプログラム ( dfs_xtraCommandLine_J, dfs_recursive_J ) において，注意深く観察すると，同じ開始頂点を与えたときに列挙結果は同じとなるものの，途中のスタックの中身は同じではない．どちらも深さ優先探索ではある．この違いが発生する原因を考察せよ．\n",
        "\n",
        "9. 深さ表示の追加  \n",
        "深さ優先探索の結果の列挙において，それぞれの頂点の深さ（開始頂点からの辺数）を合わせて表示するプログラムを作成せよ．ベースには dfs_recursive-short_J を用いること．(例：「★★列挙： 0 (深さ 0)」 ... ★★列挙： 7 (深さ 5) ... ★★列挙： 4 (深さ 4)」)\n",
        "\n",
        "10. 再帰呼出プログラムでの頂点からの撤退  \n",
        "「printf(\"  (頂点 %d にて) することが無くなったのでこの頂点から撤退します．\\n\", CurrentRoom);」という文を dfs_recursive_J.c に追記するとしたらどこが適切か示せ．\n",
        "\n",
        "\n",
        "# 出典\n",
        "\n",
        "筑波大学工学システム学類  \n",
        "データ構造とアルゴリズム  \n",
        "担当：亀田能成  \n",
        "2020/05/19.\n"
      ]
    }
  ]
}