DataAlgo2020_006(TopologicalSort).ipynb

{
  "nbformat": 4,
  "nbformat_minor": 0,
  "metadata": {
    "colab": {
      "name": "DataAlgo2020-006(TopologicalSort)",
      "provenance": [],
      "collapsed_sections": [],
      "authorship_tag": "ABX9TyO/bcNvC3c7HleDGarXcaML",
      "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_006(TopologicalSort).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.4. トポロジカルソーティング\n",
        "\n",
        "ここではトポロジカルソーティング(Topological sorting)について学ぶ．\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/\n",
        "%mkdir -p 202004_DataAlgo/DA2020_006\n",
        "%cd       202004_DataAlgo/DA2020_006\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": "NINxYWNgOSaw",
        "colab_type": "text"
      },
      "source": [
        "ここでは，グラフ4を利用する．  \n",
        "頂点数は8．有向グラフ．閉路なし．\n"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "tErWQzIr6Ttp",
        "colab_type": "text"
      },
      "source": [
        "![G4.png](data:image/png;base64,iVBORw0KGgoAAAANSUhEUgAAAV0AAACOCAYAAACSVduCAAAaKklEQVR4Ae2dCbRN1R/HX1maaxUNklQqokiyZEi0SskcEqnIVC0V0lopSiVDhhAhMxEpGTNGlCktZB4yyyxEyJDff333dW/vvuf9vXv277y77zvfvdZd79777vme3/n+9vmcffY5Z++kLFmyyK233urs67rrrpMWLVpI0MrcuXPl8ssvdzYvOXPmlHz58sm///4bqNRge7Hd2H5X9xvUG9SfoBVwArxwNS+IC7xNwhuXS9++faVBgwYuh+hLbOPHj5eqVav6oq0hunPnTilevLicOHFCQy5hNLC92G5sv6sF9Qb1J2gFnAAvXC7grfPQ/eKLLwIL3WrVqjlbf/bs2RNo6GL7XS2oN0GFLnjhckkI6LKl62YVYkuXLV3XaiZbukoZIXSVjFSWIXQJXeUqZS1H6FpbGBIgdJWMVJYhdAld5SplLUfoWlsYEiB0lYxUliF0CV3lKmUtR+haWxgSIHSVjFSWIXQJXeUqZS1H6FpbGBIgdJWMVJYhdAld5SplLUfoWlsYEiB0lYxUliF0CV3lKmUtR+haWxgSIHSVjFSWIXQJXeUqZS1H6FpbGBIgdJWMVJYhdAld5SplLUfoWlsYEiB0lYxUliF0CV3lKmUtF1joag+AQuha10VfBAhdPeiePXtWNUcce0HVTlUx1ceAN23aJHXr1pXSpUsLnv1esmSJSrCErr2NAGSTJk2kcePG9mLnFAhde+guW7ZMnnvuOXn00UelUqVKMnXqVJX8ELp2Nh4+fFhatmwp5cuXN3np3LmznDlzxk703NJq0N23b58UKFBAXn/9dVNx3n33Xbn55ptl/fr11oESut4tRAvqvffeMwfChx56SIoWLepdLMWShK4ddH/77Tezj7zzzjtmn/nkk0/MsIQTJ05M4XTsHwnd2D0LL7Fr1y4pWLCg1K5dW2bOnCmTJk2SIkWKSMOGDVWGMVWDbps2baRcuXLhuM3fOnXqSP369aO+8/KB0PXiWmgZdPUMGjRItm7dKtiZAV6tQuh6hy4Oho888oi8/PLLUelo1aqV+T7qSw8fCF0Ppp1bZM6cOeaMPbnCunXrJFu2bIKzeduiBt1SpUpJyiHVJkyYIPnz55eTJ09axUnoWtkXWfirr74idCNueH+jMZ4uDoa9e/eWjRs3RgUyfPhwKVSoUNR3Xj4Qul5cS3uZP//8U3LlyiVr1qxJ+0fp/I8KdFEJ8+bNK7Nnz45aLU6fbrnlFuvBnoMA3dOnT0d5hw/ag5gTuqks9vSFBnTTWnH16tXlpZdeSuvf6f4+CNA9depUKj/8unsBXXQ4k7dtQCJgFejiKJAnTx5ZunRplAm///676bNC09ymBAG68KpixYoyefLkiFXoS8LOo1UIXR0n/YJunz595IYbbpAtW7ZYBxoE6A4dOlTq1asnq1evjviFflfwQqOgEfnmm2/KE088YbpJcXFNo6hAF317t912m+BKbPKCU6ccOXLIihUrkn8d83tURs2r7jEHkAELbN++XZKSkswLV0yRcLR0n376abW1E7o6VvoB3SFDhsjVV18tP/30k0qQgO6UKVNUtFwVARewz1xxxRWmb3zz5s3mDh1N6L722mumMVSlShXBmbtGUYEujgCA7rx586Ji2rBhg+kHse18RoUsWbKkwOTM+vrwww8la9asEfCiMt1xxx2pOvSjDI7xA6Ebo2Fp/FwbuqNGjTKNE82JJGvUqGFAlFn3F2wX7i4IN1Tw98orrzTdmajn2mXgwIGGcbizwbaoQBf9kffcc0+qOZkWLVpk+i/2799vFWe/fv0MfA4ePCiZ9YWumYsvvjhy5MYRtm3btvLMM89YeZd8YUI3uRve32tCF1fKcd1j/vz53gM6z5K4T37EiBGZdn8BB7p27RqBLhp93bp1k8qVKwsA6Ue5//77zcVPW20V6CIIdDK3b98+Kp4BAwaY+0Jtn7bB6QL6ajJzwVnBNddcY/qOli9fbjYV9wjitEarELo6TmpBF/e2Yyp3PyaQRPeCxv2+Oo75o9KzZ09zzahLly6C60oouAUPrWCbAqAfP348lcTDDz8s3bt3T/V9rF+oQRf3gt59991R03EXK1ZM8CSHbQnChbRDhw7JqlWroqzSvnsBeiVKlIhah80H3qfr/T5d+A5AvP322zYpSHPZIFxIQ7fljh07ojzQuHsBD6ngHurkjUU8XZs9e3aVfl016OL2DSS6cOHC5gmoxx9/3DzaeL4jRpRL6fgQBOiezwYt6OL+aZwplClTxlyswUVJXJU9cuTI+Vab7u8IXe/Q3b17t+mDxLUKPP4bfuEOlubNm0ft8OlOSLIfBgG6yTY38lYDujgDKVu2rBQvXtx08TVr1kxuv/126dSpU2Q9Nm/UoIsg8Gzy4MGDTaVBPyxOwzQKoWvnIrop4CEuSKKLAbkZNmzYeU+hYlkToesdujjgjR071vQ/IjfhF06Nv/32W0I3loqY7Lca0IUcrlONHDlS3nrrLcHTtgsWLEi2Fru3qtC1CyXtpQndtL2J538IXe/Q9TtvbOn67bB3fULXu3e+L6nVveBXoIQuoetX3fKqq9XS9br+9CxH6KbHpTj9htCNk/EXWK3W3QsXWI3Vv9nStbLP14UJXV/ttRMndO3882tpQtcvZ+112dK199AosE9XyUhlGXYvsHtBuUpZyxG61haGBAhdJSOVZQhdQle5SlnLEbrWFoYECF0lI5VlCF1CV7lKWcsRutYWhgQIXSUjlWUIXUJXuUpZyxG61haGBAhdJSOVZQhdQle5SlnLEbrWFoYECF0lI5VlCF1CV7lKWcsRutYWhgQIXSUjlWUIXUJXuUpZyxG61haGBAhdJSOVZQhdQle5SlnLEbrWFoYECF0lI5VlCF1CV7lKWcsRutYWhgQIXSUjlWUIXUJXuUpZyyUMdHPnzm29sX4KYBjC+vXr+7kKJ7W/++47qVmzppOxIahjx46ZQdH/+ecfZ2P0IzCMEY3B4LH9rhbUG9SfoBVwArxwuYC3SZjUDUnSetWpU0dq1aqlplewYEEzy6fLRvoR2/Tp0yVbtmxqPmrlN6yDAbdRgZKPsO+HD65pYqzVPHnymFliw17Y/sUki88++6xarlFvUH+CVpo0aSLghW0+wsuDY+BZ+LPGXzOZ5owZM2T06NFqLzTxMUmcliYGfsF07kErf/31l5lGW8tHbZ0xY8bI0KFDBTNTBK21i5mvsf1anjZt2lQwI7SWHqZfR/0JWgEnwAstHz/99FMBz7T0oAPeJmknBpVxz5492rLUc9SB2bNnm4NsEHdyrZRMnTpV1q5dqyVHHSUH9u7daw6uSnIRGXXoovWD2W1ZguPAr7/+aiYhRSVlid0BTNGzePHi2BfkEr468Pvvv5uzOe2VELrajgZUb82aNdKhQwfZvHlzQB3wvtmErnfv/FyS0PXTXWqrOLBt2zbp2LGjrFy5UkUvKCKErpuZJnTdzAujSuEAprDu3LmzLFy4MMV/+DEtBwjdtJyJ7/eEbnz959pjcODo0aOCK7+Y/p3lwg4Quhf2KB6/IHTj4TrX6dmBU6dOCZ4mHDdunGeNoCxI6LqZaULXzbwwqgs4MHjwYBkxYsQFfhXsfxO6buaf0HUzL4wqHQ5888035iGKM2fOpOPXwfsJoetmzgldN/PCqNLpwLRp06RHjx5Oj1mQzk1R/xmhq26piiChq2IjReLpAB6f/eSTT+TAgQPxDMO5dRO6zqXEBEToupkXRhWjA7iHF/fy7tixI8YlM+/PCV03c0voupkXRuXBAQxM0r59e1m3bp2HpTPfIoSumzkldN3MC6Py6MCuXbvMY8NLlizxqJB5FiN03cwloetmXhiVhQOHDh2SLl26yJw5cyxUEn9RQtfNHBK6buaFUVk6gJkYevbsKZMnT7ZUStzFCV03c0foupkXRqXgAO7fHThwoBksWkEu4SQIXTdTRui6mRdGpejAyJEjZdCgQYqKiSFF6LqZJ0LXzbwwKmUHMFZD7969BWM3BKUQum5mmtB1My+MygcHwlMAYbSyIBRC180sE7pu5oVR+eTAokWLzEMUQZhvj9D1qRJZyhK6lgZy8cRzYPXq1dKuXTvZtGlT4gUfQ8SEbgxmZeBPCd0MNJurcscBTAGEp9dWrFjhTlDKkRC6yoYqyRG6SkZSJvEc2L9/v+lqmD9/fuIFn46ICd10mBSHnxC6cTCdq3THgWPHjpkpgDBEZGYrhK6bGSV03cwLo8pAB06fPi19+vSRsWPHZuBa/V8Voeu/x17WQOh6cY3LZEoHhgwZIsOHD88020bouplKQtfNvDCqODkAUGHiS7R+E70Qum5mkNB1My+MKo4OTJkyRbp3757wUwARunGsRP9n1YTu/zGH/wquA3PnzjV3Nhw8eDBhTSB03UwdoetmXhiVAw4sW7bMDIi+c+dOB6KJPQRCN3bPMmIJQjcjXOY6EtaBDRs2yEcffST4m2iF0HUzY4Sum3lhVA458Mcff8jHH38sS5cudSiqC4dC6F7Yo3j8gtCNh+tcZ8I5gL7dzp07J9QUQISum9WM0HUzL4zKQQcwBRDuapg4caKD0aUOidBN7YkL3xC6LmSBMSSMA//++6/0799fRo0a5XzMhK6bKSJ03cwLo3LcgREjRhj4AsKuFkLXzcwQum7mhVElgAPjx483Mw7/888/TkZL6DqZFiF03cwLo0oQB2bNmiVdu3aVw4cPOxcxoetcSkxAhK6beWFUCeTA4sWLzS1lu3fvdipqQtepdESCIXQjVvANHfDuAKYAwkMULk0BROh6z6efSxK6frpL7UA5sGXLFtPiXb58uRPbTeg6kYZUQRC6qSzhF3TAuwP79u0z4zUsWLDAu4jSkoSukpHKMoSusqGUowNHjhwxT69Nnz49rmYQunG1P82VE7ppWsN/0AHvDpw8eVJ69eoV1ymACF3v+fNzSULXT3epHXgHBg8eLEOHDo2LD4RuXGy/4EoJ3QtaxB/QATsHRo8eLZ9//rmcOXPGTijGpQndGA3LoJ8TuhlkNFcTbAcwBVC3bt0ydAogQtfNOpcw0P3666/FtZvP3Uwpo3LVgZ9++slMAbR///4MCRGgX7NmTYasiytJvwN79uwR8Ey7JGkI4nQMV4AnTZokzZs3l379+pkLE+vXr9eQpwYdyHAHMBA6HqLYvn17ZN0bN26MvNd4M2fOHDP8ZKtWrUzrety4cfLbb79pSFPDwgFwa+zYsfLFF19Is2bNDNfAN61uJxXonj17VurXry9JSUlRr19++cVi07koHYivAzi9bNeunWBGioEDB0revHlVux1at24dtb9g/5kwYUJ8N5prF3ArJcvAN3BOo6hAF4GsW7dOLrvsskiwzz33nEZ81KADcXUA9/I2btw4Urc1B0bfu3ev3HDDDZF9pmzZsuLyEJRxTUQGrxz8CoMXXAPftIoadBHQq6++agK99NJLZcWKFVoxUocOxM2B2bNny7XXXhvZAWvWrKkaC+Z0C+/cM2fOVNWmmHcHVq5cGTnQgmuaRRW6OHJfccUV0qBBA80YqUUH4uLA6dOnBS2eq666KgJGABLdDVoFD2fceOONUq5cOS1J6ig50KhRI8MzcE2zJFWtWlWeeuoplVeVKlXM0aFgwYJSoUIFFc1KlSrJkCFDNLc5IbRwNRt+auVGWwf5RQtAq5/LxaRg23C6v3nzZsE9vGhM5MuXT4oWLapWvytXrmxa0nfeeadUrFhRJd+oN0G8GwKcAC806jrqd6FChQzPNPdD8DYpa9asMmPGDLUXOqFxy42W5ssvvyzPP/+8i/ukrzFhtgMcvLR81NYZOXKk3H333eLqbAx+JefQoUOSJ08ewfZrebpw4UKZN2+emh7qDepP0Ao4AV5o5QUcA8+09KAD3ibddtttTucGR6+XXnrJ6Rj9CA63D9WoUcMPaRXNv/76S0qUKCEnTpxQ0UsUEdw2VKpUKcH2u1pQb1B/glbACdfPisHbpFtvvdXp3PTt2zeQfcRoqeBUxNWyc+dOKV68eOCgi4MMthvb72pBvQliSxfdP+CFywW8JXQdzRCh62ZiCF0384KoCF2l3LClq2SksgxbumzpKlcpazlC19rCkAChq2SksgyhS+gqVylrOULX2sKQAKGrZKSyDKFL6CpXKWs5QtfawpAAoatkpLIMoUvoKlcpazlC19rCkAChq2SksgyhS+gqVylrOULX2sKQAKGrZKSyDKFL6CpXKWs5QtfawpAAoatkpLIMoUvoKlcpazlC19rCkAChq2SksgyhS+gqVylrOULX2sKQAKGrZKSyDKFL6CpXKWu5QEMXg0Rs27bN2kQIELp2NmIYQkwBE34tW7ZMVq1aZT1YNqGrA91jx47J999/b14YMF2j8DFg7y5iXrTly5cLxtNN/tqwYYNo5MeXx4B/+OEHM/5omzZtvG95siUJ3WRmxPgWY7ViNoKHH344Mmzgk08+acaItR2ohtC1hy4G+n/wwQfNWLoYPOiuu+4ycw3GmOZUPyd0U1mS7i969uwp9957r8kLcoMXxtrInj27Gd4z3UJp/FAduhh7FIM+Y5QjTLanUQhd7y4eOHDAjASGnRuQxev48eMqwzESunbQxShl2Ll79OhhEox95/3335cBAwZ4T/i5JQld7xbizGPfvn2CfQevP//8UxYsWGCG89y0aZN34XNLqkN32LBh0rRpU/nss8/kjTfesA4QAoSudxsBxjJlysiuXbu8i6SxJKFrB13MNFuyZMk03LX7mtC18y/l0vXq1ZO2bdum/NrTZ1Xo4lQWp7Fr166VXr16EbqeUvLfQhqjjG3ZskUeffRR1RlswxESunbQrV27tnTo0CFsp+pfQlfPzqVLl5rZQjB4vUZRhW6/fv2kVq1aJq6OHTsSujFk6OjRo6laoxrQxQEQOyCmmqlTp46ZYkZrRw8CdHHKn/KCsNbQjo888ohMnTrVDDYOAL/44osya9asGGpN2j8NAnR3794t2G+SFz/uXoCm1lk7YlWDLjb+gQceMFNbQBg7tlag6F5o2LBhcm8z3XtcGc2dO7e0bt06At/p06ebOdJsNhbzZGFSxRdeeEGmTJliLtIUKVJExc8wdE+dOmUTovPLli9f3hys5s+fH4nVdhBzzL0GDcyPhp161KhR0qlTJ8mWLZtMmDAhsh6vbwBdzanivcbh53K9e/eW++67T9ClGZ4yqnHjxtKnTx+11aJvF1Mz4Y4fraIG3W7dugmO1uGCCtS8efPwR6u/aEHXrVtXDh48mGlfS5Ysicw2myNHDmnXrp3pF7edrgettFdeeUX+/vvvSA7wHa7E4rTJpqCfuFixYuYgkZlzg6l5MANwlixZzNkCpknHnQZoaXktmPIHB9lnnnkmSqJ9+/Zy//33W9/OV61aNRkxYkSm3V9Q37p06RLZZwoXLixjxowxDNK4EBlOypdffmkOjuHPGn9VoIsWT4ECBcwVPuzcaPV+8MEHZqZY3NeGaaxtCuY8wgUHHMEy6+vDDz8MTViXlBSpSDlz5vRtQk7cBmNbOdEKyJ8/v+AWm8yaF2zXPffcE8kJ4Hv99debCTlxVdumYEbhyZMnR0ngvtBcuXJZAR2COFhjgsbMnBc08pCP8Oviiy+Wm266yZw1RJlq8QGNPcx4rVlUoIvT4FtuuUVwGvb4448L7gPFdNKoPI899pj8+OOPVjGj4uC0ITOXHTt2RCoPTv+/+eYb01KpXr26L5uNU1vbCfxwsEWLL7MX3P2BHRtnB++88465UIzWL7bfpmBfwR0MyQseWsHpLG7QtynoXkB3UmYuOANGXi666CLBfrJo0SKpX7++4HuNgsYiDrjo+tEsKtDFhQU89bRx40bz2rp1q7Rs2VJwmwWunqfs7I51A4Jwy9j69esFLR+0PuEnCp5SqlKlSqx2Rf0eF9K+++67qO9waoZW9OLFi6O+j/VDuE83HG+syyfC79H3iovDuD6Buhwutn260EEXUsqDKvonMX06LuDZlCBcSMMBCw28n3/+OWJVo0aN1CamRL6xn+DsQ7OoQPd8AaFvCvfrapQgQBfgwi13yYvG3Qu4+HPJJZfI8OHDzcUG9ENWqFDB7Oy2O3ZQoJvy0U/kSgO68A874NChQ82BFq1cTM/dv3//5NXA0/sgQDdlXmCU5t0L06ZNkyuvvNI8HOEpCWks5Bt0Bw0aJJ07d05jtbF9HQTons8RDehCF1fD0YouXbq0ucMEfWG2/ZHQDQJ0z5cXLehCe/bs2SY3gDguBuFWS40SBOiezydN6I4bN04qVapkfU0qZZy+QRenZbYtqXCwhG7YCe9/cVsXbh9DN5BWIXTt+nTDecAZDnKjcSAMaxK6YSe8/8UdJuCYdvENupqBErqabuppEbo60NXLyH9KhO5/Xrj2jtB1LSPJ4tHqXkgmqfqW0CV0VSuUgphm94JCOOeVIHTPa4sbXxK6buQhZRSafboptbU+s6Wr5aS+DqGr76maIqGrZqWqEKGraqeqGFu6SnayT1fJSGUZdi+we0G5SlnLEbrWFoYECF0lI5VlCF1CV7lKWcsRutYWhgQIXSUjlWUIXUJXuUpZyxG61haGBAhdJSOVZQhdQle5SlnLEbrWFoYECF0lI5VlCF1CV7lKWcsRutYWhgQIXSUjlWUIXUJXuUpZyxG61haGBAhdJSOVZQhdQle5SlnLEbrWFoYECF0lI5VlCF1CV7lKWcsRutYWhgQIXSUjlWUIXUJXuUpZyxG61haGBDBYMcwMWsETaZjrytWC2Q0wJCGe0ApSCT+RZju7g5+eod6g/gStgBMpZ+NwzQM+BuxaRpLFw8eAk5nh0NswdNHSd7Vw7AVXM3NuCnbMcgr6uvq67rrrpEWLFu666FNkc+fOlcsvv9zZvGAqk3z58qmNm+yTjeqyGCca243td3WfQb1B/QlaASfAC1fzgrjA2/8BqG/IJw7zSUIAAAAASUVORK5CYII=)"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "rz4_9z4rOQu4",
        "colab_type": "code",
        "colab": {}
      },
      "source": [
        "%%writefile graph4.h\n",
        "// 8 nodes, directed, 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{0,0,0,0,0,0,1,0}, // 1\n",
        "\t{0,0,0,1,0,0,1,0}, // 2\n",
        "\t{0,0,0,0,0,0,0,1}, // 3\n",
        "\t{0,0,0,0,0,1,0,0}, // 4\n",
        " \t{0,0,0,0,0,0,1,0}, // 5\n",
        "\t{0,0,0,0,0,0,0,1}, // 6\n",
        "\t{0,0,0,0,0,0,0,0}  // 7\n",
        "};"
      ],
      "execution_count": 0,
      "outputs": []
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "4s3BWazcz1FB",
        "colab_type": "text"
      },
      "source": [
        "# トポロジカルソーティング概要\n",
        "\n",
        "**内容**\n",
        "\n",
        "有向で閉路のない（非循環でループのない）グラフを対象とする．\n",
        "グラフのどの頂点aも，その頂点を到着とする頂点が当該頂点aより先に並ぶように順序付けすることをトポロジカルソーティングという．\n",
        "図示すれば，頂点を一列に並べ，全ての辺が同じ向きになるようにすることである．\n",
        "トポロジカルソーティングの解は１つとは限らない．\n",
        "トポロジカルソーティングは，タスクのスケジューリングや，表計算ソフトの計算順序の決定，makeコマンドなどで現れる．各頂点を製造工程，辺を部品の搬送（製造の依存関係）とみなせば，トポロジカルソートの結果は，全製造行程の順序を示すと考えることもできる．この場合，ソートされた結果は，各行程の実行順を示すことになる．\n",
        "\n",
        "**例**\n",
        "\n",
        "日本では宴席に上座下座という概念がある．  \n",
        "今，お互いに余り知り合いではない８人が集まって宴席を設けようということになった．\n",
        "もちろん何人かは知り合いで，仕事上の付き合いがあって，そこには上下関係がある．\n",
        "上の人は上座に（部屋の奥に）座って頂かなくてはいけない．  \n",
        "もちろん，事前に下記のような関係リストを貰えていればいいのだが，残念なことに急な予定だったので貰えなかった．どうすればよいだろうか？  \n",
        "【参加者に０から７の番号を振った場合の上下関係】  \n",
        "０→１，０→４  \n",
        "１→６  \n",
        "２→３，２→６  \n",
        "３→７  \n",
        "４→５  \n",
        "５→６  \n",
        "６→７  \n",
        "\n",
        "外で待っている人たちの中から任意に一人を選び，入口傍に来て貰う．この人をＡさんとしよう．  \n",
        "Ａさんにとって直属上司を探してもらう．もし直属上司が誰もいないなら宴席に入って空いている一番奥の上座に座ってもらう．探してもらうのは直属の上司であって，もっと上の人ではない．もし一人以上見つかったら，そのうちの一人を呼んでもらう．この人をＢさんとしよう．Ｂさんにも入口傍に来て貰う．  \n",
        "Ａさんには待ってもらって，Ｂさんに同じお願いをする．すなわち，Ｂさんにとって直属の上司を探してもらう．あとは同じ．以下繰り返す．なお，例えばＡさんなりＢさんなりに直属上司が数名いる場合は，外にその上司たちがいる限り同じことを繰り返してもらう．外に直属上司がいなくなったら，宴席に入って，空いている一番奥の上座に座ってもらう．  \n",
        "もしこれを繰り返して最初に呼んだＡさんまで入った後，まだ外に人がいるようなら，最初に戻って作業を継続する（外で待っている人たちの中から任意に一人を選び‥）\n",
        "\n",
        "ポイントは，各自は，自分から見て（直属も含めて）上司が全員座り終えるまでは宴席に座ろうとはしない，というところである．上司たちも同じことを繰り返すことで，結果としてトポロジカルソーティングが完成する．\n",
        "\n",
        "**実装**\n",
        "\n",
        "実はトポロジカルソーティングソーティングはこれまでに教えたアルゴリズムそのままで実現できる．厳密には全く同じではないが，変更するのは printf()の位置だけである．元の深さ優先探索アルゴリズムでは「行き順」と言って，当該頂点に初めて到達したときに列挙を宣言する．一方で，変更後では，「戻り順」と言って，当該頂点から最終的に撤退する（スタックから除去する）ときに列挙を宣言する．\n",
        "\n",
        "全く同じアルゴリズムでも宣言するタイミングが違うだけで列挙順の意味がまるで異なるところがアルゴリズム論の妙である．"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "0_o0avWIHZqC",
        "colab_type": "text"
      },
      "source": [
        "# 深さ優先探索プログラム（再帰呼出）\n",
        "\n",
        "**目標**\n",
        "\n",
        "今回の学習に合わせて，再帰呼出を利用したプログラムを再度導入する．  \n",
        "\n",
        "**説明**\n",
        "\n",
        "グラフをG3からG4に変更した以外は，前節で提示したものと全く同一である．\n",
        "\n",
        "**コード**\n",
        "\n",
        "下記の通り．再掲しただけなので，プログラムとしては同じである．  \n",
        "\n",
        "**備考**\n",
        "\n",
        "開始頂点から全頂点が到達可能でない場合，列挙できずに残る．  \n",
        "今回のグラフG4では開始頂点を0にすると，頂点2, 3が列挙されずに残る．"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "Eo2CM8EqZi97",
        "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 \"graph4.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": "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-short_J dfs_recursive-short_J.c"
      ],
      "execution_count": 0,
      "outputs": []
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "CxBI4UbEcB9L",
        "colab_type": "text"
      },
      "source": [
        "開始頂点を0にして実行．（頂点2,3を訪れないまま終わる）"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "O3zzVD4tcA3h",
        "colab_type": "code",
        "colab": {}
      },
      "source": [
        "!./dfs_recursive-short_J 0"
      ],
      "execution_count": 0,
      "outputs": []
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "r60cXNVItEev",
        "colab_type": "text"
      },
      "source": [
        "# トポロジカルソーティング実装\n",
        "\n",
        "**目標**\n",
        "\n",
        "深さ優先探索アルゴリズムを再利用してトポロジカルソーティングを実現する．\n",
        "\n",
        "**説明**\n",
        "\n",
        "アルゴリズムを担うdfs()関数においては，printf()を移動させただけである．  \n",
        "開始頂点から到達できない頂点をソーティングに加えるためにmain()関数側を追記している．\n",
        "それでも元のプログラムと構造としては変わってないことをよく確認すること．\n",
        "\n",
        "**コード**\n",
        "\n",
        "下記の通り．  \n",
        "\n",
        "**備考**\n",
        "\n"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "w1v08T5Ttw-x",
        "colab_type": "code",
        "colab": {}
      },
      "source": [
        "%%writefile topologicalsorting_J.c\n",
        "// Topological sorting (almost same as DFS)\n",
        "// 2020/05 kameda[at]ccs.tsukuba.ac.jp\n",
        "#include <stdio.h> // printf()\n",
        "#include <stdlib.h> // atoi()\n",
        "#include \"graph6dash.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",
        "\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",
        "\n",
        "\t// トポロジカルソーティング\n",
        "\tprintf(\"●●列挙： %d\\n\", CurrentRoom);\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",
        "            return -1;\n",
        "        }\n",
        "    }\n",
        "\n",
        "\tfor (RoomToCheck = 0; RoomToCheck < N; RoomToCheck++)\n",
        "\t\tlisted[RoomToCheck] = 0;\n",
        "\n",
        "\tdfs(startnode); // 開始頂点番号を引数にしてdfs関数を呼び出す\n",
        "\n",
        "    // 残りがあれば再度同じアルゴリズムを実行して対応\n",
        "    {\n",
        "        int r;\n",
        "        for (r = 0; r < N; r++) {\n",
        "            if (listed[r] == 0) {\n",
        "                dfs(r);\n",
        "            }\n",
        "        }\n",
        "    }\n",
        "\n",
        "\treturn 0;\n",
        "}"
      ],
      "execution_count": 0,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "mGDWYHGAuvcs",
        "colab_type": "code",
        "colab": {}
      },
      "source": [
        "!gcc -Wall -o topologicalsorting_J topologicalsorting_J.c"
      ],
      "execution_count": 0,
      "outputs": []
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "A1RsCBCNsrmj",
        "colab_type": "text"
      },
      "source": [
        "開始頂点を0にして実行してみる．"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "dNojxs9Iu6mt",
        "colab_type": "code",
        "colab": {}
      },
      "source": [
        "!./topologicalsorting_J 0"
      ],
      "execution_count": 0,
      "outputs": []
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "nJEhszOkxIoj",
        "colab_type": "text"
      },
      "source": [
        "各自でトポロジカルソーティングが実現できていることを作図等して確認すること．  \n",
        "下図は開始頂点0での実行例に合わせて書き直したグラフである．  \n",
        "トポロジーが維持されたままソーティングされていることに注意する．  \n",
        "グラフ理論的に表現するなら，下図のグラフはG4と同形である．  \n",
        "どの頂点を開始頂点にしてもトポロジカルソーティングが実現できることも確認する．"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "9zH053FixcJ6",
        "colab_type": "text"
      },
      "source": [
        "![G4-ts.png](data:image/png;base64,iVBORw0KGgoAAAANSUhEUgAAAacAAABaCAYAAAAclJnrAAAXSElEQVR4Ae2dB7AVNfuHr4hYsDCOogNYQBAVEbGiiF1EEZCu2JCmiDoWhLGXDxUdHAtWGBULIM2CIIhYQRRUBC8gigoWQIoVEKz5z5P/Xb7D8Wbv7ibLydnvzczOuXezm01+726eJJvNW6IkRFbg9NNPV7Vq1VJ169aVTTSQe0DuAbkHyu6BvffeWzVo0ED9888/kevTig4sqegAif+vAmeccYb66KOP/rtD/hIFRAFRQBRQq1evVscdd5zasGGDMzUETjGkBE4ffPBBjDPkUFFAFBAFsq/AypUrBU6FNDNwmjlzZiGzINcWBUQBUcA7Bb7//nuBUyGtInAqpPpybVFAFPBVAYFTgS3Tpk0b9cknnxQ4F3J5UUAUEAX8UkDgVAB7MPtk3rx5au7cuerYY49Vw4cP15Mifv755wLkRi4pCogCooB/CgicCmSTiy++WFWuXFlVqlRJbbXVVqpGjRpq6dKlBcqNXFYUEAVEAb8UEDgVyB6lpaVqyy23VCUlJXrr379/gXIilxUFRAFRwD8FBE4FtEm3bt00mHbZZRe1fPnyAuZELi0KiAKigF8KCJwKaI8FCxZoOPXr16+AuZBLiwKigCjgnwICpwLb5I477lDffPNNgXMhlxcFRAFRwC8FBE4x7PHXX3+pL774Qs2ZM8fJxmw9Zu0xldw2zcWLF1utQfXHH3+ozz//3DoftuXIPx+NbOG9YsUKxTu+/LQL/T92t50Es3btWrVw4ULvyobe6G4TsDv2L7Sd8q8/f/58vbRO0rIxW5fnNT9dH/6nfqOe8yGsW7dOnXDCCU6zUtKxY0fVtm1b77b27durUaNGJS4slTez6k499VRn22mnnWadVvPmzVWdOnUUy30kDTNmzFA1a9a0zotLbUjrxBNPVAcddJACnknDmWeeqZo0aeJd2fiMoFmzZkmLpc977LHHVL169bwrG3qje9KAvbE79nd9T9mmd8ghh6gePXokLZpatWqV2meffRTPrW1eXJ9P/fbZZ58lLhv1K/Wsi/qfurFatWqqdevWTtKDSyVVq1ZVU6dO9W7r3bu36tWrV2LhP/zwQ30zJU4gxRNZIJHWWNIwYcIE1alTp6Snp3beb7/9pr8FW7NmTeJrcJNjO98CPQPsZhMGDBigbrjhBpskUjkXvdE9acDewJvWs2/h5ZdftnpWvv76a3X88cf7ViydH2xms9Yn9Sv1rIv6/4033lCzZs1Sr7/+upP04FLJvvvu66Xww4YNU3369EmcN1YPb9GiReLz0zqRYQK6v0uWLEl8iVdeecXqgUt84QpO5MNkHmQbOLFE1Pvvv1/BlTZ/9Jdffql7BjZXvvPOO72EE3qje9KAvbH7Tz/9lDSJ1M578cUX1dlnn504fRol9AhduoJInJm8E3HhY9OQo36lnvUxwKUSfBP5GB599FF16aWXJs6ar3D6+++/MwsnKicXcHrvvfcS2z2tExnfp5KyCcDp+uuvt0kilXPR2wWcfvzxx1TyZ5PoCy+84AROPLe+BVs4Ub9Sz/oY4JLAaTNbRuAULjiVpMApXCPXsQIns6JBz0ngZNYojRiBUxqqVpCmwClcIIFTuD5pxAqczKoKnMzapBkjcEpTXUPaAieDMGW7BU7h+qQRK3AyqypwMmuTZozAKU11DWkLnAzClO0WOIXrk0aswMmsqsDJrE2aMQKnNNU1pC1wMghTtlvgFK5PGrECJ7OqAiezNmnGCJzSVNeQtsDJIEzZboFTuD5pxAqczKoKnMzapBkjcEpTXUPaAieDMGW7BU7h+qQRK3AyqypwMmuTZozAKU11DWkLnAzClO0WOIXrk0aswMmsqsDJrE2aMQKnNNU1pC1wMghTtlvgFK5PGrECJ7OqAiezNmnGOIET66mxfEmw/frrr3qNLZvFPym0TytEPP/88+qyyy5T+HJi5WWb4BucKNvdd9/tZHVjH1aIYJmZZ555Ri8TxGoMbNdee60aPXq0jdn0Cve+rRBx7733Kjbb4AucWGF78ODBek3N2267Tf3yyy+2RVO+rBDx8ccfq+uuu05dccUV+v60LphSyqcVIj799FPtTcBFuUjDCZyotFn599BDD9Xb4Ycfrv9nIUib4AucWKjziCOO0LC88sorVfXq1dXs2bMTF80XOLFAI72U/fffX98IGzZsSFym4EQf4EQjiRWyzz//fHX55Zdv3J566qkgm4l+fVu+iMqOlembNm2aqDy5J/kCpy5duuilvR588EHVsmVLdcwxx1it00gZfYDT8OHDVe3atdXNN9+sHnnkEV0u7k9bdxc+wGnZsmXaVtyHwcr9uJexDU7gROYWLVqkW5Y8wPi86dq1q95sMugDnFgQs379+uqHH37YWBT24VgrafAFTlTWDz/8sF5JmAYFPWDb4AOc8EuEe4P169fbFmeT832DU/fu3XVlh8sD2+ADnFjMeL/99tukwqayGzRokFXxCg2nP//8Uy/SzAK0QcCvFw0LVvK2CYWG0++//65X6r/kkkv0aBkNXEYqaBzaNnadwClfXCpuehqM1doEH+BEy/uqq66yKca/zvUFTkHGaIEffPDBmYHTt99+qxdodTEkFGjEr09wmjJliurQoYPCdvgIsg0+wOnCCy/UQ165ZRk6dKj1YruFhhPl4ZnPDzQIR4wYkb871v+FhhMjSNQdua9wAC+9RNveUypwYpivb9++sUQu72Af4IS/lEmTJmmHY7R8Zs6cWV5WY+0zwYmWRq6RwxJ16TKDJfcbN26cGTjRi2dIiB48wylsLkAVBqeo7hRcrUrepk0b3epmnP+UU04Ju1UixYXBKUrZApcZNquS4yuLIa/cQM/C1nmlD3DKLRN/v/rqq6pBgwbWnpULDSfqrNWrV29SvO+++07tueeeChczNsE5nPAaecABBygeGttQHpzefPNNNXny5EhJ27rMACI8+LyYZeiE7bDDDtMTI6I8sKZMki5uJWjhExh3HjJkiDr66KNV1If7tddec+bPKWtwwgMyvmDOPfdc1bNnT+2Vk3eiNh5DsRNwynVDzYP50EMPaS+rUe8HF3B66aWXNvaWcO6WFpy4zi233KIYlqoouIATPYkxY8Zscikc6fFO1KZx4QucGEnCsR8NXoadS0tLNylrkn+AE/VcELjH+/fvr3vUwb6w3zRcZnTr1k21a9cu7LKR4pzDiReZrhz80Yq6+uqrdUEWLFigKPQWW2yhZ7xEKR2z6mzyQoXD+6ajjjpKUeERgAcum22648Dp5JNP1i0LemNAqaSkRFWpUkW3pILZj7w7Wb58uX6/RS+AypFeARsw69y5cxQZKjwmi3Daa6+9FK7sg8AMKZt7gXTQHxAwG/XZZ5/Vk36wW8OGDYPLVPg7cOBAa39OlCNooNGTdwUn3LTjyRZAMCuRsjE8HyUEowFRG1flpWmCE++hcGKZNPgCJ153/Oc//9EOVFu1aqVsJ+igByMEDO0yhEZDbPvtt9d2izqkxgSv/N5qUp05D0/P1JnUW7bBOZwQi5fsLsKTTz6pW70AapttttGi88Ccc845ip4DFTutO6ZCjxw5cuOG0Z9++mkNMdvxeCqe8ePHb1KcG2+8UfEgJw1AjwqFoRnKE2zbbbeduueeexTlfvzxx/XNy5RoysLvqFGj9EZ5eQ921llnJc3CJudlDU4MjeZXZgCdoQabhwZ33VTW2C6wGb916tTRDzgPeUUb9w0VVNIAFHO9ulIx2UKXvJDOkUceqRtNuWVr1KiRhtXYsWP1sxY8c8CRoSk2RjNw800jLl/3OOVEW+773MDkI0Zi6JklDb7AKTf/jJpw36CfTaCHwj2VazMa8Hwags0oO3UkdqMeC2zG7/Tp03X9mq950vwAJoDCc+IiOIUTM9rq1atnNc06t1BU0sDuoosu0r2KwABUylSo9Ix4qObNm6e++uqrjRstFFpwPDC2D+5JJ52kjZubr/vvv193zXP3xfmbVibpMmTBC1+GCoOyYVjiKxomYhp4p06d4lzWeGzW4FReQYESQ330fpIGxtCxG714vnfbeeedtd14X8esJYb5Ktp4gG084XJ9KnFayczW41OAGjVq6CFMm4oOCNCaZ4gI+AX3I8OYS5Ys0cP0PGtz5szRGxXbtGnT9PbWW2+pcePGabjZwInhLoY9cwMVK89HRc9D7jn5f/sIJ/LYo0cP/T1Xfn7j/N+6dWs1ceJEdd999+nGV2A3bEKdSA8Km1FXUt8ENuMXG6L5E088EeeS5R7L8DY9XNtJcLmJO4UTvRm6dDyoLkLusB7vsOiCVqtWLbJBMYotnJitlz+5g3FagJk0AB/eOTEFn8A7J4YJaZFHfS/ickIElQ7vZKJOxggrtw9TyQFR/ofSVL48PDbT5QFb7ke4wIoptHHuMdthPeCB7YOWMC1kZkvRm7YBb/6ECCovwBT13YGLYb2bbrpJt+Rz7y+ePd4d2oRCw4mh0rfffvtfReA7p/y65V8HVbADuARDeNz3QaMJMEUJLob1GD4HJDb3X3l5dQon6M1Hc65CeRMiEIBWQZRgOyGCawC4PfbYQ7c6gv95n8HDnDQEDzIt0vwQFRAu4EQjgpYuM6KCcWLep9i0Un2AExUBjZjARswm4r5kONYm5MMpSIteelTNXEyICK7LLxDOBWZuXJy/8+HEuZQpaoXjYkIEQ6+77bbbxqEuRkToFTJKYBMKDSfuD0aUmFjFs0/gHqVswT2atHzlzdaj0RR1AonthAjAy/0XtU6OU06ncGK4zeZdTH7Gy4NT/jFh/7uAE+mTD2YM8Y6IVipDcTYhDE5R03UBJ1rfTN9t0qSJfnj44BH75U8NjZonjvMBTuTjgQce0DajPLwL6dWrV6RZZ2FlNcEp7Jz8ONdwotdr27Mgj+XBKT/vYf+7gBPp806NhhLviunp0jO0DYWGE/mnkdusWTP9moLeKO/yeI9sG8qDU5w0beGEvbbeemt1zTXX6G/UmHjERo/MdojPKZy4CVwS1Bc4YWzm7tPasVkZIrhpfIFT0HOit8S7ElpbWeg5BTozzMH9SIvcRfARTvRuokz1rqj8vsCJfPKMMcli8eLFFWU7UrwPcAoyGrz3sZnVGKTFb6HhROPorrvu0u9RWTcw2FjyjTrTJjiFk01GyjvXJziVl7+k+3yBU9L8h53nS88pLI9J43yEU9Ky5J/nE5zy82b7v09wsi1L/vmFhlN+flz+L3ByqWbEtARO4UKJy4xwfdKIFTiZVWV4ivcqPLe+BYFTgSwiPSez8C7eOZlTTx4jPadw7Vy/cwq/WvRYgZNZK4GTWZs0Y6TnlKa6hrSl52QQpmy39JzC9UkjVuBkVlXgZNYmzRiBU5rqGtIWOBmEKdstcArXJ41YgZNZVYGTWZs0YwROaaprSFvgZBCmbLfAKVyfNGIFTmZVBU5mbdKMETilqa4hbYGTQZiy3QKncH3SiBU4mVUVOJm1STNG4JSmuoa0BU4GYcp2C5zC9UkjVuBkVlXgZNYmzRiBU5rqGtIWOBmEKdstcArXJ41YgZNZVYGTWZs0YwROaaprSFvgZBCmbLfAKVyfNGIFTmZVBU5mbdKMETilqa4hbYGTQZiy3QKncH3SiBU4mVUVOJm1STNG4JSmuoa0BU4GYcp2C5zC9UkjVuBkVlXgZNYmzRiBU5rqGtIWOBmEKdstcArXJ41YgZNZVYGTWZs0YzSc8BDqY8Ddep8+fRJnDQ+vrD3lY2CtLptVlydMmKC6dOniXdEAL44UWd08acBmgQO1pGmkcd6KFSu0Az6btG+//XZ166232iSRyrnobfOsYG/sjuNM3wIegjt37pw4W3inxgOxjwHvxax0njRQv1LP+hjgUkmVKlXUqFGjrLfRo0crNhdpkcZ5550X2etteeLiPXfXXXfV3jXbtm1r/csNjs+q9u3bW6WFjyEcGNq433jnnXfU7rvvbpWPXE06dOigvZ7m7kvyd8uWLbUfHhtvyHj3xLdUkuvnn4Mre8qWvz/J/3gqxkW6TRg8eLD2Gprk+mmeg97onjRgb/wvYX8X+XRlM/KCzahLkoaVK1dqF+g8t7Zlc/WcBfmoXr26op5LGvBzhjau6myX6cClkt69e6sLLrjAeuvRo4d2X+4iLdIgPXoISQNeZWfNmqWmTp1qveEtFgda2267rZo0aZJ1erNnz7Za5Rh34zNnzrTOB9rgaZSFZKdMmWKdHmmVlpYmNZk+D0+e+GFyYTcqS9x/u0gLH0MLFy60Kht+fHBr7SI/LtNAb3S3Cdid58RFvmg1DxkyxElaNOQYmksaGA3Ab5GLcjVo0EANGjTISVrkh/otqvfs8spP/Uo966rOdpkOXCopL9NJ9q1atcra7XCS626uc1q0aKFKSkrUxIkTN9clN9t18GQ5bdq0zXa9zXUhHjz8+UgoLgXoxS1ZsqS4Mh0ht/S+aJhKiKaAMzhBOoarbEgeLcub/6jJkydrMAGnxo0bO/E+uvlLUf4V6Q1QLuCbtdC1a1c1cuTIrBUr8+Vp3ry5mj9/fubKyWSf6dOnZ65caRXICZxwybvTTjvpSg6/8lkK69evV40aNdoIJypyfE1lJdC7oEyVKlXKXM9X4FScd6nAqTjt5jrXTuDUr1+/jZV3w4YNlc0LcdcFtE1v2bJlqm/fvnp2HNMb+Xvo0KG2yXpx/pw5czbaDUDx0p8x9qwEgVNxWlLgVJx2c51razgtWrRIVa5ceZNKLks9i0DwuXPn6hltwf9Z+B0wYICqXbu22mGHHVStWrVU/fr11bx587JQNF0GgVNxmlLgVJx2c51razjxvQ5DecyZ53sAxviz+HL93XffVXxXkKWwZs0atW7dOg3d8ePHq7Vr1yqGMbMSBE7FaUmBU3HazXWureEUZGjMmDFWH80G6fj6m0U4BVrzDRdTU7MWBE7FaVGBU3HazXWuncFp2LBhes686wz6kl6W4dSxY0fFjMSsBYFTcVpU4FScdnOda4FTREUFThGF8ugwgZNHxoiRFYFTDLEyfKjAKaJxsw4n1iDLWgBOzz33XNaKlfnyCJwyb+JIBRQ4RZJJqSzDqV27dnoZo4hSFM1h3bt3V2PHji2a/EpG/18BPmnI0qzRwK7yEW6gRLRfgVM0nTINJxZ/ZIFMVonI0lazZk39AXWWyvS/UBZWmmE18KwFgVM8iwqcIuqV5Z4T6yLSUuWj3CxtrVu3VgMHDsxUmbJkH1NZWIQ2Sx+DB1WMwClQItqvwCmaTpnuOUWUoOgOY2mmcePGFV2+JcPZVEDgFM+uAqeIemW55xRRgqI7TGbrFZ3JMp1hgVM88wqcIuolcIoolEeHCZw8MoZkRQmc4t0EAqeIegmcIgrl0WECJ4+MIVkROMW8BwROEQUTOEUUyqPDBE4eGUOyInCKeQ8InCIKJnCKKJRHhwmcPDKGZEXgFPMeEDhFFEzgFFEojw4TOHlkDMmKwCnmPSBwiiiYwCmiUB4dJnDyyBiSFYFTzHtA4BRRMIFTRKE8Okzg5JExJCsCp5j3gMApomACp4hCeXSYwMkjY0hWBE4x7wGBU0TBBE4RhfLoMIGTR8aQrAicYt4DAqeIgk2fPl21bds24tFymA8K9OzZU40YMcKHrEgeRAGBU8x7QOAUUbAZM2aoAw88ULszx6W5bP5r0LRpU4FTxPtbDktfAVkhIp7GAqeIei1dulR16NBB957oQcnmvwbYq7S0NKKF5TBRIF0FBE7x9BU4xdNLjhYFRAFRIJECAqd4sgmc4uklR4sCooAokEgBgVM82QRO8fSSo0UBUUAUSKSAwCmebAKneHrJ0aKAKCAKJFJA4BRPNoFTPL3kaFFAFBAFEikgcIonm1M48V2JBFFAFBAFRIF/K9CqVSvF95ISoingFE69evWKdlU5ShQQBUSB/zEFBE7xDO4MTuPHj1c77rijqlu3rmyigdwDcg/IPZB3D1StWlW+u4vBp/8DtVbvAEBhDB4AAAAASUVORK5CYII=)"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "DY_MbwoPf_9h",
        "colab_type": "text"
      },
      "source": [
        "# 節末課題\n",
        "\n",
        "1. アルゴリズムの完全性  \n",
        "閉路のない有向グラフが与えられている限り，本節で示したトポロジカルソーティングを行うアルゴリズムは必ず全頂点を並べて終われることを自分なりに説明せよ．  \n",
        "これは本来は証明問題である．そういう文献等を探してきて読解しそれを説明するだけでも良い．\n",
        "\n",
        "2. 計算量  \n",
        "topologicalsorting_J プログラムの時間計算量と空間計算量を議論せよ．\n",
        "\n",
        "3. 閉路の存在  \n",
        "トポロジカルソーティングに与えるグラフには閉路が存在してはならない． その理由を説明せよ．\n",
        "\n",
        "4. 閉路の扱い  \n",
        "本節の topologicalsorting_J プログラムでは，実際には閉路が含まれるグラフを与えても実行すると結果が出てしまう．これは，閉路があるとトポロジカルソーティングができないはず，ということと矛盾する．\n",
        "本プログラムで実行結果がでるのは，グラフの解釈を都合のよいように勝手に変えているからと考えることができる．それでは，本プログラムでは，閉路が存在するとき，それをどう解釈しているのか，説明を試みよ．\n",
        "\n",
        "\n",
        "# 出典\n",
        "\n",
        "筑波大学工学システム学類  \n",
        "データ構造とアルゴリズム  \n",
        "担当：亀田能成  \n",
        "2020/06/10.\n",
        "\n",
        "\n",
        "\n",
        "\n"
      ]
    }
  ]
}