Copy_of_1001_prim_kruskal.ipynb

{
  "nbformat": 4,
  "nbformat_minor": 0,
  "metadata": {
    "colab": {
      "name": "Copy of 1001-prim-kruskal.ipynb",
      "provenance": [],
      "authorship_tag": "ABX9TyPlBi7wjlIchLjvVHG6Cpr+",
      "include_colab_link": true
    },
    "kernelspec": {
      "name": "python3",
      "display_name": "Python 3"
    },
    "language_info": {
      "name": "python"
    }
  },
  "cells": [
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "view-in-github",
        "colab_type": "text"
      },
      "source": [
        "<a href=\"https://colab.research.google.com/github/lmcanavals/acomplex/blob/main/Copy_of_1001_prim_kruskal.ipynb\" target=\"_parent\"><img src=\"https://colab.research.google.com/assets/colab-badge.svg\" alt=\"Open In Colab\"/></a>"
      ]
    },
    {
      "cell_type": "code",
      "source": [
        "!git clone https://github.com/lmcanavals/acomplex.git"
      ],
      "metadata": {
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "id": "ZoK0v2vxmcwa",
        "outputId": "1297eb6a-8091-4e6f-e37b-b2799f87f399"
      },
      "execution_count": null,
      "outputs": [
        {
          "output_type": "stream",
          "name": "stdout",
          "text": [
            "fatal: destination path 'acomplex' already exists and is not an empty directory.\n"
          ]
        }
      ]
    },
    {
      "cell_type": "code",
      "source": [
        "%%bash\n",
        "cd acomplex\n",
        "git pull"
      ],
      "metadata": {
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "id": "6MBZzS8u6qaq",
        "outputId": "b22be3f6-f9bf-4e81-8fa1-bf8ee6c03a51"
      },
      "execution_count": null,
      "outputs": [
        {
          "output_type": "stream",
          "name": "stdout",
          "text": [
            "Already up to date.\n"
          ]
        }
      ]
    },
    {
      "cell_type": "code",
      "source": [
        "from acomplex.graphstuff import adjlShow\n",
        "from acomplex.disjointset import DisjointSet"
      ],
      "metadata": {
        "id": "ia64gqJEmh43"
      },
      "execution_count": null,
      "outputs": []
    },
    {
      "cell_type": "code",
      "execution_count": null,
      "metadata": {
        "id": "T1pYiweGlgtE"
      },
      "outputs": [],
      "source": [
        "import heapq as h\n",
        "import math\n",
        "\n",
        "def prim(G):\n",
        "    n = len(G)\n",
        "    visited = [False]*n\n",
        "    path = [-1]*n\n",
        "    cost = [math.inf]*n\n",
        "\n",
        "    cost[0] = 0\n",
        "    q = [(0, 0)]\n",
        "    while q:\n",
        "        _, u = h.heappop(q)\n",
        "        if visited[u]: continue\n",
        "        visited[u] = True\n",
        "        for v, w in G[u]:\n",
        "            if not visited[v] and w < cost[v]:\n",
        "                cost[v] = w\n",
        "                path[v] = u\n",
        "                h.heappush(q, (w, v))\n",
        "\n",
        "    return path "
      ]
    },
    {
      "cell_type": "code",
      "source": [
        "%%file 1001a.al\n",
        "2 9 3 9 4 8\n",
        "2 6 3 1 6 8\n",
        "0 9 1 6 4 4 5 2 6 5\n",
        "0 9 1 1 7 4\n",
        "0 8 2 4 6 1\n",
        "2 2\n",
        "1 8 2 5 4 1\n",
        "3 4"
      ],
      "metadata": {
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "id": "9qMc7FfnnHBt",
        "outputId": "51ec8c5e-60a9-49a7-d977-82cc99d7abdd"
      },
      "execution_count": null,
      "outputs": [
        {
          "output_type": "stream",
          "name": "stdout",
          "text": [
            "Overwriting 1001a.al\n"
          ]
        }
      ]
    },
    {
      "cell_type": "code",
      "source": [
        "with open(\"1001a.al\") as f:\n",
        "  G = []\n",
        "  for line in f:\n",
        "    if line == '-\\n':\n",
        "      G.append([])\n",
        "    else:\n",
        "      nums = [int(x) for x in line.split()]\n",
        "      G.append([(nums[i], nums[i+1]) for i in range(0, len(nums), 2)])\n",
        "\n",
        "  for x in G:\n",
        "    print(x)"
      ],
      "metadata": {
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "id": "PNTCwB52ncGN",
        "outputId": "aedf8ebd-b66a-4ba7-d564-a5544c8bb728"
      },
      "execution_count": null,
      "outputs": [
        {
          "output_type": "stream",
          "name": "stdout",
          "text": [
            "[(2, 9), (3, 9), (4, 8)]\n",
            "[(2, 6), (3, 1), (6, 8)]\n",
            "[(0, 9), (1, 6), (4, 4), (5, 2), (6, 5)]\n",
            "[(0, 9), (1, 1), (7, 4)]\n",
            "[(0, 8), (2, 4), (6, 1)]\n",
            "[(2, 2)]\n",
            "[(1, 8), (2, 5), (4, 1)]\n",
            "[(3, 4)]\n"
          ]
        }
      ]
    },
    {
      "cell_type": "code",
      "source": [
        "adjlShow(G, weighted=True, layout=\"neato\")"
      ],
      "metadata": {
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 252
        },
        "id": "mf5_JbXWnfSi",
        "outputId": "f3d6552b-12f4-4dda-f698-affa6cbf3303"
      },
      "execution_count": null,
      "outputs": [
        {
          "output_type": "execute_result",
          "data": {
            "text/plain": [
              "<graphviz.dot.Graph at 0x7fda9c1384d0>"
            ],
            "image/svg+xml": "<?xml version=\"1.0\" encoding=\"UTF-8\" standalone=\"no\"?>\n<!DOCTYPE svg PUBLIC \"-//W3C//DTD SVG 1.1//EN\"\n \"http://www.w3.org/Graphics/SVG/1.1/DTD/svg11.dtd\">\n<!-- Generated by graphviz version 2.40.1 (20161225.0304)\n -->\n<!-- Title: G Pages: 1 -->\n<svg width=\"314pt\" height=\"173pt\"\n viewBox=\"0.00 0.00 314.01 172.56\" xmlns=\"http://www.w3.org/2000/svg\" xmlns:xlink=\"http://www.w3.org/1999/xlink\">\n<g id=\"graph0\" class=\"graph\" transform=\"scale(1 1) rotate(0) translate(4 168.5635)\">\n<title>G</title>\n<polygon fill=\"#ffffff\" stroke=\"transparent\" points=\"-4,4 -4,-168.5635 310.0138,-168.5635 310.0138,4 -4,4\"/>\n<!-- 0 -->\n<g id=\"node1\" class=\"node\">\n<title>0</title>\n<ellipse fill=\"none\" stroke=\"#ff4500\" cx=\"141.7257\" cy=\"-150.1827\" rx=\"15.6129\" ry=\"12.0417\"/>\n<text text-anchor=\"middle\" x=\"141.7257\" y=\"-148.2827\" font-family=\"monospace\" font-size=\"8.00\" fill=\"#7b68ee\">0</text>\n</g>\n<!-- 2 -->\n<g id=\"node3\" class=\"node\">\n<title>2</title>\n<ellipse fill=\"none\" stroke=\"#ff4500\" cx=\"91.2569\" cy=\"-75.5692\" rx=\"15.6129\" ry=\"12.0417\"/>\n<text text-anchor=\"middle\" x=\"91.2569\" y=\"-73.6692\" font-family=\"monospace\" font-size=\"8.00\" fill=\"#7b68ee\">2</text>\n</g>\n<!-- 0&#45;&#45;2 -->\n<g id=\"edge1\" class=\"edge\">\n<title>0&#45;&#45;2</title>\n<path fill=\"none\" stroke=\"#c0c0c0\" d=\"M134.4948,-139.4924C124.9007,-125.3084 108.0618,-100.4137 98.4744,-86.2397\"/>\n<text text-anchor=\"middle\" x=\"113.4846\" y=\"-115.466\" font-family=\"monospace\" font-size=\"8.00\" fill=\"#000000\">9</text>\n</g>\n<!-- 3 -->\n<g id=\"node4\" class=\"node\">\n<title>3</title>\n<ellipse fill=\"none\" stroke=\"#ff4500\" cx=\"220.9227\" cy=\"-123.5602\" rx=\"15.6129\" ry=\"12.0417\"/>\n<text text-anchor=\"middle\" x=\"220.9227\" y=\"-121.6602\" font-family=\"monospace\" font-size=\"8.00\" fill=\"#7b68ee\">3</text>\n</g>\n<!-- 0&#45;&#45;3 -->\n<g id=\"edge2\" class=\"edge\">\n<title>0&#45;&#45;3</title>\n<path fill=\"none\" stroke=\"#c0c0c0\" d=\"M156.2517,-145.2997C170.5414,-140.4962 192.231,-133.2051 206.4888,-128.4123\"/>\n<text text-anchor=\"middle\" x=\"178.3703\" y=\"-139.456\" font-family=\"monospace\" font-size=\"8.00\" fill=\"#000000\">9</text>\n</g>\n<!-- 4 -->\n<g id=\"node5\" class=\"node\">\n<title>4</title>\n<ellipse fill=\"none\" stroke=\"#ff4500\" cx=\"133.1521\" cy=\"-88.2024\" rx=\"15.6129\" ry=\"12.0417\"/>\n<text text-anchor=\"middle\" x=\"133.1521\" y=\"-86.3024\" font-family=\"monospace\" font-size=\"8.00\" fill=\"#7b68ee\">4</text>\n</g>\n<!-- 0&#45;&#45;4 -->\n<g id=\"edge3\" class=\"edge\">\n<title>0&#45;&#45;4</title>\n<path fill=\"none\" stroke=\"#c0c0c0\" d=\"M140.0319,-137.9373C138.5288,-127.0713 136.3445,-111.2805 134.8424,-100.4222\"/>\n<text text-anchor=\"middle\" x=\"134.4372\" y=\"-121.7798\" font-family=\"monospace\" font-size=\"8.00\" fill=\"#000000\">8</text>\n</g>\n<!-- 1 -->\n<g id=\"node2\" class=\"node\">\n<title>1</title>\n<ellipse fill=\"none\" stroke=\"#ff4500\" cx=\"182.8246\" cy=\"-49.5647\" rx=\"15.6129\" ry=\"12.0417\"/>\n<text text-anchor=\"middle\" x=\"182.8246\" y=\"-47.6647\" font-family=\"monospace\" font-size=\"8.00\" fill=\"#7b68ee\">1</text>\n</g>\n<!-- 1&#45;&#45;2 -->\n<g id=\"edge4\" class=\"edge\">\n<title>1&#45;&#45;2</title>\n<path fill=\"none\" stroke=\"#c0c0c0\" d=\"M168.1127,-53.7428C151.0251,-58.5955 123.0042,-66.5532 105.9323,-71.4015\"/>\n<text text-anchor=\"middle\" x=\"134.0225\" y=\"-65.1722\" font-family=\"monospace\" font-size=\"8.00\" fill=\"#000000\">6</text>\n</g>\n<!-- 1&#45;&#45;3 -->\n<g id=\"edge5\" class=\"edge\">\n<title>1&#45;&#45;3</title>\n<path fill=\"none\" stroke=\"#c0c0c0\" d=\"M188.6109,-60.8031C195.7716,-74.7109 207.8962,-98.2597 215.0819,-112.2162\"/>\n<text text-anchor=\"middle\" x=\"198.8464\" y=\"-89.1096\" font-family=\"monospace\" font-size=\"8.00\" fill=\"#000000\">1</text>\n</g>\n<!-- 6 -->\n<g id=\"node7\" class=\"node\">\n<title>6</title>\n<ellipse fill=\"none\" stroke=\"#ff4500\" cx=\"126.0814\" cy=\"-12.0208\" rx=\"15.6129\" ry=\"12.0417\"/>\n<text text-anchor=\"middle\" x=\"126.0814\" y=\"-10.1208\" font-family=\"monospace\" font-size=\"8.00\" fill=\"#7b68ee\">6</text>\n</g>\n<!-- 1&#45;&#45;6 -->\n<g id=\"edge6\" class=\"edge\">\n<title>1&#45;&#45;6</title>\n<path fill=\"none\" stroke=\"#c0c0c0\" d=\"M170.7908,-41.6026C161.1613,-35.2313 147.7228,-26.3397 138.0978,-19.9714\"/>\n<text text-anchor=\"middle\" x=\"151.4443\" y=\"-33.387\" font-family=\"monospace\" font-size=\"8.00\" fill=\"#000000\">8</text>\n</g>\n<!-- 2&#45;&#45;4 -->\n<g id=\"edge7\" class=\"edge\">\n<title>2&#45;&#45;4</title>\n<path fill=\"none\" stroke=\"#c0c0c0\" d=\"M105.9098,-79.9877C109.9684,-81.2115 114.3745,-82.5401 118.4366,-83.765\"/>\n<text text-anchor=\"middle\" x=\"109.1732\" y=\"-84.4764\" font-family=\"monospace\" font-size=\"8.00\" fill=\"#000000\">4</text>\n</g>\n<!-- 5 -->\n<g id=\"node6\" class=\"node\">\n<title>5</title>\n<ellipse fill=\"none\" stroke=\"#ff4500\" cx=\"15.5563\" cy=\"-81.4441\" rx=\"15.6129\" ry=\"12.0417\"/>\n<text text-anchor=\"middle\" x=\"15.5563\" y=\"-79.5441\" font-family=\"monospace\" font-size=\"8.00\" fill=\"#7b68ee\">5</text>\n</g>\n<!-- 2&#45;&#45;5 -->\n<g id=\"edge8\" class=\"edge\">\n<title>2&#45;&#45;5</title>\n<path fill=\"none\" stroke=\"#c0c0c0\" d=\"M75.5717,-76.7865C62.5796,-77.7948 44.208,-79.2206 31.2215,-80.2284\"/>\n<text text-anchor=\"middle\" x=\"50.3966\" y=\"-81.1075\" font-family=\"monospace\" font-size=\"8.00\" fill=\"#000000\">2</text>\n</g>\n<!-- 2&#45;&#45;6 -->\n<g id=\"edge9\" class=\"edge\">\n<title>2&#45;&#45;6</title>\n<path fill=\"none\" stroke=\"#c0c0c0\" d=\"M97.3228,-64.4999C103.6367,-52.9783 113.476,-35.0234 119.8504,-23.3912\"/>\n<text text-anchor=\"middle\" x=\"105.5866\" y=\"-46.5455\" font-family=\"monospace\" font-size=\"8.00\" fill=\"#000000\">5</text>\n</g>\n<!-- 7 -->\n<g id=\"node8\" class=\"node\">\n<title>7</title>\n<ellipse fill=\"none\" stroke=\"#ff4500\" cx=\"290.4574\" cy=\"-152.5427\" rx=\"15.6129\" ry=\"12.0417\"/>\n<text text-anchor=\"middle\" x=\"290.4574\" y=\"-150.6427\" font-family=\"monospace\" font-size=\"8.00\" fill=\"#7b68ee\">7</text>\n</g>\n<!-- 3&#45;&#45;7 -->\n<g id=\"edge10\" class=\"edge\">\n<title>3&#45;&#45;7</title>\n<path fill=\"none\" stroke=\"#c0c0c0\" d=\"M234.6605,-129.2863C246.8509,-134.3673 264.5664,-141.7512 276.7481,-146.8286\"/>\n<text text-anchor=\"middle\" x=\"252.7043\" y=\"-140.6574\" font-family=\"monospace\" font-size=\"8.00\" fill=\"#000000\">4</text>\n</g>\n<!-- 4&#45;&#45;6 -->\n<g id=\"edge11\" class=\"edge\">\n<title>4&#45;&#45;6</title>\n<path fill=\"none\" stroke=\"#c0c0c0\" d=\"M132.0161,-75.9625C130.7044,-61.8303 128.5584,-38.7092 127.2381,-24.4834\"/>\n<text text-anchor=\"middle\" x=\"126.6271\" y=\"-52.8229\" font-family=\"monospace\" font-size=\"8.00\" fill=\"#000000\">1</text>\n</g>\n</g>\n</svg>\n"
          },
          "metadata": {},
          "execution_count": 7
        }
      ]
    },
    {
      "cell_type": "code",
      "source": [
        "path = prim(G)\n",
        "print(path)\n",
        "adjlShow(G, weighted=True, path=path, layout=\"neato\")"
      ],
      "metadata": {
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 269
        },
        "id": "XNx53tgPnlNm",
        "outputId": "0f48e480-1525-4fc5-b4df-cb08d3bd5a2d"
      },
      "execution_count": null,
      "outputs": [
        {
          "output_type": "stream",
          "name": "stdout",
          "text": [
            "[-1, 2, 4, 1, 0, 2, 4, 3]\n"
          ]
        },
        {
          "output_type": "execute_result",
          "data": {
            "text/plain": [
              "<graphviz.dot.Graph at 0x7fda9c1301d0>"
            ],
            "image/svg+xml": "<?xml version=\"1.0\" encoding=\"UTF-8\" standalone=\"no\"?>\n<!DOCTYPE svg PUBLIC \"-//W3C//DTD SVG 1.1//EN\"\n \"http://www.w3.org/Graphics/SVG/1.1/DTD/svg11.dtd\">\n<!-- Generated by graphviz version 2.40.1 (20161225.0304)\n -->\n<!-- Title: G Pages: 1 -->\n<svg width=\"314pt\" height=\"173pt\"\n viewBox=\"0.00 0.00 314.01 172.56\" xmlns=\"http://www.w3.org/2000/svg\" xmlns:xlink=\"http://www.w3.org/1999/xlink\">\n<g id=\"graph0\" class=\"graph\" transform=\"scale(1 1) rotate(0) translate(4 168.5635)\">\n<title>G</title>\n<polygon fill=\"#ffffff\" stroke=\"transparent\" points=\"-4,4 -4,-168.5635 310.0138,-168.5635 310.0138,4 -4,4\"/>\n<!-- 0 -->\n<g id=\"node1\" class=\"node\">\n<title>0</title>\n<ellipse fill=\"none\" stroke=\"#ff4500\" cx=\"141.7257\" cy=\"-150.1827\" rx=\"15.6129\" ry=\"12.0417\"/>\n<text text-anchor=\"middle\" x=\"141.7257\" y=\"-148.2827\" font-family=\"monospace\" font-size=\"8.00\" fill=\"#7b68ee\">0</text>\n</g>\n<!-- 2 -->\n<g id=\"node3\" class=\"node\">\n<title>2</title>\n<ellipse fill=\"none\" stroke=\"#ff4500\" cx=\"91.2569\" cy=\"-75.5692\" rx=\"15.6129\" ry=\"12.0417\"/>\n<text text-anchor=\"middle\" x=\"91.2569\" y=\"-73.6692\" font-family=\"monospace\" font-size=\"8.00\" fill=\"#7b68ee\">2</text>\n</g>\n<!-- 0&#45;&#45;2 -->\n<g id=\"edge8\" class=\"edge\">\n<title>0&#45;&#45;2</title>\n<path fill=\"none\" stroke=\"#c0c0c0\" d=\"M134.4948,-139.4924C124.9007,-125.3084 108.0618,-100.4137 98.4744,-86.2397\"/>\n<text text-anchor=\"middle\" x=\"113.4846\" y=\"-115.466\" font-family=\"monospace\" font-size=\"8.00\" fill=\"#000000\">9</text>\n</g>\n<!-- 3 -->\n<g id=\"node4\" class=\"node\">\n<title>3</title>\n<ellipse fill=\"none\" stroke=\"#ff4500\" cx=\"220.9227\" cy=\"-123.5602\" rx=\"15.6129\" ry=\"12.0417\"/>\n<text text-anchor=\"middle\" x=\"220.9227\" y=\"-121.6602\" font-family=\"monospace\" font-size=\"8.00\" fill=\"#7b68ee\">3</text>\n</g>\n<!-- 0&#45;&#45;3 -->\n<g id=\"edge9\" class=\"edge\">\n<title>0&#45;&#45;3</title>\n<path fill=\"none\" stroke=\"#c0c0c0\" d=\"M156.2517,-145.2997C170.5414,-140.4962 192.231,-133.2051 206.4888,-128.4123\"/>\n<text text-anchor=\"middle\" x=\"178.3703\" y=\"-139.456\" font-family=\"monospace\" font-size=\"8.00\" fill=\"#000000\">9</text>\n</g>\n<!-- 4 -->\n<g id=\"node5\" class=\"node\">\n<title>4</title>\n<ellipse fill=\"none\" stroke=\"#ff4500\" cx=\"133.1521\" cy=\"-88.2024\" rx=\"15.6129\" ry=\"12.0417\"/>\n<text text-anchor=\"middle\" x=\"133.1521\" y=\"-86.3024\" font-family=\"monospace\" font-size=\"8.00\" fill=\"#7b68ee\">4</text>\n</g>\n<!-- 0&#45;&#45;4 -->\n<g id=\"edge4\" class=\"edge\">\n<title>0&#45;&#45;4</title>\n<path fill=\"none\" stroke=\"#ffa500\" stroke-width=\"2\" d=\"M140.0319,-137.9373C138.9515,-130.1274 137.5193,-119.7733 136.2413,-110.5351\"/>\n<polygon fill=\"#ffa500\" stroke=\"#ffa500\" stroke-width=\"2\" points=\"139.6798,-109.8483 134.8424,-100.4222 132.7458,-110.8075 139.6798,-109.8483\"/>\n<text text-anchor=\"middle\" x=\"135.1366\" y=\"-126.8362\" font-family=\"monospace\" font-size=\"8.00\" fill=\"#000000\">8</text>\n</g>\n<!-- 1 -->\n<g id=\"node2\" class=\"node\">\n<title>1</title>\n<ellipse fill=\"none\" stroke=\"#ff4500\" cx=\"182.8246\" cy=\"-49.5647\" rx=\"15.6129\" ry=\"12.0417\"/>\n<text text-anchor=\"middle\" x=\"182.8246\" y=\"-47.6647\" font-family=\"monospace\" font-size=\"8.00\" fill=\"#7b68ee\">1</text>\n</g>\n<!-- 1&#45;&#45;3 -->\n<g id=\"edge3\" class=\"edge\">\n<title>1&#45;&#45;3</title>\n<path fill=\"none\" stroke=\"#ffa500\" stroke-width=\"2\" d=\"M188.6109,-60.8031C194.373,-71.9945 203.3494,-89.4287 210.3801,-103.0841\"/>\n<polygon fill=\"#ffa500\" stroke=\"#ffa500\" stroke-width=\"2\" points=\"207.3925,-104.9276 215.0819,-112.2162 213.6161,-101.7232 207.3925,-104.9276\"/>\n<text text-anchor=\"middle\" x=\"196.4955\" y=\"-84.5436\" font-family=\"monospace\" font-size=\"8.00\" fill=\"#000000\">1</text>\n</g>\n<!-- 6 -->\n<g id=\"node7\" class=\"node\">\n<title>6</title>\n<ellipse fill=\"none\" stroke=\"#ff4500\" cx=\"126.0814\" cy=\"-12.0208\" rx=\"15.6129\" ry=\"12.0417\"/>\n<text text-anchor=\"middle\" x=\"126.0814\" y=\"-10.1208\" font-family=\"monospace\" font-size=\"8.00\" fill=\"#7b68ee\">6</text>\n</g>\n<!-- 1&#45;&#45;6 -->\n<g id=\"edge10\" class=\"edge\">\n<title>1&#45;&#45;6</title>\n<path fill=\"none\" stroke=\"#c0c0c0\" d=\"M170.7908,-41.6026C161.1613,-35.2313 147.7228,-26.3397 138.0978,-19.9714\"/>\n<text text-anchor=\"middle\" x=\"151.4443\" y=\"-33.387\" font-family=\"monospace\" font-size=\"8.00\" fill=\"#000000\">8</text>\n</g>\n<!-- 2&#45;&#45;1 -->\n<g id=\"edge1\" class=\"edge\">\n<title>2&#45;&#45;1</title>\n<path fill=\"none\" stroke=\"#ffa500\" stroke-width=\"2\" d=\"M105.9688,-71.3911C120.1194,-67.3725 141.768,-61.2245 158.4872,-56.4763\"/>\n<polygon fill=\"#ffa500\" stroke=\"#ffa500\" stroke-width=\"2\" points=\"159.4858,-59.8313 168.1492,-53.7324 157.5734,-53.0975 159.4858,-59.8313\"/>\n<text text-anchor=\"middle\" x=\"129.228\" y=\"-66.5337\" font-family=\"monospace\" font-size=\"8.00\" fill=\"#000000\">6</text>\n</g>\n<!-- 5 -->\n<g id=\"node6\" class=\"node\">\n<title>5</title>\n<ellipse fill=\"none\" stroke=\"#ff4500\" cx=\"15.5563\" cy=\"-81.4441\" rx=\"15.6129\" ry=\"12.0417\"/>\n<text text-anchor=\"middle\" x=\"15.5563\" y=\"-79.5441\" font-family=\"monospace\" font-size=\"8.00\" fill=\"#7b68ee\">5</text>\n</g>\n<!-- 2&#45;&#45;5 -->\n<g id=\"edge5\" class=\"edge\">\n<title>2&#45;&#45;5</title>\n<path fill=\"none\" stroke=\"#ffa500\" stroke-width=\"2\" d=\"M75.5717,-76.7865C65.7261,-77.5506 52.7912,-78.5544 41.4516,-79.4345\"/>\n<polygon fill=\"#ffa500\" stroke=\"#ffa500\" stroke-width=\"2\" points=\"40.9206,-75.9651 31.2215,-80.2284 41.4623,-82.9441 40.9206,-75.9651\"/>\n<text text-anchor=\"middle\" x=\"55.5117\" y=\"-80.7105\" font-family=\"monospace\" font-size=\"8.00\" fill=\"#000000\">2</text>\n</g>\n<!-- 2&#45;&#45;6 -->\n<g id=\"edge11\" class=\"edge\">\n<title>2&#45;&#45;6</title>\n<path fill=\"none\" stroke=\"#c0c0c0\" d=\"M97.3228,-64.4999C103.6367,-52.9783 113.476,-35.0234 119.8504,-23.3912\"/>\n<text text-anchor=\"middle\" x=\"105.5866\" y=\"-46.5455\" font-family=\"monospace\" font-size=\"8.00\" fill=\"#000000\">5</text>\n</g>\n<!-- 7 -->\n<g id=\"node8\" class=\"node\">\n<title>7</title>\n<ellipse fill=\"none\" stroke=\"#ff4500\" cx=\"290.4574\" cy=\"-152.5427\" rx=\"15.6129\" ry=\"12.0417\"/>\n<text text-anchor=\"middle\" x=\"290.4574\" y=\"-150.6427\" font-family=\"monospace\" font-size=\"8.00\" fill=\"#7b68ee\">7</text>\n</g>\n<!-- 3&#45;&#45;7 -->\n<g id=\"edge7\" class=\"edge\">\n<title>3&#45;&#45;7</title>\n<path fill=\"none\" stroke=\"#ffa500\" stroke-width=\"2\" d=\"M234.6605,-129.2863C243.9938,-133.1764 256.5657,-138.4165 267.4133,-142.9378\"/>\n<polygon fill=\"#ffa500\" stroke=\"#ffa500\" stroke-width=\"2\" points=\"266.1713,-146.2119 276.7481,-146.8286 268.8644,-139.7507 266.1713,-146.2119\"/>\n<text text-anchor=\"middle\" x=\"248.0369\" y=\"-138.712\" font-family=\"monospace\" font-size=\"8.00\" fill=\"#000000\">4</text>\n</g>\n<!-- 4&#45;&#45;2 -->\n<g id=\"edge2\" class=\"edge\">\n<title>4&#45;&#45;2</title>\n<path fill=\"none\" stroke=\"#ffa500\" stroke-width=\"2\" d=\"M118.4992,-83.7839C117.6114,-83.5162 116.7069,-83.2435 115.7931,-82.9679\"/>\n<polygon fill=\"#ffa500\" stroke=\"#ffa500\" stroke-width=\"2\" points=\"116.557,-79.5427 105.9723,-80.0065 114.536,-86.2446 116.557,-79.5427\"/>\n<text text-anchor=\"middle\" x=\"114.1461\" y=\"-85.9759\" font-family=\"monospace\" font-size=\"8.00\" fill=\"#000000\">4</text>\n</g>\n<!-- 4&#45;&#45;6 -->\n<g id=\"edge6\" class=\"edge\">\n<title>4&#45;&#45;6</title>\n<path fill=\"none\" stroke=\"#ffa500\" stroke-width=\"2\" d=\"M132.0161,-75.9625C130.9811,-64.8113 129.4266,-48.0635 128.1683,-34.5052\"/>\n<polygon fill=\"#ffa500\" stroke=\"#ffa500\" stroke-width=\"2\" points=\"131.6474,-34.1171 127.2381,-24.4834 124.6773,-34.7641 131.6474,-34.1171\"/>\n<text text-anchor=\"middle\" x=\"127.0922\" y=\"-48.8338\" font-family=\"monospace\" font-size=\"8.00\" fill=\"#000000\">1</text>\n</g>\n</g>\n</svg>\n"
          },
          "metadata": {},
          "execution_count": 8
        }
      ]
    },
    {
      "cell_type": "code",
      "source": [
        "def kruskal(G, k):\n",
        "    n = len(G)\n",
        "    ds = DisjointSet(n)\n",
        "    edges = [(w, u, v) for u in range(n) for v, w in G[u]]\n",
        "    edges.sort()\n",
        "    T = []\n",
        "    links = 0\n",
        "    for _, u, v in edges:\n",
        "        if not ds.sameset(u, v):\n",
        "            T.append((u, v))\n",
        "            ds.union(u, v)\n",
        "            links += 1\n",
        "        if links == n - k: break\n",
        "\n",
        "    return T"
      ],
      "metadata": {
        "id": "sQqWgzpNn6GT"
      },
      "execution_count": null,
      "outputs": []
    },
    {
      "cell_type": "code",
      "source": [
        "path = kruskal(G, 3)\n",
        "print(path)\n",
        "adjlShow(G, weighted=True, path=path, simplepath=False, layout=\"neato\")"
      ],
      "metadata": {
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 269
        },
        "id": "w0tFK4sRuNje",
        "outputId": "38d249df-0b40-4438-ac77-900d9d8bedcd"
      },
      "execution_count": null,
      "outputs": [
        {
          "output_type": "stream",
          "name": "stdout",
          "text": [
            "[(1, 3), (4, 6), (2, 5), (2, 4), (3, 7)]\n"
          ]
        },
        {
          "output_type": "execute_result",
          "data": {
            "text/plain": [
              "<graphviz.dot.Graph at 0x7fda9c140690>"
            ],
            "image/svg+xml": "<?xml version=\"1.0\" encoding=\"UTF-8\" standalone=\"no\"?>\n<!DOCTYPE svg PUBLIC \"-//W3C//DTD SVG 1.1//EN\"\n \"http://www.w3.org/Graphics/SVG/1.1/DTD/svg11.dtd\">\n<!-- Generated by graphviz version 2.40.1 (20161225.0304)\n -->\n<!-- Title: G Pages: 1 -->\n<svg width=\"314pt\" height=\"173pt\"\n viewBox=\"0.00 0.00 314.01 172.56\" xmlns=\"http://www.w3.org/2000/svg\" xmlns:xlink=\"http://www.w3.org/1999/xlink\">\n<g id=\"graph0\" class=\"graph\" transform=\"scale(1 1) rotate(0) translate(4 168.5635)\">\n<title>G</title>\n<polygon fill=\"#ffffff\" stroke=\"transparent\" points=\"-4,4 -4,-168.5635 310.0138,-168.5635 310.0138,4 -4,4\"/>\n<!-- 0 -->\n<g id=\"node1\" class=\"node\">\n<title>0</title>\n<ellipse fill=\"none\" stroke=\"#ff4500\" cx=\"141.7257\" cy=\"-150.1827\" rx=\"15.6129\" ry=\"12.0417\"/>\n<text text-anchor=\"middle\" x=\"141.7257\" y=\"-148.2827\" font-family=\"monospace\" font-size=\"8.00\" fill=\"#7b68ee\">0</text>\n</g>\n<!-- 2 -->\n<g id=\"node3\" class=\"node\">\n<title>2</title>\n<ellipse fill=\"none\" stroke=\"#ff4500\" cx=\"91.2569\" cy=\"-75.5692\" rx=\"15.6129\" ry=\"12.0417\"/>\n<text text-anchor=\"middle\" x=\"91.2569\" y=\"-73.6692\" font-family=\"monospace\" font-size=\"8.00\" fill=\"#7b68ee\">2</text>\n</g>\n<!-- 0&#45;&#45;2 -->\n<g id=\"edge6\" class=\"edge\">\n<title>0&#45;&#45;2</title>\n<path fill=\"none\" stroke=\"#c0c0c0\" d=\"M134.4948,-139.4924C124.9007,-125.3084 108.0618,-100.4137 98.4744,-86.2397\"/>\n<text text-anchor=\"middle\" x=\"113.4846\" y=\"-115.466\" font-family=\"monospace\" font-size=\"8.00\" fill=\"#000000\">9</text>\n</g>\n<!-- 3 -->\n<g id=\"node4\" class=\"node\">\n<title>3</title>\n<ellipse fill=\"none\" stroke=\"#ff4500\" cx=\"220.9227\" cy=\"-123.5602\" rx=\"15.6129\" ry=\"12.0417\"/>\n<text text-anchor=\"middle\" x=\"220.9227\" y=\"-121.6602\" font-family=\"monospace\" font-size=\"8.00\" fill=\"#7b68ee\">3</text>\n</g>\n<!-- 0&#45;&#45;3 -->\n<g id=\"edge7\" class=\"edge\">\n<title>0&#45;&#45;3</title>\n<path fill=\"none\" stroke=\"#c0c0c0\" d=\"M156.2517,-145.2997C170.5414,-140.4962 192.231,-133.2051 206.4888,-128.4123\"/>\n<text text-anchor=\"middle\" x=\"178.3703\" y=\"-139.456\" font-family=\"monospace\" font-size=\"8.00\" fill=\"#000000\">9</text>\n</g>\n<!-- 4 -->\n<g id=\"node5\" class=\"node\">\n<title>4</title>\n<ellipse fill=\"none\" stroke=\"#ff4500\" cx=\"133.1521\" cy=\"-88.2024\" rx=\"15.6129\" ry=\"12.0417\"/>\n<text text-anchor=\"middle\" x=\"133.1521\" y=\"-86.3024\" font-family=\"monospace\" font-size=\"8.00\" fill=\"#7b68ee\">4</text>\n</g>\n<!-- 0&#45;&#45;4 -->\n<g id=\"edge8\" class=\"edge\">\n<title>0&#45;&#45;4</title>\n<path fill=\"none\" stroke=\"#c0c0c0\" d=\"M140.0319,-137.9373C138.5288,-127.0713 136.3445,-111.2805 134.8424,-100.4222\"/>\n<text text-anchor=\"middle\" x=\"134.4372\" y=\"-121.7798\" font-family=\"monospace\" font-size=\"8.00\" fill=\"#000000\">8</text>\n</g>\n<!-- 1 -->\n<g id=\"node2\" class=\"node\">\n<title>1</title>\n<ellipse fill=\"none\" stroke=\"#ff4500\" cx=\"182.8246\" cy=\"-49.5647\" rx=\"15.6129\" ry=\"12.0417\"/>\n<text text-anchor=\"middle\" x=\"182.8246\" y=\"-47.6647\" font-family=\"monospace\" font-size=\"8.00\" fill=\"#7b68ee\">1</text>\n</g>\n<!-- 1&#45;&#45;2 -->\n<g id=\"edge9\" class=\"edge\">\n<title>1&#45;&#45;2</title>\n<path fill=\"none\" stroke=\"#c0c0c0\" d=\"M168.1127,-53.7428C151.0251,-58.5955 123.0042,-66.5532 105.9323,-71.4015\"/>\n<text text-anchor=\"middle\" x=\"134.0225\" y=\"-65.1722\" font-family=\"monospace\" font-size=\"8.00\" fill=\"#000000\">6</text>\n</g>\n<!-- 6 -->\n<g id=\"node7\" class=\"node\">\n<title>6</title>\n<ellipse fill=\"none\" stroke=\"#ff4500\" cx=\"126.0814\" cy=\"-12.0208\" rx=\"15.6129\" ry=\"12.0417\"/>\n<text text-anchor=\"middle\" x=\"126.0814\" y=\"-10.1208\" font-family=\"monospace\" font-size=\"8.00\" fill=\"#7b68ee\">6</text>\n</g>\n<!-- 1&#45;&#45;6 -->\n<g id=\"edge10\" class=\"edge\">\n<title>1&#45;&#45;6</title>\n<path fill=\"none\" stroke=\"#c0c0c0\" d=\"M170.7908,-41.6026C161.1613,-35.2313 147.7228,-26.3397 138.0978,-19.9714\"/>\n<text text-anchor=\"middle\" x=\"151.4443\" y=\"-33.387\" font-family=\"monospace\" font-size=\"8.00\" fill=\"#000000\">8</text>\n</g>\n<!-- 2&#45;&#45;6 -->\n<g id=\"edge11\" class=\"edge\">\n<title>2&#45;&#45;6</title>\n<path fill=\"none\" stroke=\"#c0c0c0\" d=\"M97.3228,-64.4999C103.6367,-52.9783 113.476,-35.0234 119.8504,-23.3912\"/>\n<text text-anchor=\"middle\" x=\"105.5866\" y=\"-46.5455\" font-family=\"monospace\" font-size=\"8.00\" fill=\"#000000\">5</text>\n</g>\n<!-- 3&#45;&#45;1 -->\n<g id=\"edge1\" class=\"edge\">\n<title>3&#45;&#45;1</title>\n<path fill=\"none\" stroke=\"#ffa500\" stroke-width=\"2\" d=\"M215.1364,-112.3219C209.3743,-101.1305 200.3979,-83.6963 193.3672,-70.0409\"/>\n<polygon fill=\"#ffa500\" stroke=\"#ffa500\" stroke-width=\"2\" points=\"196.3548,-68.1974 188.6653,-60.9088 190.1312,-71.4018 196.3548,-68.1974\"/>\n<text text-anchor=\"middle\" x=\"201.2518\" y=\"-93.7814\" font-family=\"monospace\" font-size=\"8.00\" fill=\"#000000\">1</text>\n</g>\n<!-- 4&#45;&#45;2 -->\n<g id=\"edge4\" class=\"edge\">\n<title>4&#45;&#45;2</title>\n<path fill=\"none\" stroke=\"#ffa500\" stroke-width=\"2\" d=\"M118.4992,-83.7839C117.6114,-83.5162 116.7069,-83.2435 115.7931,-82.9679\"/>\n<polygon fill=\"#ffa500\" stroke=\"#ffa500\" stroke-width=\"2\" points=\"116.557,-79.5427 105.9723,-80.0065 114.536,-86.2446 116.557,-79.5427\"/>\n<text text-anchor=\"middle\" x=\"114.1461\" y=\"-85.9759\" font-family=\"monospace\" font-size=\"8.00\" fill=\"#000000\">4</text>\n</g>\n<!-- 5 -->\n<g id=\"node6\" class=\"node\">\n<title>5</title>\n<ellipse fill=\"none\" stroke=\"#ff4500\" cx=\"15.5563\" cy=\"-81.4441\" rx=\"15.6129\" ry=\"12.0417\"/>\n<text text-anchor=\"middle\" x=\"15.5563\" y=\"-79.5441\" font-family=\"monospace\" font-size=\"8.00\" fill=\"#7b68ee\">5</text>\n</g>\n<!-- 5&#45;&#45;2 -->\n<g id=\"edge3\" class=\"edge\">\n<title>5&#45;&#45;2</title>\n<path fill=\"none\" stroke=\"#ffa500\" stroke-width=\"2\" d=\"M31.2415,-80.2269C41.0871,-79.4628 54.022,-78.4589 65.3616,-77.5789\"/>\n<polygon fill=\"#ffa500\" stroke=\"#ffa500\" stroke-width=\"2\" points=\"65.8926,-81.0483 75.5918,-76.7849 65.3509,-74.0693 65.8926,-81.0483\"/>\n<text text-anchor=\"middle\" x=\"45.3016\" y=\"-81.5029\" font-family=\"monospace\" font-size=\"8.00\" fill=\"#000000\">2</text>\n</g>\n<!-- 6&#45;&#45;4 -->\n<g id=\"edge2\" class=\"edge\">\n<title>6&#45;&#45;4</title>\n<path fill=\"none\" stroke=\"#ffa500\" stroke-width=\"2\" d=\"M127.2174,-24.2607C128.2524,-35.4119 129.8068,-52.1597 131.0652,-65.718\"/>\n<polygon fill=\"#ffa500\" stroke=\"#ffa500\" stroke-width=\"2\" points=\"127.5861,-66.1061 131.9954,-75.7398 134.5562,-65.4591 127.5861,-66.1061\"/>\n<text text-anchor=\"middle\" x=\"126.1413\" y=\"-47.5893\" font-family=\"monospace\" font-size=\"8.00\" fill=\"#000000\">1</text>\n</g>\n<!-- 7 -->\n<g id=\"node8\" class=\"node\">\n<title>7</title>\n<ellipse fill=\"none\" stroke=\"#ff4500\" cx=\"290.4574\" cy=\"-152.5427\" rx=\"15.6129\" ry=\"12.0417\"/>\n<text text-anchor=\"middle\" x=\"290.4574\" y=\"-150.6427\" font-family=\"monospace\" font-size=\"8.00\" fill=\"#7b68ee\">7</text>\n</g>\n<!-- 7&#45;&#45;3 -->\n<g id=\"edge5\" class=\"edge\">\n<title>7&#45;&#45;3</title>\n<path fill=\"none\" stroke=\"#ffa500\" stroke-width=\"2\" d=\"M276.7196,-146.8167C267.3863,-142.9265 254.8144,-137.6865 243.9668,-133.1652\"/>\n<polygon fill=\"#ffa500\" stroke=\"#ffa500\" stroke-width=\"2\" points=\"245.2088,-129.891 234.632,-129.2744 242.5157,-136.3523 245.2088,-129.891\"/>\n<text text-anchor=\"middle\" x=\"257.3432\" y=\"-142.5909\" font-family=\"monospace\" font-size=\"8.00\" fill=\"#000000\">4</text>\n</g>\n</g>\n</svg>\n"
          },
          "metadata": {},
          "execution_count": 11
        }
      ]
    },
    {
      "cell_type": "code",
      "source": [
        ""
      ],
      "metadata": {
        "id": "wzoXlqlWuOx-"
      },
      "execution_count": null,
      "outputs": []
    }
  ]
}