{
"metadata": {
"name": "",
"signature": "sha256:ecb9bbda12d6fdb3e39aeaf2fe5ef561c8a8f84a2def1400dc3ed8df4da10809"
},
"nbformat": 3,
"nbformat_minor": 0,
"worksheets": [
{
"cells": [
{
"cell_type": "heading",
"level": 1,
"metadata": {},
"source": [
"5 Trees and cut sets"
]
},
{
"cell_type": "heading",
"level": 2,
"metadata": {},
"source": [
"Example 01:Page 263"
]
},
{
"cell_type": "code",
"collapsed": false,
"input": [
"print \"Problem of connecting 19 lamps to a single electric outlet by using extension cords each of which has four outlets\"\n",
"total_lamps=19#Total lamps to be connected to a single electric outlet\n",
"outlets=4#Number of outlets in each extension cord.\n",
"def calc(lamp,outlet):\n",
" return (lamp-1)/(outlets-1)#Since any such connection is a quaternary tree with the single outlet connected to the root of the tree\n",
"print \"Although there are many ways to connect the lights,\",calc(total_lamps,outlets),\"extension cords are always required.\"\n"
],
"language": "python",
"metadata": {},
"outputs": [
{
"output_type": "stream",
"stream": "stdout",
"text": [
"Problem of connecting 19 lamps to a single electric outlet by using extension cords each of which has four outlets\n",
"Although there are many ways to connect the lights, 6 extension cords are always required.\n"
]
}
],
"prompt_number": 1
},
{
"cell_type": "heading",
"level": 2,
"metadata": {},
"source": [
"Example 02:Page 263"
]
},
{
"cell_type": "code",
"collapsed": false,
"input": [
"print \"A hypothetical computer has an instruction which computes the sum of three numbers.\"\n",
"nodes=9#Number of leaf nodes in each regular ternary tree to compute the sum of nine numbers\n",
"num=3#An instruction adds only three numbers\n",
"def calc(node,num):\n",
" return (nodes-1)/(num-1)\n",
"print \"The addition instruction will be executed \",calc(nodes,num),\"times to find the sum of nine numbers\"\n"
],
"language": "python",
"metadata": {},
"outputs": [
{
"output_type": "stream",
"stream": "stdout",
"text": [
"A hypothetical computer has an instruction which computes the sum of three numbers.\n",
"The addition instruction will be executed 4 times to find the sum of nine numbers\n"
]
}
],
"prompt_number": 2
},
{
"cell_type": "heading",
"level": 2,
"metadata": {},
"source": [
"Example 03:Page 278"
]
},
{
"cell_type": "code",
"collapsed": false,
"input": [
"print \"Implementation of Kruskal's algorithm\"\n",
"n=input(\"Enter the number of nodes\")\n",
"print \"Enter the adjacency matrix\"\n",
"cost=[[\"\" for i in range(n+1)]for j in range(n+1)]#Matrix is declared\n",
"parent=[\"\" for i in range(n+1)]#List is declared\n",
"mincost=0#Initially mincost is zero\n",
"for i in range(1,n+1):\n",
" for j in range(1,n+1):#To include n, have used n+1\n",
" print \"Enter the input for\",i,j\n",
" cost[i][j]=input()#Gets input matrix\n",
" if cost[i][j]==0:\n",
" cost[i][j]=999#Max cost is assigned if there is no edge between the specified nodes\n",
"ne=1#Count of visited nodes\n",
"def find(i):\n",
" while parent[i]:\n",
" i=parent[i]\n",
" return i\n",
"def uni(i,j):\n",
" if i!=j:\n",
" parent[j]=i\n",
" return 1\n",
" return 0\n",
"\n",
"print \"\\nThe edges of the minimum cost spanning tree is\"\n",
"while ne<n:\n",
" min=999\n",
" for i in range(1,n+1):\n",
" for j in range(1,n+1):\n",
" if cost[i][j]<min:\n",
" min=cost[i][j]#If the new node has minimum value,takes the new value\n",
" global a\n",
" global v\n",
" global b\n",
" a=i\n",
" global u\n",
" u=i\n",
" b=j\n",
" v=j\n",
" u=find(u)\n",
" v=find(v)\n",
" if uni(u,v):\n",
" print \"\\nEdge\",ne,\"(\",a,\" ,\",b,\")=\",min\n",
" ne=ne+1\n",
" mincost=mincost+min\n",
" cost[a][b]=cost[b][a]=999\n",
"print \"\\nMinimum cost=\",mincost\n",
"\n"
],
"language": "python",
"metadata": {},
"outputs": [
{
"output_type": "stream",
"stream": "stdout",
"text": [
"Implementation of Kruskal's algorithm\n"
]
},
{
"name": "stdout",
"output_type": "stream",
"stream": "stdout",
"text": [
"Enter the number of nodes9\n"
]
},
{
"output_type": "stream",
"stream": "stdout",
"text": [
"Enter the adjacency matrix\n",
"Enter the input for 1 1\n"
]
},
{
"name": "stdout",
"output_type": "stream",
"stream": "stdout",
"text": [
"0\n"
]
},
{
"output_type": "stream",
"stream": "stdout",
"text": [
"Enter the input for 1 2\n"
]
},
{
"name": "stdout",
"output_type": "stream",
"stream": "stdout",
"text": [
"4\n"
]
},
{
"output_type": "stream",
"stream": "stdout",
"text": [
"Enter the input for 1 3\n"
]
},
{
"name": "stdout",
"output_type": "stream",
"stream": "stdout",
"text": [
"0\n"
]
},
{
"output_type": "stream",
"stream": "stdout",
"text": [
"Enter the input for 1 4\n"
]
},
{
"name": "stdout",
"output_type": "stream",
"stream": "stdout",
"text": [
"0\n"
]
},
{
"output_type": "stream",
"stream": "stdout",
"text": [
"Enter the input for 1 5\n"
]
},
{
"name": "stdout",
"output_type": "stream",
"stream": "stdout",
"text": [
"0\n"
]
},
{
"output_type": "stream",
"stream": "stdout",
"text": [
"Enter the input for 1 6\n"
]
},
{
"name": "stdout",
"output_type": "stream",
"stream": "stdout",
"text": [
"0\n"
]
},
{
"output_type": "stream",
"stream": "stdout",
"text": [
"Enter the input for 1 7\n"
]
},
{
"name": "stdout",
"output_type": "stream",
"stream": "stdout",
"text": [
"0\n"
]
},
{
"output_type": "stream",
"stream": "stdout",
"text": [
"Enter the input for 1 8\n"
]
},
{
"name": "stdout",
"output_type": "stream",
"stream": "stdout",
"text": [
"5\n"
]
},
{
"output_type": "stream",
"stream": "stdout",
"text": [
"Enter the input for 1 9\n"
]
},
{
"name": "stdout",
"output_type": "stream",
"stream": "stdout",
"text": [
"2\n"
]
},
{
"output_type": "stream",
"stream": "stdout",
"text": [
"Enter the input for 2 1\n"
]
},
{
"name": "stdout",
"output_type": "stream",
"stream": "stdout",
"text": [
"4\n"
]
},
{
"output_type": "stream",
"stream": "stdout",
"text": [
"Enter the input for 2 2\n"
]
},
{
"name": "stdout",
"output_type": "stream",
"stream": "stdout",
"text": [
"0\n"
]
},
{
"output_type": "stream",
"stream": "stdout",
"text": [
"Enter the input for 2 3\n"
]
},
{
"name": "stdout",
"output_type": "stream",
"stream": "stdout",
"text": [
"4\n"
]
},
{
"output_type": "stream",
"stream": "stdout",
"text": [
"Enter the input for 2 4\n"
]
},
{
"name": "stdout",
"output_type": "stream",
"stream": "stdout",
"text": [
"2\n"
]
},
{
"output_type": "stream",
"stream": "stdout",
"text": [
"Enter the input for 2 5\n"
]
},
{
"name": "stdout",
"output_type": "stream",
"stream": "stdout",
"text": [
"0\n"
]
},
{
"output_type": "stream",
"stream": "stdout",
"text": [
"Enter the input for 2 6\n"
]
},
{
"name": "stdout",
"output_type": "stream",
"stream": "stdout",
"text": [
"0\n"
]
},
{
"output_type": "stream",
"stream": "stdout",
"text": [
"Enter the input for 2 7\n"
]
},
{
"name": "stdout",
"output_type": "stream",
"stream": "stdout",
"text": [
"0\n"
]
},
{
"output_type": "stream",
"stream": "stdout",
"text": [
"Enter the input for 2 8\n"
]
},
{
"name": "stdout",
"output_type": "stream",
"stream": "stdout",
"text": [
"0\n"
]
},
{
"output_type": "stream",
"stream": "stdout",
"text": [
"Enter the input for 2 9\n"
]
},
{
"name": "stdout",
"output_type": "stream",
"stream": "stdout",
"text": [
"1\n"
]
},
{
"output_type": "stream",
"stream": "stdout",
"text": [
"Enter the input for 3 1\n"
]
},
{
"name": "stdout",
"output_type": "stream",
"stream": "stdout",
"text": [
"0\n"
]
},
{
"output_type": "stream",
"stream": "stdout",
"text": [
"Enter the input for 3 2\n"
]
},
{
"name": "stdout",
"output_type": "stream",
"stream": "stdout",
"text": [
"4\n"
]
},
{
"output_type": "stream",
"stream": "stdout",
"text": [
"Enter the input for 3 3\n"
]
},
{
"name": "stdout",
"output_type": "stream",
"stream": "stdout",
"text": [
"0\n"
]
},
{
"output_type": "stream",
"stream": "stdout",
"text": [
"Enter the input for 3 4\n"
]
},
{
"name": "stdout",
"output_type": "stream",
"stream": "stdout",
"text": [
"4\n"
]
},
{
"output_type": "stream",
"stream": "stdout",
"text": [
"Enter the input for 3 5\n"
]
},
{
"name": "stdout",
"output_type": "stream",
"stream": "stdout",
"text": [
"0\n"
]
},
{
"output_type": "stream",
"stream": "stdout",
"text": [
"Enter the input for 3 6\n"
]
},
{
"name": "stdout",
"output_type": "stream",
"stream": "stdout",
"text": [
"0\n"
]
},
{
"output_type": "stream",
"stream": "stdout",
"text": [
"Enter the input for 3 7\n"
]
},
{
"name": "stdout",
"output_type": "stream",
"stream": "stdout",
"text": [
"0\n"
]
},
{
"output_type": "stream",
"stream": "stdout",
"text": [
"Enter the input for 3 8\n"
]
},
{
"name": "stdout",
"output_type": "stream",
"stream": "stdout",
"text": [
"0\n"
]
},
{
"output_type": "stream",
"stream": "stdout",
"text": [
"Enter the input for 3 9\n"
]
},
{
"name": "stdout",
"output_type": "stream",
"stream": "stdout",
"text": [
"0\n"
]
},
{
"output_type": "stream",
"stream": "stdout",
"text": [
"Enter the input for 4 1\n"
]
},
{
"name": "stdout",
"output_type": "stream",
"stream": "stdout",
"text": [
"0\n"
]
},
{
"output_type": "stream",
"stream": "stdout",
"text": [
"Enter the input for 4 2\n"
]
},
{
"name": "stdout",
"output_type": "stream",
"stream": "stdout",
"text": [
"2\n"
]
},
{
"output_type": "stream",
"stream": "stdout",
"text": [
"Enter the input for 4 3\n"
]
},
{
"name": "stdout",
"output_type": "stream",
"stream": "stdout",
"text": [
"4\n"
]
},
{
"output_type": "stream",
"stream": "stdout",
"text": [
"Enter the input for 4 4\n"
]
},
{
"name": "stdout",
"output_type": "stream",
"stream": "stdout",
"text": [
"0\n"
]
},
{
"output_type": "stream",
"stream": "stdout",
"text": [
"Enter the input for 4 5\n"
]
},
{
"name": "stdout",
"output_type": "stream",
"stream": "stdout",
"text": [
"9\n"
]
},
{
"output_type": "stream",
"stream": "stdout",
"text": [
"Enter the input for 4 6\n"
]
},
{
"name": "stdout",
"output_type": "stream",
"stream": "stdout",
"text": [
"0\n"
]
},
{
"output_type": "stream",
"stream": "stdout",
"text": [
"Enter the input for 4 7\n"
]
},
{
"name": "stdout",
"output_type": "stream",
"stream": "stdout",
"text": [
"0\n"
]
},
{
"output_type": "stream",
"stream": "stdout",
"text": [
"Enter the input for 4 8\n"
]
},
{
"name": "stdout",
"output_type": "stream",
"stream": "stdout",
"text": [
"0\n"
]
},
{
"output_type": "stream",
"stream": "stdout",
"text": [
"Enter the input for 4 9\n"
]
},
{
"name": "stdout",
"output_type": "stream",
"stream": "stdout",
"text": [
"3\n"
]
},
{
"output_type": "stream",
"stream": "stdout",
"text": [
"Enter the input for 5 1\n"
]
},
{
"name": "stdout",
"output_type": "stream",
"stream": "stdout",
"text": [
"0\n"
]
},
{
"output_type": "stream",
"stream": "stdout",
"text": [
"Enter the input for 5 2\n"
]
},
{
"name": "stdout",
"output_type": "stream",
"stream": "stdout",
"text": [
"0\n"
]
},
{
"output_type": "stream",
"stream": "stdout",
"text": [
"Enter the input for 5 3\n"
]
},
{
"name": "stdout",
"output_type": "stream",
"stream": "stdout",
"text": [
"0\n"
]
},
{
"output_type": "stream",
"stream": "stdout",
"text": [
"Enter the input for 5 4\n"
]
},
{
"name": "stdout",
"output_type": "stream",
"stream": "stdout",
"text": [
"9\n"
]
},
{
"output_type": "stream",
"stream": "stdout",
"text": [
"Enter the input for 5 5\n"
]
},
{
"name": "stdout",
"output_type": "stream",
"stream": "stdout",
"text": [
"0\n"
]
},
{
"output_type": "stream",
"stream": "stdout",
"text": [
"Enter the input for 5 6\n"
]
},
{
"name": "stdout",
"output_type": "stream",
"stream": "stdout",
"text": [
"6\n"
]
},
{
"output_type": "stream",
"stream": "stdout",
"text": [
"Enter the input for 5 7\n"
]
},
{
"name": "stdout",
"output_type": "stream",
"stream": "stdout",
"text": [
"0\n"
]
},
{
"output_type": "stream",
"stream": "stdout",
"text": [
"Enter the input for 5 8\n"
]
},
{
"name": "stdout",
"output_type": "stream",
"stream": "stdout",
"text": [
"0\n"
]
},
{
"output_type": "stream",
"stream": "stdout",
"text": [
"Enter the input for 5 9\n"
]
},
{
"name": "stdout",
"output_type": "stream",
"stream": "stdout",
"text": [
"7\n"
]
},
{
"output_type": "stream",
"stream": "stdout",
"text": [
"Enter the input for 6 1\n"
]
},
{
"name": "stdout",
"output_type": "stream",
"stream": "stdout",
"text": [
"0\n"
]
},
{
"output_type": "stream",
"stream": "stdout",
"text": [
"Enter the input for 6 2\n"
]
},
{
"name": "stdout",
"output_type": "stream",
"stream": "stdout",
"text": [
"0\n"
]
},
{
"output_type": "stream",
"stream": "stdout",
"text": [
"Enter the input for 6 3\n"
]
},
{
"name": "stdout",
"output_type": "stream",
"stream": "stdout",
"text": [
"0\n"
]
},
{
"output_type": "stream",
"stream": "stdout",
"text": [
"Enter the input for 6 4\n"
]
},
{
"name": "stdout",
"output_type": "stream",
"stream": "stdout",
"text": [
"0\n"
]
},
{
"output_type": "stream",
"stream": "stdout",
"text": [
"Enter the input for 6 5\n"
]
},
{
"name": "stdout",
"output_type": "stream",
"stream": "stdout",
"text": [
"6\n"
]
},
{
"output_type": "stream",
"stream": "stdout",
"text": [
"Enter the input for 6 6\n"
]
},
{
"name": "stdout",
"output_type": "stream",
"stream": "stdout",
"text": [
"0\n"
]
},
{
"output_type": "stream",
"stream": "stdout",
"text": [
"Enter the input for 6 7\n"
]
},
{
"name": "stdout",
"output_type": "stream",
"stream": "stdout",
"text": [
"5\n"
]
},
{
"output_type": "stream",
"stream": "stdout",
"text": [
"Enter the input for 6 8\n"
]
},
{
"name": "stdout",
"output_type": "stream",
"stream": "stdout",
"text": [
"1\n"
]
},
{
"output_type": "stream",
"stream": "stdout",
"text": [
"Enter the input for 6 9\n"
]
},
{
"name": "stdout",
"output_type": "stream",
"stream": "stdout",
"text": [
"4\n"
]
},
{
"output_type": "stream",
"stream": "stdout",
"text": [
"Enter the input for 7 1\n"
]
},
{
"name": "stdout",
"output_type": "stream",
"stream": "stdout",
"text": [
"0\n"
]
},
{
"output_type": "stream",
"stream": "stdout",
"text": [
"Enter the input for 7 2\n"
]
},
{
"name": "stdout",
"output_type": "stream",
"stream": "stdout",
"text": [
"0\n"
]
},
{
"output_type": "stream",
"stream": "stdout",
"text": [
"Enter the input for 7 3\n"
]
},
{
"name": "stdout",
"output_type": "stream",
"stream": "stdout",
"text": [
"0\n"
]
},
{
"output_type": "stream",
"stream": "stdout",
"text": [
"Enter the input for 7 4\n"
]
},
{
"name": "stdout",
"output_type": "stream",
"stream": "stdout",
"text": [
"0\n"
]
},
{
"output_type": "stream",
"stream": "stdout",
"text": [
"Enter the input for 7 5\n"
]
},
{
"name": "stdout",
"output_type": "stream",
"stream": "stdout",
"text": [
"0\n"
]
},
{
"output_type": "stream",
"stream": "stdout",
"text": [
"Enter the input for 7 6\n"
]
},
{
"name": "stdout",
"output_type": "stream",
"stream": "stdout",
"text": [
"5\n"
]
},
{
"output_type": "stream",
"stream": "stdout",
"text": [
"Enter the input for 7 7\n"
]
},
{
"name": "stdout",
"output_type": "stream",
"stream": "stdout",
"text": [
"0\n"
]
},
{
"output_type": "stream",
"stream": "stdout",
"text": [
"Enter the input for 7 8\n"
]
},
{
"name": "stdout",
"output_type": "stream",
"stream": "stdout",
"text": [
"5\n"
]
},
{
"output_type": "stream",
"stream": "stdout",
"text": [
"Enter the input for 7 9\n"
]
},
{
"name": "stdout",
"output_type": "stream",
"stream": "stdout",
"text": [
"0\n"
]
},
{
"output_type": "stream",
"stream": "stdout",
"text": [
"Enter the input for 8 1\n"
]
},
{
"name": "stdout",
"output_type": "stream",
"stream": "stdout",
"text": [
"5\n"
]
},
{
"output_type": "stream",
"stream": "stdout",
"text": [
"Enter the input for 8 2\n"
]
},
{
"name": "stdout",
"output_type": "stream",
"stream": "stdout",
"text": [
"0\n"
]
},
{
"output_type": "stream",
"stream": "stdout",
"text": [
"Enter the input for 8 3\n"
]
},
{
"name": "stdout",
"output_type": "stream",
"stream": "stdout",
"text": [
"0\n"
]
},
{
"output_type": "stream",
"stream": "stdout",
"text": [
"Enter the input for 8 4\n"
]
},
{
"name": "stdout",
"output_type": "stream",
"stream": "stdout",
"text": [
"0\n"
]
},
{
"output_type": "stream",
"stream": "stdout",
"text": [
"Enter the input for 8 5\n"
]
},
{
"name": "stdout",
"output_type": "stream",
"stream": "stdout",
"text": [
"0\n"
]
},
{
"output_type": "stream",
"stream": "stdout",
"text": [
"Enter the input for 8 6\n"
]
},
{
"name": "stdout",
"output_type": "stream",
"stream": "stdout",
"text": [
"1\n"
]
},
{
"output_type": "stream",
"stream": "stdout",
"text": [
"Enter the input for 8 7\n"
]
},
{
"name": "stdout",
"output_type": "stream",
"stream": "stdout",
"text": [
"5\n"
]
},
{
"output_type": "stream",
"stream": "stdout",
"text": [
"Enter the input for 8 8\n"
]
},
{
"name": "stdout",
"output_type": "stream",
"stream": "stdout",
"text": [
"0\n"
]
},
{
"output_type": "stream",
"stream": "stdout",
"text": [
"Enter the input for 8 9\n"
]
},
{
"name": "stdout",
"output_type": "stream",
"stream": "stdout",
"text": [
"8\n"
]
},
{
"output_type": "stream",
"stream": "stdout",
"text": [
"Enter the input for 9 1\n"
]
},
{
"name": "stdout",
"output_type": "stream",
"stream": "stdout",
"text": [
"2\n"
]
},
{
"output_type": "stream",
"stream": "stdout",
"text": [
"Enter the input for 9 2\n"
]
},
{
"name": "stdout",
"output_type": "stream",
"stream": "stdout",
"text": [
"1\n"
]
},
{
"output_type": "stream",
"stream": "stdout",
"text": [
"Enter the input for 9 3\n"
]
},
{
"name": "stdout",
"output_type": "stream",
"stream": "stdout",
"text": [
"0\n"
]
},
{
"output_type": "stream",
"stream": "stdout",
"text": [
"Enter the input for 9 4\n"
]
},
{
"name": "stdout",
"output_type": "stream",
"stream": "stdout",
"text": [
"3\n"
]
},
{
"output_type": "stream",
"stream": "stdout",
"text": [
"Enter the input for 9 5\n"
]
},
{
"name": "stdout",
"output_type": "stream",
"stream": "stdout",
"text": [
"7\n"
]
},
{
"output_type": "stream",
"stream": "stdout",
"text": [
"Enter the input for 9 6\n"
]
},
{
"name": "stdout",
"output_type": "stream",
"stream": "stdout",
"text": [
"4\n"
]
},
{
"output_type": "stream",
"stream": "stdout",
"text": [
"Enter the input for 9 7\n"
]
},
{
"name": "stdout",
"output_type": "stream",
"stream": "stdout",
"text": [
"0\n"
]
},
{
"output_type": "stream",
"stream": "stdout",
"text": [
"Enter the input for 9 8\n"
]
},
{
"name": "stdout",
"output_type": "stream",
"stream": "stdout",
"text": [
"8\n"
]
},
{
"output_type": "stream",
"stream": "stdout",
"text": [
"Enter the input for 9 9\n"
]
},
{
"name": "stdout",
"output_type": "stream",
"stream": "stdout",
"text": [
"0\n"
]
},
{
"output_type": "stream",
"stream": "stdout",
"text": [
"\n",
"The edges of the minimum cost spanning tree is\n",
"\n",
"Edge 1 ( 2 , 9 )= 1\n",
"\n",
"Edge 2 ( 6 , 8 )= 1\n",
"\n",
"Edge 3 ( 1 , 9 )= 2\n",
"\n",
"Edge 4 ( 2 , 4 )= 2\n",
"\n",
"Edge 5 ( 2 , 3 )= 4\n",
"\n",
"Edge 6 ( 6 , 9 )= 4\n",
"\n",
"Edge 7 ( 6 , 7 )= 5\n",
"\n",
"Edge 8 ( 5 , 6 )= 6\n",
"\n",
"Minimum cost= 25\n"
]
}
],
"prompt_number": 3
},
{
"cell_type": "heading",
"level": 2,
"metadata": {},
"source": [
"Example 04:Page 280"
]
},
{
"cell_type": "code",
"collapsed": false,
"input": [
"print \"PRIM'S ALGORITHM\"\n",
"n=input(\"Enter the number of nodes\")\n",
"print \"Enter the adjacency matrix\"\n",
"cost=[[\"\" for i in range(n+1)]for j in range(n+1)]#Matrix declaration\n",
"visited=[0 for i in range(n+1)]#List declaration\n",
"n1=n+1#For use in range()\n",
"for i in range(1,n+1):\n",
" for j in range(1,n+1):\n",
" print \"Enter the input for\",i,j\n",
" cost[i][j]=input()#Get the adjacency matrix\n",
" if(cost[i][j]==0):\n",
" cost[i][j]=999#If there is no edge between two nodes, assign high cost\n",
"visited[1]=1#First node is initially visited\n",
"ne=1#Variable for node counting\n",
"mincost=0#Initially mincost is zero\n",
"\n",
"print \"\\n\"\n",
"while ne<n:\n",
" min=999\n",
" for i in range(1,n):\n",
" for j in range(1,n+1):#Generates all nodes\n",
" if(cost[i][j]<min):\n",
" if(visited[i]!=0):\n",
" min=cost[i][j]#Changes value if the new node has less cost\n",
" global a\n",
" a=i\n",
" u=i\n",
" global b\n",
" b=j\n",
" global v\n",
" v=j\n",
" if(visited[v]==0 or visited[u]==0):\n",
" \n",
" print \"\\nedge\",ne,\":(\",a,\" \",b,\")\",\"cost\",min\n",
" ne=ne+1\n",
" mincost=mincost+min\n",
" visited[b]=1\n",
" cost[a][b]=cost[b][a]=999\n",
"print \"minimum cost=\",mincost\n"
],
"language": "python",
"metadata": {},
"outputs": [
{
"output_type": "stream",
"stream": "stdout",
"text": [
"PRIM'S ALGORITHM\n"
]
},
{
"name": "stdout",
"output_type": "stream",
"stream": "stdout",
"text": [
"Enter the number of nodes7\n"
]
},
{
"output_type": "stream",
"stream": "stdout",
"text": [
"Enter the adjacency matrix\n",
"Enter the input for 1 1\n"
]
},
{
"name": "stdout",
"output_type": "stream",
"stream": "stdout",
"text": [
"0\n"
]
},
{
"output_type": "stream",
"stream": "stdout",
"text": [
"Enter the input for 1 2\n"
]
},
{
"name": "stdout",
"output_type": "stream",
"stream": "stdout",
"text": [
"2\n"
]
},
{
"output_type": "stream",
"stream": "stdout",
"text": [
"Enter the input for 1 3\n"
]
},
{
"name": "stdout",
"output_type": "stream",
"stream": "stdout",
"text": [
"0\n"
]
},
{
"output_type": "stream",
"stream": "stdout",
"text": [
"Enter the input for 1 4\n"
]
},
{
"name": "stdout",
"output_type": "stream",
"stream": "stdout",
"text": [
"0\n"
]
},
{
"output_type": "stream",
"stream": "stdout",
"text": [
"Enter the input for 1 5\n"
]
},
{
"name": "stdout",
"output_type": "stream",
"stream": "stdout",
"text": [
"0\n"
]
},
{
"output_type": "stream",
"stream": "stdout",
"text": [
"Enter the input for 1 6\n"
]
},
{
"name": "stdout",
"output_type": "stream",
"stream": "stdout",
"text": [
"1\n"
]
},
{
"output_type": "stream",
"stream": "stdout",
"text": [
"Enter the input for 1 7\n"
]
},
{
"name": "stdout",
"output_type": "stream",
"stream": "stdout",
"text": [
"6\n"
]
},
{
"output_type": "stream",
"stream": "stdout",
"text": [
"Enter the input for 2 1\n"
]
},
{
"name": "stdout",
"output_type": "stream",
"stream": "stdout",
"text": [
"2\n"
]
},
{
"output_type": "stream",
"stream": "stdout",
"text": [
"Enter the input for 2 2\n"
]
},
{
"name": "stdout",
"output_type": "stream",
"stream": "stdout",
"text": [
"0\n"
]
},
{
"output_type": "stream",
"stream": "stdout",
"text": [
"Enter the input for 2 3\n"
]
},
{
"name": "stdout",
"output_type": "stream",
"stream": "stdout",
"text": [
"5\n"
]
},
{
"output_type": "stream",
"stream": "stdout",
"text": [
"Enter the input for 2 4\n"
]
},
{
"name": "stdout",
"output_type": "stream",
"stream": "stdout",
"text": [
"0\n"
]
},
{
"output_type": "stream",
"stream": "stdout",
"text": [
"Enter the input for 2 5\n"
]
},
{
"name": "stdout",
"output_type": "stream",
"stream": "stdout",
"text": [
"0\n"
]
},
{
"output_type": "stream",
"stream": "stdout",
"text": [
"Enter the input for 2 6\n"
]
},
{
"name": "stdout",
"output_type": "stream",
"stream": "stdout",
"text": [
"0\n"
]
},
{
"output_type": "stream",
"stream": "stdout",
"text": [
"Enter the input for 2 7\n"
]
},
{
"name": "stdout",
"output_type": "stream",
"stream": "stdout",
"text": [
"1\n"
]
},
{
"output_type": "stream",
"stream": "stdout",
"text": [
"Enter the input for 3 1\n"
]
},
{
"name": "stdout",
"output_type": "stream",
"stream": "stdout",
"text": [
"0\n"
]
},
{
"output_type": "stream",
"stream": "stdout",
"text": [
"Enter the input for 3 2\n"
]
},
{
"name": "stdout",
"output_type": "stream",
"stream": "stdout",
"text": [
"5\n"
]
},
{
"output_type": "stream",
"stream": "stdout",
"text": [
"Enter the input for 3 3\n"
]
},
{
"name": "stdout",
"output_type": "stream",
"stream": "stdout",
"text": [
"0\n"
]
},
{
"output_type": "stream",
"stream": "stdout",
"text": [
"Enter the input for 3 4\n"
]
},
{
"name": "stdout",
"output_type": "stream",
"stream": "stdout",
"text": [
"6\n"
]
},
{
"output_type": "stream",
"stream": "stdout",
"text": [
"Enter the input for 3 5\n"
]
},
{
"name": "stdout",
"output_type": "stream",
"stream": "stdout",
"text": [
"0\n"
]
},
{
"output_type": "stream",
"stream": "stdout",
"text": [
"Enter the input for 3 6\n"
]
},
{
"name": "stdout",
"output_type": "stream",
"stream": "stdout",
"text": [
"0\n"
]
},
{
"output_type": "stream",
"stream": "stdout",
"text": [
"Enter the input for 3 7\n"
]
},
{
"name": "stdout",
"output_type": "stream",
"stream": "stdout",
"text": [
"3\n"
]
},
{
"output_type": "stream",
"stream": "stdout",
"text": [
"Enter the input for 4 1\n"
]
},
{
"name": "stdout",
"output_type": "stream",
"stream": "stdout",
"text": [
"0\n"
]
},
{
"output_type": "stream",
"stream": "stdout",
"text": [
"Enter the input for 4 2\n"
]
},
{
"name": "stdout",
"output_type": "stream",
"stream": "stdout",
"text": [
"0\n"
]
},
{
"output_type": "stream",
"stream": "stdout",
"text": [
"Enter the input for 4 3\n"
]
},
{
"name": "stdout",
"output_type": "stream",
"stream": "stdout",
"text": [
"6\n"
]
},
{
"output_type": "stream",
"stream": "stdout",
"text": [
"Enter the input for 4 4\n"
]
},
{
"name": "stdout",
"output_type": "stream",
"stream": "stdout",
"text": [
"0\n"
]
},
{
"output_type": "stream",
"stream": "stdout",
"text": [
"Enter the input for 4 5\n"
]
},
{
"name": "stdout",
"output_type": "stream",
"stream": "stdout",
"text": [
"3\n"
]
},
{
"output_type": "stream",
"stream": "stdout",
"text": [
"Enter the input for 4 6\n"
]
},
{
"name": "stdout",
"output_type": "stream",
"stream": "stdout",
"text": [
"0\n"
]
},
{
"output_type": "stream",
"stream": "stdout",
"text": [
"Enter the input for 4 7\n"
]
},
{
"name": "stdout",
"output_type": "stream",
"stream": "stdout",
"text": [
"3\n"
]
},
{
"output_type": "stream",
"stream": "stdout",
"text": [
"Enter the input for 5 1\n"
]
},
{
"name": "stdout",
"output_type": "stream",
"stream": "stdout",
"text": [
"0\n"
]
},
{
"output_type": "stream",
"stream": "stdout",
"text": [
"Enter the input for 5 2\n"
]
},
{
"name": "stdout",
"output_type": "stream",
"stream": "stdout",
"text": [
"0\n"
]
},
{
"output_type": "stream",
"stream": "stdout",
"text": [
"Enter the input for 5 3\n"
]
},
{
"name": "stdout",
"output_type": "stream",
"stream": "stdout",
"text": [
"0\n"
]
},
{
"output_type": "stream",
"stream": "stdout",
"text": [
"Enter the input for 5 4\n"
]
},
{
"name": "stdout",
"output_type": "stream",
"stream": "stdout",
"text": [
"3\n"
]
},
{
"output_type": "stream",
"stream": "stdout",
"text": [
"Enter the input for 5 5\n"
]
},
{
"name": "stdout",
"output_type": "stream",
"stream": "stdout",
"text": [
"0\n"
]
},
{
"output_type": "stream",
"stream": "stdout",
"text": [
"Enter the input for 5 6\n"
]
},
{
"name": "stdout",
"output_type": "stream",
"stream": "stdout",
"text": [
"2\n"
]
},
{
"output_type": "stream",
"stream": "stdout",
"text": [
"Enter the input for 5 7\n"
]
},
{
"name": "stdout",
"output_type": "stream",
"stream": "stdout",
"text": [
"7\n"
]
},
{
"output_type": "stream",
"stream": "stdout",
"text": [
"Enter the input for 6 1\n"
]
},
{
"name": "stdout",
"output_type": "stream",
"stream": "stdout",
"text": [
"1\n"
]
},
{
"output_type": "stream",
"stream": "stdout",
"text": [
"Enter the input for 6 2\n"
]
},
{
"name": "stdout",
"output_type": "stream",
"stream": "stdout",
"text": [
"0\n"
]
},
{
"output_type": "stream",
"stream": "stdout",
"text": [
"Enter the input for 6 3\n"
]
},
{
"name": "stdout",
"output_type": "stream",
"stream": "stdout",
"text": [
"0\n"
]
},
{
"output_type": "stream",
"stream": "stdout",
"text": [
"Enter the input for 6 4\n"
]
},
{
"name": "stdout",
"output_type": "stream",
"stream": "stdout",
"text": [
"0\n"
]
},
{
"output_type": "stream",
"stream": "stdout",
"text": [
"Enter the input for 6 5\n"
]
},
{
"name": "stdout",
"output_type": "stream",
"stream": "stdout",
"text": [
"2\n"
]
},
{
"output_type": "stream",
"stream": "stdout",
"text": [
"Enter the input for 6 6\n"
]
},
{
"name": "stdout",
"output_type": "stream",
"stream": "stdout",
"text": [
"0\n"
]
},
{
"output_type": "stream",
"stream": "stdout",
"text": [
"Enter the input for 6 7\n"
]
},
{
"name": "stdout",
"output_type": "stream",
"stream": "stdout",
"text": [
"4\n"
]
},
{
"output_type": "stream",
"stream": "stdout",
"text": [
"Enter the input for 7 1\n"
]
},
{
"name": "stdout",
"output_type": "stream",
"stream": "stdout",
"text": [
"6\n"
]
},
{
"output_type": "stream",
"stream": "stdout",
"text": [
"Enter the input for 7 2\n"
]
},
{
"name": "stdout",
"output_type": "stream",
"stream": "stdout",
"text": [
"1\n"
]
},
{
"output_type": "stream",
"stream": "stdout",
"text": [
"Enter the input for 7 3\n"
]
},
{
"name": "stdout",
"output_type": "stream",
"stream": "stdout",
"text": [
"3\n"
]
},
{
"output_type": "stream",
"stream": "stdout",
"text": [
"Enter the input for 7 4\n"
]
},
{
"name": "stdout",
"output_type": "stream",
"stream": "stdout",
"text": [
"3\n"
]
},
{
"output_type": "stream",
"stream": "stdout",
"text": [
"Enter the input for 7 5\n"
]
},
{
"name": "stdout",
"output_type": "stream",
"stream": "stdout",
"text": [
"7\n"
]
},
{
"output_type": "stream",
"stream": "stdout",
"text": [
"Enter the input for 7 6\n"
]
},
{
"name": "stdout",
"output_type": "stream",
"stream": "stdout",
"text": [
"4\n"
]
},
{
"output_type": "stream",
"stream": "stdout",
"text": [
"Enter the input for 7 7\n"
]
},
{
"name": "stdout",
"output_type": "stream",
"stream": "stdout",
"text": [
"0\n"
]
},
{
"output_type": "stream",
"stream": "stdout",
"text": [
"\n",
"\n",
"\n",
"edge 1 :( 1 6 ) cost 1\n",
"\n",
"edge 2 :( 1 2 ) cost 2\n",
"\n",
"edge 3 :( 2 7 ) cost 1\n",
"\n",
"edge 4 :( 6 5 ) cost 2\n",
"\n",
"edge 5 :( 5 4 ) cost 3\n",
"\n",
"edge 6 :( 2 3 ) cost 5\n",
"minimum cost= 14\n"
]
}
],
"prompt_number": 4
}
],
"metadata": {}
}
]
}