{"id":643,"date":"2023-08-27T16:30:59","date_gmt":"2023-08-27T11:00:59","guid":{"rendered":"https:\/\/moodle.sit.ac.in\/blog\/?p=643"},"modified":"2023-10-18T18:58:05","modified_gmt":"2023-10-18T13:28:05","slug":"design-analysis-of-algorithms-lab-manual-21cs42","status":"publish","type":"post","link":"https:\/\/moodle.sit.ac.in\/blog\/design-analysis-of-algorithms-lab-manual-21cs42\/","title":{"rendered":"Design & Analysis of\u00a0Algorithms Lab Manual – 21CS42"},"content":{"rendered":"\n

Demystifying Algorithms & Solving Problems<\/h4>\n\n\n

\"\"<\/a><\/p>\n

In this blog post, you will find solutions for the lab component Design & Analysis of\u00a0Algorithms (21CS42)<\/strong> course work for the IV semester of VTU<\/strong> university. The solutions to the lab component are coded in C++<\/strong>. We recommend using the Code:Blocks<\/strong><\/a> as the integrated development environment (IDE). You can find the lab syllabus on the university’s website or click here<\/strong><\/a>. Along with C++ programs for each question I have provided an equivalent Java<\/strong> Program as well.<\/p>\n

After getting the necessary development environment setup, Now lets focus on the solutions. Click on the appropriate hyperlink to go to your program of choice.<\/p>\n

    \n
  1. Module 1<\/span><\/a>\n
      \n
    1. Selection Sort<\/span><\/a><\/li>\n<\/ol>\n<\/li>\n
    2. Module 2<\/span><\/a>\n
        \n
      1. Quick Sort<\/span><\/a><\/li>\n
      2. Merge Sort<\/span><\/a><\/li>\n<\/ol>\n<\/li>\n
      3. Module 3<\/span><\/a>\n
          \n
        1. Knapsack problem using Greedy method.<\/span><\/a><\/li>\n
        2. Dijkstra’s Algorithm<\/span><\/a><\/li>\n
        3. Kruskal’s Algorithm<\/span><\/a><\/li>\n
        4. Prim’s Algorithm<\/span><\/a><\/li>\n<\/ol>\n<\/li>\n
        5. Module 4<\/span><\/a>\n
            \n
          1. Floyd’s Algorithm<\/span><\/a><\/li>\n
          2. Travelling Sales Person Problem<\/span><\/a><\/li>\n
          3. 0\/1 Knapsack problem<\/span><\/a><\/li>\n<\/ol>\n<\/li>\n
          4. Module 5<\/span><\/a>\n
              \n
            1. Subset Sum Problem<\/span><\/a><\/li>\n
            2. Hamiltonian Cycles<\/span><\/a><\/li>\n<\/ol>\n<\/li>\n<\/ol>\n\n\n
              \n\n\n\n
              \"\"<\/figure>\n\n\n\n

              Module 1 <\/h2>\n\n\n\n

              Selection Sort<\/h3>\n\n\n\n

              Sort a given set of n integer elements using Selection Sort method and compute its time complexity. Run the program for varied values of n> 5000 and record the time taken to sort. Plot a graph of the time taken versus n. The elements can be read from a file or can be generated using the random number generator. Demonstrate using C++\/Java how the brute force method works along with its time complexity analysis: worst case, average case and best case.<\/p>\n\n\n\n

              C++ Code<\/h4>\n\n\n\n
              <\/circle><\/circle><\/circle><\/g><\/svg><\/span><\/path><\/path><\/svg><\/span>
              \/******************************************************************************<\/span><\/span>\n*File\t\t: 01SelectionSort.cpp<\/span><\/span>\n*Description\t: Program to sort an array using Merge Sort<\/span><\/span>\n*Author: Prabodh C P<\/span><\/span>\n*Compiler: gcc compiler 7.5.0, Ubuntu 18.04<\/span><\/span>\n*Date: Friday 4 February 2020<\/span><\/span>\n******************************************************************************\/<\/span><\/span>\n#include<\/span> <\/span><iostream><\/span><\/span>\n#include<\/span> <\/span><fstream><\/span><\/span>\n#include<\/span> <\/span><iomanip><\/span><\/span>\n#include<\/span> <\/span><vector><\/span><\/span>\n#include<\/span> <\/span><ctime><\/span><\/span>\n#include<\/span> <\/span><cstdlib><\/span><\/span>\nusing<\/span> <\/span>namespace<\/span> <\/span>std<\/span>;<\/span><\/span>\n<\/span>\nclass<\/span> <\/span>SelectionSort<\/span>{<\/span><\/span>\n    vector <\/span><int><\/span> numList;<\/span><\/span>\n    <\/span>int<\/span> iNum;<\/span><\/span>\n    <\/span>public:<\/span><\/span>\n<\/span>\n    <\/span>void<\/span> <\/span>fnGenRandArray<\/span>(<\/span>int<\/span>);<\/span><\/span>\n    <\/span>void<\/span> <\/span>fnSortArray<\/span>(<\/span>int<\/span>);<\/span><\/span>\n    <\/span>void<\/span> <\/span>fnDispArray<\/span>(<\/span>int<\/span>);<\/span><\/span>\n    <\/span>void<\/span> <\/span>fnSwap<\/span>(<\/span>int<\/span> <\/span>&<\/span>,<\/span>int<\/span> <\/span>&<\/span>);<\/span><\/span>\n};<\/span><\/span>\n<\/span>\nint<\/span> <\/span>main<\/span>( <\/span>int<\/span> <\/span>argc<\/span>, <\/span>char<\/span> <\/span>**<\/span>argv<\/span>)<\/span><\/span>\n{<\/span><\/span>\n<\/span>\n    <\/span>struct<\/span> <\/span>timespec<\/span> tv;<\/span><\/span>\n    <\/span>int<\/span> iChoice, i, iNum;<\/span><\/span>\n    <\/span>double<\/span> dStart, dEnd;<\/span><\/span>\n    SelectionSort myListObj;<\/span><\/span>\n\tofstream <\/span>fout<\/span>(<\/span>"SelectPlot.dat"<\/span>, <\/span>ios<\/span>::out);<\/span><\/span>\n    <\/span>for<\/span>(;;)<\/span><\/span>\n    {<\/span><\/span>\n        cout <\/span><<<\/span> <\/span>"<\/span>\\n<\/span>1.Plot the Graph<\/span>\\n<\/span>2.SelectionSort<\/span>\\n<\/span>3.Exit"<\/span> ;<\/span><\/span>\n        cout <\/span><<<\/span> <\/span>"<\/span>\\n<\/span>Enter your choice<\/span>\\n<\/span>"<\/span>;<\/span><\/span>\n        cin <\/span>>><\/span> iChoice;<\/span><\/span>\n        <\/span>switch<\/span>(iChoice)<\/span><\/span>\n        {<\/span><\/span>\n            <\/span>case<\/span> <\/span>1<\/span>: <\/span>for<\/span>(i<\/span>=<\/span>100<\/span>;i<\/span><<\/span>10000<\/span>;i<\/span>+=<\/span>100<\/span>)<\/span><\/span>\n                    {<\/span><\/span>\n                        myListObj.<\/span>fnGenRandArray<\/span>(i);<\/span><\/span>\n                        <\/span>clock_gettime<\/span>(CLOCK_REALTIME, <\/span>&<\/span>tv);<\/span><\/span>\n                        dStart <\/span>=<\/span> tv.tv_sec <\/span>+<\/span> tv.tv_nsec<\/span>\/<\/span>1000000000.0<\/span>;<\/span><\/span>\n                        myListObj.<\/span>fnSortArray<\/span>(i);<\/span><\/span>\n                        <\/span>clock_gettime<\/span>(CLOCK_REALTIME, <\/span>&<\/span>tv);<\/span><\/span>\n                        dEnd <\/span>=<\/span> tv.tv_sec <\/span>+<\/span> tv.tv_nsec<\/span>\/<\/span>1000000000.0<\/span>;<\/span><\/span>\n<\/span>\n                        fout <\/span><<<\/span> i <\/span><<<\/span> <\/span>"<\/span>\\t<\/span>"<\/span> <\/span><<<\/span> <\/span>setprecision<\/span>(<\/span>10<\/span>) <\/span><<<\/span> dEnd <\/span>-<\/span> dStart <\/span><<<\/span> endl;<\/span><\/span>\n                    }<\/span><\/span>\n                    cout <\/span><<<\/span> <\/span>"<\/span>\\n<\/span>Data File generated and stored in file < SelectPlot.dat >.<\/span>\\n<\/span> Use a plotting utility<\/span>\\n<\/span>"<\/span>;<\/span><\/span>\n                    <\/span>break<\/span>;<\/span><\/span>\n            <\/span>case<\/span> <\/span>2<\/span>:<\/span><\/span>\n                    cout <\/span><<<\/span> <\/span>"<\/span>\\n<\/span>Enter number of elements to sort : "<\/span>; cin <\/span>>><\/span> iNum;<\/span><\/span>\n                    myListObj.<\/span>fnGenRandArray<\/span>(iNum);<\/span><\/span>\n                    cout <\/span><<<\/span> <\/span>"<\/span>\\n<\/span>Unsorted Array"<\/span> <\/span><<<\/span> endl;<\/span><\/span>\n                    myListObj.<\/span>fnDispArray<\/span>(iNum);<\/span><\/span>\n                    myListObj.<\/span>fnSortArray<\/span>(iNum);<\/span><\/span>\n                    cout <\/span><<<\/span> <\/span>"<\/span>\\n<\/span>Sorted Array"<\/span> <\/span><<<\/span> endl;<\/span><\/span>\n                    myListObj.<\/span>fnDispArray<\/span>(iNum);<\/span><\/span>\n                    <\/span>break<\/span>;<\/span><\/span>\n            <\/span>case<\/span> <\/span>3<\/span>:<\/span><\/span>\n                    <\/span>exit<\/span>(<\/span>0<\/span>);<\/span><\/span>\n        }<\/span><\/span>\n    }<\/span><\/span>\n    fout.<\/span>close<\/span>();<\/span><\/span>\n    <\/span>return<\/span> <\/span>0<\/span>;<\/span><\/span>\n}<\/span><\/span>\n<\/span>\nvoid<\/span> <\/span>SelectionSort<\/span>::<\/span>fnGenRandArray<\/span>(<\/span>int<\/span> <\/span>n<\/span>)<\/span><\/span>\n{<\/span><\/span>\n    <\/span>int<\/span> i, iVal;<\/span><\/span>\n<\/span>\n\t<\/span>srand<\/span>(<\/span>time<\/span>(<\/span>NULL<\/span>));<\/span><\/span>\n\t<\/span>for<\/span>(i<\/span>=<\/span>0<\/span>;i<\/span><<\/span>n;i<\/span>++<\/span>)<\/span><\/span>\n\t{<\/span><\/span>\n        iVal <\/span>=<\/span> <\/span>rand<\/span>()<\/span>%<\/span>10000<\/span>;<\/span><\/span>\n        numList.<\/span>push_back<\/span>(iVal);<\/span><\/span>\n\t}<\/span><\/span>\n}<\/span><\/span>\n<\/span>\nvoid<\/span> <\/span>SelectionSort<\/span>::<\/span>fnDispArray<\/span>(<\/span>int<\/span> <\/span>n<\/span>)<\/span><\/span>\n{<\/span><\/span>\n    <\/span>int<\/span> i;<\/span><\/span>\n\t<\/span>for<\/span>(i<\/span>=<\/span>0<\/span>;i<\/span><<\/span>n;i<\/span>++<\/span>)<\/span><\/span>\n\t{<\/span><\/span>\n        cout <\/span><<<\/span> <\/span>setw<\/span>(<\/span>8<\/span>) <\/span><<<\/span> numList[i] <\/span><<<\/span> endl;<\/span><\/span>\n    }<\/span><\/span>\n}<\/span><\/span>\n<\/span>\n<\/span>\nvoid<\/span> <\/span>SelectionSort<\/span>::<\/span>fnSortArray<\/span>(<\/span>int<\/span> <\/span>n<\/span>)<\/span><\/span>\n{<\/span><\/span>\n\t<\/span>int<\/span> i, j, min_idx;<\/span><\/span>\n\t<\/span>for<\/span>(i<\/span>=<\/span>0<\/span>;i<\/span><<\/span>n<\/span>-<\/span>1<\/span>;i<\/span>++<\/span>)<\/span><\/span>\n\t{<\/span><\/span>\n\t\tmin_idx <\/span>=<\/span> i;<\/span><\/span>\n\t\t<\/span>for<\/span>(j<\/span>=<\/span>i<\/span>+<\/span>1<\/span>;j<\/span><<\/span>n;j<\/span>++<\/span>)<\/span><\/span>\n\t\t{<\/span><\/span>\n\t\t\t<\/span>if<\/span>(numList[j] <\/span><<\/span> numList[min_idx])<\/span><\/span>\n\t\t\t\tmin_idx <\/span>=<\/span> j;<\/span><\/span>\n\t\t}<\/span><\/span>\n\t\t<\/span>fnSwap<\/span>(numList[i], numList[min_idx]);<\/span><\/span>\n\t}<\/span><\/span>\n}<\/span><\/span>\n<\/span>\nvoid<\/span> <\/span>SelectionSort<\/span>::<\/span>fnSwap<\/span>(<\/span>int<\/span> <\/span>&<\/span>a<\/span>,<\/span>int<\/span> <\/span>&<\/span>b<\/span>)<\/span><\/span>\n{<\/span><\/span>\n\t<\/span>int<\/span> t;<\/span><\/span>\n\tt <\/span>=<\/span> a;\ta <\/span>=<\/span> b;\tb <\/span>=<\/span> t;<\/span><\/span>\n}<\/span><\/span>\n<\/span><\/code><\/pre><\/div>\n\n\n\n
              Java Code<\/h4>\n\n\n\n
              <\/circle><\/circle><\/circle><\/g><\/svg><\/span><\/path><\/path><\/svg><\/span>
              import<\/span> java.util.ArrayList;<\/span><\/span>\nimport<\/span> java.util.List;<\/span><\/span>\nimport<\/span> java.io.FileWriter;<\/span><\/span>\nimport<\/span> java.io.IOException;<\/span><\/span>\nimport<\/span> java.io.PrintWriter;<\/span><\/span>\n<\/span>\npublic<\/span> <\/span>class<\/span> <\/span>SelectionSort<\/span> {<\/span><\/span>\n    <\/span>private<\/span> List<<\/span>Integer<\/span>> numList;<\/span><\/span>\n<\/span>\n    <\/span>public<\/span> <\/span>SelectionSort<\/span>() {<\/span><\/span>\n        numList <\/span>=<\/span> <\/span>new<\/span> ArrayList<>();<\/span><\/span>\n    }<\/span><\/span>\n<\/span>\n    <\/span>public<\/span> <\/span>void<\/span> <\/span>fnGenRandArray<\/span>(<\/span>int<\/span> <\/span>n<\/span>) {<\/span><\/span>\n        <\/span>int<\/span> i, iVal;<\/span><\/span>\n        <\/span>for<\/span> (i <\/span>=<\/span> <\/span>0<\/span>; i <\/span><<\/span> n; i<\/span>++<\/span>) {<\/span><\/span>\n            iVal <\/span>=<\/span> (<\/span>int<\/span>) (Math.<\/span>random<\/span>() <\/span>*<\/span> <\/span>10000<\/span>);<\/span><\/span>\n            numList.<\/span>add<\/span>(iVal);<\/span><\/span>\n        }<\/span><\/span>\n    }<\/span><\/span>\n<\/span>\n    <\/span>public<\/span> <\/span>void<\/span> <\/span>fnDispArray<\/span>(<\/span>int<\/span> <\/span>n<\/span>) {<\/span><\/span>\n        <\/span>for<\/span> (<\/span>int<\/span> i <\/span>=<\/span> <\/span>0<\/span>; i <\/span><<\/span> n; i<\/span>++<\/span>) {<\/span><\/span>\n            System.out.<\/span>println<\/span>(String.<\/span>format<\/span>(<\/span>"%8d"<\/span>, numList.<\/span>get<\/span>(i)));<\/span><\/span>\n        }<\/span><\/span>\n    }<\/span><\/span>\n<\/span>\n    <\/span>public<\/span> <\/span>void<\/span> <\/span>fnSortArray<\/span>(<\/span>int<\/span> <\/span>n<\/span>) {<\/span><\/span>\n        <\/span>int<\/span> i, j, min_idx;<\/span><\/span>\n        <\/span>for<\/span> (i <\/span>=<\/span> <\/span>0<\/span>; i <\/span><<\/span> n <\/span>-<\/span> <\/span>1<\/span>; i<\/span>++<\/span>) {<\/span><\/span>\n            min_idx <\/span>=<\/span> i;<\/span><\/span>\n            <\/span>for<\/span> (j <\/span>=<\/span> i <\/span>+<\/span> <\/span>1<\/span>; j <\/span><<\/span> n; j<\/span>++<\/span>) {<\/span><\/span>\n                <\/span>if<\/span> (numList.<\/span>get<\/span>(j) <\/span><<\/span> numList.<\/span>get<\/span>(min_idx))<\/span><\/span>\n                    min_idx <\/span>=<\/span> j;<\/span><\/span>\n            }<\/span><\/span>\n            <\/span>fnSwap<\/span>(i, min_idx);<\/span><\/span>\n        }<\/span><\/span>\n    }<\/span><\/span>\n<\/span>\n    <\/span>public<\/span> <\/span>void<\/span> <\/span>fnSwap<\/span>(<\/span>int<\/span> <\/span>a<\/span>, <\/span>int<\/span> <\/span>b<\/span>) {<\/span><\/span>\n        <\/span>int<\/span> temp <\/span>=<\/span> numList.<\/span>get<\/span>(a);<\/span><\/span>\n        numList.<\/span>set<\/span>(a, numList.<\/span>get<\/span>(b));<\/span><\/span>\n        numList.<\/span>set<\/span>(b, temp);<\/span><\/span>\n    }<\/span><\/span>\n<\/span>\n    <\/span>public<\/span> <\/span>static<\/span> <\/span>void<\/span> <\/span>main<\/span>(<\/span>String<\/span>[] <\/span>args<\/span>) {<\/span><\/span>\n        <\/span>long<\/span> startTime, endTime;<\/span><\/span>\n        <\/span>int<\/span> iChoice, iNum;<\/span><\/span>\n        SelectionSort myListObj <\/span>=<\/span> <\/span>new<\/span> <\/span>SelectionSort<\/span>();<\/span><\/span>\n<\/span>\n        <\/span>try<\/span> (PrintWriter fout <\/span>=<\/span> <\/span>new<\/span> <\/span>PrintWriter<\/span>(<\/span>new<\/span> <\/span>FileWriter<\/span>(<\/span>"SelectPlot.dat"<\/span>))) {<\/span><\/span>\n            <\/span>for<\/span> (;;) {<\/span><\/span>\n                System.out.<\/span>println<\/span>(<\/span>"<\/span>\\n<\/span>1.SelectionSort<\/span>\\n<\/span>2.Plot the Graph<\/span>\\n<\/span>3.Exit"<\/span>);<\/span><\/span>\n                System.out.<\/span>println<\/span>(<\/span>"Enter your choice"<\/span>);<\/span><\/span>\n                iChoice <\/span>=<\/span> Integer.<\/span>parseInt<\/span>(System.<\/span>console<\/span>().<\/span>readLine<\/span>());<\/span><\/span>\n<\/span>\n                <\/span>switch<\/span> (iChoice) {<\/span><\/span>\n                    <\/span>case<\/span> <\/span>1<\/span>:<\/span><\/span>\n                        System.out.<\/span>print<\/span>(<\/span>"Enter number of elements to sort : "<\/span>);<\/span><\/span>\n                        iNum <\/span>=<\/span> Integer.<\/span>parseInt<\/span>(System.<\/span>console<\/span>().<\/span>readLine<\/span>());<\/span><\/span>\n                        myListObj.<\/span>fnGenRandArray<\/span>(iNum);<\/span><\/span>\n<\/span>\n                        System.out.<\/span>println<\/span>(<\/span>"<\/span>\\n<\/span>Unsorted Array"<\/span>);<\/span><\/span>\n                        myListObj.<\/span>fnDispArray<\/span>(iNum);<\/span><\/span>\n<\/span>\n                        myListObj.<\/span>fnSortArray<\/span>(iNum);<\/span><\/span>\n<\/span>\n                        System.out.<\/span>println<\/span>(<\/span>"<\/span>\\n<\/span>Sorted Array"<\/span>);<\/span><\/span>\n                        myListObj.<\/span>fnDispArray<\/span>(iNum);<\/span><\/span>\n                        <\/span>break<\/span>;<\/span><\/span>\n                    <\/span>case<\/span> <\/span>2<\/span>:<\/span><\/span>\n                        <\/span>for<\/span> (<\/span>int<\/span> i <\/span>=<\/span> <\/span>100<\/span>; i <\/span><<\/span> <\/span>10000<\/span>; i <\/span>+=<\/span> <\/span>100<\/span>) {<\/span><\/span>\n                            myListObj.<\/span>fnGenRandArray<\/span>(i);<\/span><\/span>\n<\/span>\n                            startTime <\/span>=<\/span> System.<\/span>nanoTime<\/span>();<\/span><\/span>\n                            myListObj.<\/span>fnSortArray<\/span>(i);<\/span><\/span>\n                            endTime <\/span>=<\/span> System.<\/span>nanoTime<\/span>();<\/span><\/span>\n\/\/\t\t\t\t\t\t\tSystem.out.println(i + "\\t" + (endTime - startTime));<\/span><\/span>\n                            fout.<\/span>println<\/span>(i <\/span>+<\/span> <\/span>"<\/span>\\t<\/span>"<\/span> <\/span>+<\/span> ((endTime <\/span>-<\/span> startTime) <\/span>\/<\/span> <\/span>1e9<\/span>));<\/span><\/span>\n                        }<\/span><\/span>\n<\/span>\n                        System.out.<\/span>println<\/span>(<\/span>"<\/span>\\n<\/span>Data File generated and stored in file < SelectPlot.dat >. Use a plotting utility"<\/span>);<\/span><\/span>\n                        <\/span>break<\/span>;<\/span><\/span>\n                    <\/span>case<\/span> <\/span>3<\/span>:<\/span><\/span>\n                        System.<\/span>exit<\/span>(<\/span>0<\/span>);<\/span><\/span>\n                }<\/span><\/span>\n            }<\/span><\/span>\n        } <\/span>catch<\/span> (IOException <\/span>e<\/span>) {<\/span><\/span>\n            System.out.<\/span>println<\/span>(<\/span>"Error: "<\/span> <\/span>+<\/span> e.<\/span>getMessage<\/span>());<\/span><\/span>\n        }<\/span><\/span>\n    }<\/span><\/span>\n}<\/span><\/span>\n<\/span><\/code><\/pre><\/div>\n\n\n\n
              Output<\/h4>\n\n\n\n
              <\/circle><\/circle><\/circle><\/g><\/svg><\/span><\/path><\/path><\/svg><\/span>
              1.SelectionSort<\/span><\/span>\n2.Plot the Graph<\/span><\/span>\n3.Exit<\/span><\/span>\nEnter your choice<\/span><\/span>\n1<\/span><\/span>\n<\/span>\nEnter number <\/span>of<\/span> elements to <\/span>sort<\/span> : <\/span>4<\/span><\/span>\n<\/span>\nUnsorted Array<\/span><\/span>\n    <\/span>2465<\/span><\/span>\n    <\/span>1009<\/span><\/span>\n    <\/span>9680<\/span><\/span>\n    <\/span>8206<\/span><\/span>\n<\/span>\nSorted Array<\/span><\/span>\n    <\/span>1009<\/span><\/span>\n    <\/span>2465<\/span><\/span>\n    <\/span>8206<\/span><\/span>\n    <\/span>9680<\/span><\/span>\n<\/span>\n1.SelectionSort<\/span><\/span>\n2.Plot the Graph<\/span><\/span>\n3.Exit<\/span><\/span>\nEnter your choice<\/span><\/span>\n2<\/span><\/span>\n<\/span>\nData File generated and stored <\/span>in<\/span> file <\/span><<\/span> SelectPlot.dat <\/span>><\/span>.<\/span><\/span>\n Use a plotting utility<\/span><\/span>\n<\/span>\n1.SelectionSort<\/span><\/span>\n2.Plot the Graph<\/span><\/span>\n3.Exit<\/span><\/span>\nEnter your choice<\/span><\/span>\n3<\/span><\/span>\n<\/span><\/code><\/pre><\/div>\n\n\n\n
              Plotting using Gnuplot Utility<\/h3>\n\n\n\n
              Gnuplot<\/a><\/strong> is one of the popular tools used for plotting. You can install using the following command on Ubuntu.<\/p>\n\n\n\n
              <\/circle><\/circle><\/circle><\/g><\/svg><\/span><\/path><\/path><\/svg><\/span>
              $ sudo apt install gnuplot<\/span><\/span><\/code><\/pre><\/div>\n\n\n\n
              After executing option 2 in the program output we see that a file SelectPlot.dat<\/strong> was created in your local folder which contains running times for various input sizes. The first column specifies the input size and the second specifies the running time in microseconds.<\/p>\n\n\n\n
              Contents of SelectPlot.dat<\/strong><\/p>\n\n\n\n
              <\/circle><\/circle><\/circle><\/g><\/svg><\/span><\/path><\/path><\/svg><\/span>
              $ head SelectPlot.dat <\/span><\/span>\n100<\/span>\t<\/span>0.0001306533813<\/span><\/span>\n200<\/span>\t<\/span>0.0004434585571<\/span><\/span>\n300<\/span>\t<\/span>0.0009500980377<\/span><\/span>\n400<\/span>\t<\/span>0.001492977142<\/span><\/span>\n500<\/span>\t<\/span>0.002258777618<\/span><\/span>\n600<\/span>\t<\/span>0.003211975098<\/span><\/span>\n700<\/span>\t<\/span>0.004380464554<\/span><\/span>\n800<\/span>\t<\/span>0.005626916885<\/span><\/span>\n900<\/span>\t<\/span>0.006759643555<\/span><\/span>\n1000<\/span> <\/span>0.005615472794<\/span><\/span>\n<\/span><\/code><\/pre><\/div>\n\n\n\n
              Plotting Script for Gnuplot<\/h3>\n\n\n\n
              We will now see how to generate a plot graph of data contained in SelectPlot.dat<\/strong> and store it as an image. For that let’s write a gnuplot script file called 01SelectPlot.gpl<\/strong>. The contents of which are shown below<\/p>\n\n\n\n
              <\/circle><\/circle><\/circle><\/g><\/svg><\/span><\/path><\/path><\/svg><\/span>
              # Gnuplot script file for plotting data <\/span>in<\/span> file <\/span>"SelectPlot.dat"<\/span><\/span>\n# This file is called       01SelectPlot.gpl<\/span><\/span>\nset terminal png font arial<\/span><\/span>\nset title <\/span>"Time Complexity for Selection Sort"<\/span><\/span>\nset autoscale<\/span><\/span>\nset xlabel <\/span>"Size of Input"<\/span><\/span>\nset ylabel <\/span>"Sorting Time (microseconds)"<\/span><\/span>\nset grid<\/span><\/span>\nset output <\/span>"SelectPlot.png"<\/span><\/span>\nplot <\/span>"SelectPlot.dat"<\/span> t <\/span>'Selection Sort'<\/span> <\/span>with<\/span> lines<\/span><\/span><\/code><\/pre><\/div>\n\n\n\n
              The above file illustrates how to set various properties in the plot using the set<\/strong> command. Observe that the last line in the script generates the graph using plot<\/strong> command. <\/p>\n\n\n\n
              To execute the Gnuplot script you have to give the following command:<\/p>\n\n\n\n
              <\/circle><\/circle><\/circle><\/g><\/svg><\/span><\/path><\/path><\/svg><\/span>
              $ gnuplot 01SelectPlot.gpl<\/span><\/span><\/code><\/pre><\/div>\n\n\n\n
              You can now see that an image file by name SelectPlot.png<\/strong> containing the graph will be created in your local folder. <\/p>\n\n\n\n
              \"\"<\/a>
              Plot of Selection Sort<\/strong><\/figcaption><\/figure>\n\n\n\n
              Time Complexity Analysis<\/h3>\n\n\n\n
              Worst Case – O(n2<\/sup>)<\/strong><\/p>\n\n\n\n
              Average Case – O(n2<\/sup>)<\/strong><\/p>\n\n\n\n
              Best Case – O(n2<\/sup>)<\/strong><\/p>\n\n\n\n
              \n\n\n\n
              Module 2<\/h2>\n\n\n\n
              Quick Sort<\/h3>\n\n\n\n
              Sort a given set of n integer elements using Quick Sort method and compute its time complexity. Run the program for varied values of n> 5000, and record the time taken to sort. Plot a graph of the time taken versus n. The elements can be read from a file or can be generated using the random number generator. Demonstrate using C++\/Java how the divide-and-conquer method works along with its time complexity analysis: worst case, average case and best case.<\/p>\n\n\n\n
              C++ Code<\/h4>\n\n\n\n
              <\/circle><\/circle><\/circle><\/g><\/svg><\/span><\/path><\/path><\/svg><\/span>
              \/******************************************************************************<\/span><\/span>\n*File\t\t\t: 03QuickSort.c<\/span><\/span>\n*Description\t: Program to sort an array using Quick Sort<\/span><\/span>\n*Author\t\t\t: Prabodh C P<\/span><\/span>\n*Compiler\t\t: gcc compiler 7.5.0, Ubuntu 18.04<\/span><\/span>\n*Date\t\t\t: Friday 4 February 2020<\/span><\/span>\n******************************************************************************\/<\/span><\/span>\n<\/span>\n#include<\/span> <\/span><iostream><\/span><\/span>\n#include<\/span> <\/span><fstream><\/span><\/span>\n#include<\/span> <\/span><iomanip><\/span><\/span>\n#include<\/span> <\/span><vector><\/span><\/span>\n#include<\/span> <\/span><ctime><\/span><\/span>\n#include<\/span> <\/span><cstdlib><\/span><\/span>\nusing<\/span> <\/span>namespace<\/span> <\/span>std<\/span>;<\/span><\/span>\n<\/span>\nclass<\/span> <\/span>QuickSort<\/span>{<\/span><\/span>\n    vector <\/span><int><\/span> numList;<\/span><\/span>\n    <\/span>int<\/span> iNum;<\/span><\/span>\n    <\/span>public:<\/span><\/span>\n<\/span>\n    <\/span>void<\/span> <\/span>fnGenRandArray<\/span>(<\/span>int<\/span>);<\/span><\/span>\n    <\/span>void<\/span> <\/span>fnQuickSort<\/span>(<\/span>int<\/span>, <\/span>int<\/span>);<\/span><\/span>\n    <\/span>void<\/span> <\/span>fnDispArray<\/span>(<\/span>int<\/span>);<\/span><\/span>\n    <\/span>int<\/span> <\/span>fnPartition<\/span>(<\/span>int<\/span> ,<\/span>int<\/span> );<\/span><\/span>\n    <\/span>void<\/span> <\/span>fnSwap<\/span>(<\/span>int&<\/span>, <\/span>int&<\/span>);<\/span><\/span>\n};<\/span><\/span>\n<\/span>\nint<\/span> <\/span>main<\/span>( <\/span>int<\/span> <\/span>argc<\/span>, <\/span>char<\/span> <\/span>**<\/span>argv<\/span>)<\/span><\/span>\n{<\/span><\/span>\n<\/span>\n    <\/span>struct<\/span> <\/span>timespec<\/span> tv;<\/span><\/span>\n    <\/span>int<\/span> iChoice, i, iNum;<\/span><\/span>\n    <\/span>double<\/span> dStart, dEnd;<\/span><\/span>\n    QuickSort myListObj;<\/span><\/span>\n\tofstream <\/span>fout<\/span>(<\/span>"QuickPlot.dat"<\/span>, <\/span>ios<\/span>::out);<\/span><\/span>\n    <\/span>for<\/span>(;;)<\/span><\/span>\n    {<\/span><\/span>\n        cout <\/span><<<\/span> <\/span>"<\/span>\\n<\/span>1.Quick Sort<\/span>\\n<\/span>2.Plot the Graph<\/span>\\n<\/span>3.Exit"<\/span> ;<\/span><\/span>\n        cout <\/span><<<\/span> <\/span>"<\/span>\\n<\/span>Enter your choice<\/span>\\n<\/span>"<\/span>;<\/span><\/span>\n        cin <\/span>>><\/span> iChoice;<\/span><\/span>\n        <\/span>switch<\/span>(iChoice)<\/span><\/span>\n        {<\/span><\/span>\n            <\/span>case<\/span> <\/span>1<\/span>:<\/span><\/span>\n                    cout <\/span><<<\/span> <\/span>"<\/span>\\n<\/span>Enter number of elements to sort : "<\/span>; cin <\/span>>><\/span> iNum;<\/span><\/span>\n                    myListObj.<\/span>fnGenRandArray<\/span>(iNum);<\/span><\/span>\n                    cout <\/span><<<\/span> <\/span>"<\/span>\\n<\/span>Unsorted Array"<\/span> <\/span><<<\/span> endl;<\/span><\/span>\n                    myListObj.<\/span>fnDispArray<\/span>(iNum);<\/span><\/span>\n                    myListObj.<\/span>fnQuickSort<\/span>(<\/span>0<\/span>,iNum<\/span>-<\/span>1<\/span>);<\/span><\/span>\n                    cout <\/span><<<\/span> <\/span>"<\/span>\\n<\/span>Sorted Array"<\/span> <\/span><<<\/span> endl;<\/span><\/span>\n                    myListObj.<\/span>fnDispArray<\/span>(iNum);<\/span><\/span>\n                    <\/span>break<\/span>;<\/span><\/span>\n<\/span>\n            <\/span>case<\/span> <\/span>2<\/span>: <\/span>for<\/span>(i<\/span>=<\/span>100<\/span>;i<\/span><<\/span>100000<\/span>;i<\/span>+=<\/span>100<\/span>)<\/span><\/span>\n                    {<\/span><\/span>\n                        myListObj.<\/span>fnGenRandArray<\/span>(i);<\/span><\/span>\n                        <\/span>clock_gettime<\/span>(CLOCK_REALTIME, <\/span>&<\/span>tv);<\/span><\/span>\n                        dStart <\/span>=<\/span> tv.tv_sec <\/span>+<\/span> tv.tv_nsec<\/span>\/<\/span>1000000000.0<\/span>;<\/span><\/span>\n                        myListObj.<\/span>fnQuickSort<\/span>(<\/span>0<\/span>,i<\/span>-<\/span>1<\/span>);<\/span><\/span>\n                        <\/span>clock_gettime<\/span>(CLOCK_REALTIME, <\/span>&<\/span>tv);<\/span><\/span>\n                        dEnd <\/span>=<\/span> tv.tv_sec <\/span>+<\/span> tv.tv_nsec<\/span>\/<\/span>1000000000.0<\/span>;<\/span><\/span>\n<\/span>\n                        fout <\/span><<<\/span> i <\/span><<<\/span> <\/span>"<\/span>\\t<\/span>"<\/span> <\/span><<<\/span> <\/span>setprecision<\/span>(<\/span>10<\/span>) <\/span><<<\/span> dEnd <\/span>-<\/span> dStart <\/span><<<\/span> endl;<\/span><\/span>\n                    }<\/span><\/span>\n                    cout <\/span><<<\/span> <\/span>"<\/span>\\n<\/span>Data File generated and stored in file < QuickPlot.dat >.<\/span>\\n<\/span> Use a plotting utility<\/span>\\n<\/span>"<\/span>;<\/span><\/span>\n                    <\/span>break<\/span>;<\/span><\/span>\n            <\/span>case<\/span> <\/span>3<\/span>:<\/span><\/span>\n                    <\/span>exit<\/span>(<\/span>0<\/span>);<\/span><\/span>\n        }<\/span><\/span>\n    }<\/span><\/span>\n    fout.<\/span>close<\/span>();<\/span><\/span>\n    <\/span>return<\/span> <\/span>0<\/span>;<\/span><\/span>\n}<\/span><\/span>\n<\/span>\n<\/span>\n\/******************************************************************************<\/span><\/span>\n*Function: fnPartition<\/span><\/span>\n*Description: Function to partition an iaArray using First element as Pivot<\/span><\/span>\n*Function parameters:<\/span><\/span>\n*\tint l - start index of the subiaArray to be sorted<\/span><\/span>\n*\tint r - end index of the subiaArray to be sorted<\/span><\/span>\n*<\/span>RETURNS:<\/span> integer value specifying the location of partition<\/span><\/span>\n******************************************************************************\/<\/span><\/span>\nint<\/span> <\/span>QuickSort<\/span> :: <\/span>fnPartition<\/span>(<\/span>int<\/span> <\/span>l<\/span>, <\/span>int<\/span> <\/span>r<\/span>)<\/span><\/span>\n{<\/span><\/span>\n\t<\/span>int<\/span> i,j;<\/span><\/span>\n\t<\/span>int<\/span> p;<\/span><\/span>\n\tp <\/span>=<\/span> numList[l];<\/span><\/span>\n\ti <\/span>=<\/span> l;<\/span><\/span>\n\tj <\/span>=<\/span> r<\/span>+<\/span>1<\/span>;<\/span><\/span>\n\t<\/span>do<\/span><\/span>\n\t{<\/span><\/span>\n\t\t<\/span>do<\/span> { i<\/span>++<\/span>; } <\/span>while<\/span> (numList[i] <\/span><<\/span> p);<\/span><\/span>\n\t\t<\/span>do<\/span> { j<\/span>--<\/span>; } <\/span>while<\/span> (numList[j] <\/span>><\/span> p);<\/span><\/span>\n\t\t<\/span>fnSwap<\/span>(numList[i], numList[j]);<\/span><\/span>\n\t}<\/span>while<\/span> (i<\/span><<\/span>j);<\/span><\/span>\n\t<\/span>fnSwap<\/span>(numList[i], numList[j]);<\/span><\/span>\n\t<\/span>fnSwap<\/span>(numList[l], numList[j]);<\/span><\/span>\n\t<\/span>return<\/span> j;<\/span><\/span>\n}<\/span><\/span>\n<\/span>\n\/******************************************************************************<\/span><\/span>\n*Function: fnQuickSort<\/span><\/span>\n*Description: Function to sort elements in an iaArray using Quick Sort<\/span><\/span>\n*Function parameters:<\/span><\/span>\n*\tint l - start index of the subiaArray to be sorted<\/span><\/span>\n*\tint r - end index of the subiaArray to be sorted*RETURNS\t: no value<\/span><\/span>\n******************************************************************************\/<\/span><\/span>\nvoid<\/span> <\/span>QuickSort<\/span> :: <\/span>fnQuickSort<\/span>(<\/span>int<\/span> <\/span>l<\/span>, <\/span>int<\/span> <\/span>r<\/span>)<\/span><\/span>\n{<\/span><\/span>\n\t<\/span>int<\/span> s;<\/span><\/span>\n\t<\/span>if<\/span> (l <\/span><<\/span> r)<\/span><\/span>\n\t{<\/span><\/span>\n\t\ts <\/span>=<\/span> <\/span>fnPartition<\/span>(l, r);<\/span><\/span>\n\t\t<\/span>fnQuickSort<\/span>(l, s<\/span>-<\/span>1<\/span>);<\/span><\/span>\n\t\t<\/span>fnQuickSort<\/span>(s<\/span>+<\/span>1<\/span>, r);<\/span><\/span>\n\t}<\/span><\/span>\n}<\/span><\/span>\n<\/span>\nvoid<\/span> <\/span>QuickSort<\/span>::<\/span>fnGenRandArray<\/span>(<\/span>int<\/span> <\/span>n<\/span>)<\/span><\/span>\n{<\/span><\/span>\n    <\/span>int<\/span> i, iVal;<\/span><\/span>\n<\/span>\n\t<\/span>srand<\/span>(<\/span>time<\/span>(<\/span>NULL<\/span>));<\/span><\/span>\n\t<\/span>for<\/span>(i<\/span>=<\/span>0<\/span>;i<\/span><<\/span>n;i<\/span>++<\/span>)<\/span><\/span>\n\t{<\/span><\/span>\n        iVal <\/span>=<\/span> <\/span>rand<\/span>()<\/span>%<\/span>10000<\/span>;<\/span><\/span>\n        numList.<\/span>push_back<\/span>(iVal);<\/span><\/span>\n\t}<\/span><\/span>\n}<\/span><\/span>\n<\/span>\nvoid<\/span> <\/span>QuickSort<\/span>::<\/span>fnDispArray<\/span>(<\/span>int<\/span> <\/span>n<\/span>)<\/span><\/span>\n{<\/span><\/span>\n    <\/span>int<\/span> i;<\/span><\/span>\n\t<\/span>for<\/span>(i<\/span>=<\/span>0<\/span>;i<\/span><<\/span>n;i<\/span>++<\/span>)<\/span><\/span>\n\t{<\/span><\/span>\n        cout <\/span><<<\/span> <\/span>setw<\/span>(<\/span>8<\/span>) <\/span><<<\/span> numList[i] <\/span><<<\/span> endl;<\/span><\/span>\n    }<\/span><\/span>\n}<\/span><\/span>\n<\/span>\nvoid<\/span> <\/span>QuickSort<\/span>::<\/span>fnSwap<\/span>(<\/span>int<\/span> <\/span>&<\/span>a<\/span>,<\/span>int<\/span> <\/span>&<\/span>b<\/span>)<\/span><\/span>\n{<\/span><\/span>\n\t<\/span>int<\/span> t;<\/span><\/span>\n\tt <\/span>=<\/span> a;<\/span><\/span>\n\ta <\/span>=<\/span> b;<\/span><\/span>\n\tb <\/span>=<\/span> t;<\/span><\/span>\n}<\/span><\/span><\/code><\/pre><\/div>\n\n\n\n
              Java Code<\/h4>\n\n\n\n
              <\/circle><\/circle><\/circle><\/g><\/svg><\/span><\/path><\/path><\/svg><\/span>
              import<\/span> java.util.ArrayList;<\/span><\/span>\nimport<\/span> java.util.List;<\/span><\/span>\nimport<\/span> java.io.FileWriter;<\/span><\/span>\nimport<\/span> java.io.IOException;<\/span><\/span>\nimport<\/span> java.io.PrintWriter;<\/span><\/span>\n<\/span>\npublic<\/span> <\/span>class<\/span> <\/span>QuickSort<\/span> {<\/span><\/span>\n    <\/span>private<\/span> List<<\/span>Integer<\/span>> numList;<\/span><\/span>\n<\/span>\n    <\/span>public<\/span> <\/span>QuickSort<\/span>() {<\/span><\/span>\n        numList <\/span>=<\/span> <\/span>new<\/span> ArrayList<>();<\/span><\/span>\n    }<\/span><\/span>\n<\/span>\n    <\/span>public<\/span> <\/span>void<\/span> <\/span>fnGenRandArray<\/span>(<\/span>int<\/span> <\/span>n<\/span>) {<\/span><\/span>\n        <\/span>int<\/span> i, iVal;<\/span><\/span>\n        <\/span>for<\/span> (i <\/span>=<\/span> <\/span>0<\/span>; i <\/span><<\/span> n; i<\/span>++<\/span>) {<\/span><\/span>\n            iVal <\/span>=<\/span> (<\/span>int<\/span>) (Math.<\/span>random<\/span>() <\/span>*<\/span> <\/span>10000<\/span>);<\/span><\/span>\n            numList.<\/span>add<\/span>(iVal);<\/span><\/span>\n        }<\/span><\/span>\n    }<\/span><\/span>\n<\/span>\n    <\/span>public<\/span> <\/span>void<\/span> <\/span>fnDispArray<\/span>(<\/span>int<\/span> <\/span>n<\/span>) {<\/span><\/span>\n        <\/span>for<\/span> (<\/span>int<\/span> i <\/span>=<\/span> <\/span>0<\/span>; i <\/span><<\/span> n; i<\/span>++<\/span>) {<\/span><\/span>\n            System.out.<\/span>println<\/span>(String.<\/span>format<\/span>(<\/span>"%8d"<\/span>, numList.<\/span>get<\/span>(i)));<\/span><\/span>\n        }<\/span><\/span>\n    }<\/span><\/span>\n<\/span>\n    <\/span>public<\/span> <\/span>void<\/span> <\/span>fnSortArray<\/span>(<\/span>int<\/span> <\/span>l<\/span>, <\/span>int<\/span> <\/span>r<\/span>) {<\/span><\/span>\n        <\/span>if<\/span> (l <\/span><<\/span> r) {<\/span><\/span>\n            <\/span>int<\/span> s <\/span>=<\/span> <\/span>fnPartition<\/span>(l, r);<\/span><\/span>\n            <\/span>fnSortArray<\/span>(l, s <\/span>-<\/span> <\/span>1<\/span>);<\/span><\/span>\n            <\/span>fnSortArray<\/span>(s <\/span>+<\/span> <\/span>1<\/span>, r);<\/span><\/span>\n        }<\/span><\/span>\n    }<\/span><\/span>\n<\/span>\n    <\/span>public<\/span> <\/span>int<\/span> <\/span>fnPartition<\/span>(<\/span>int<\/span> <\/span>l<\/span>, <\/span>int<\/span> <\/span>r<\/span>) {<\/span><\/span>\n        <\/span>int<\/span> pivot <\/span>=<\/span> numList.<\/span>get<\/span>(l);<\/span><\/span>\n        <\/span>int<\/span> i <\/span>=<\/span> l <\/span>+<\/span> <\/span>1<\/span>;<\/span><\/span>\n        <\/span>int<\/span> j <\/span>=<\/span> r;<\/span><\/span>\n        <\/span>while<\/span> (i <\/span><=<\/span> j) {<\/span><\/span>\n            <\/span>if<\/span> (numList.<\/span>get<\/span>(i) <\/span><=<\/span> pivot) {<\/span><\/span>\n                i<\/span>++<\/span>;<\/span><\/span>\n            } <\/span>else<\/span> <\/span>if<\/span> (numList.<\/span>get<\/span>(j) <\/span>><\/span> pivot) {<\/span><\/span>\n                j<\/span>--<\/span>;<\/span><\/span>\n            } <\/span>else<\/span> {<\/span><\/span>\n                <\/span>int<\/span> temp <\/span>=<\/span> numList.<\/span>get<\/span>(i);<\/span><\/span>\n                numList.<\/span>set<\/span>(i, numList.<\/span>get<\/span>(j));<\/span><\/span>\n                numList.<\/span>set<\/span>(j, temp);<\/span><\/span>\n                i<\/span>++<\/span>;<\/span><\/span>\n                j<\/span>--<\/span>;<\/span><\/span>\n            }<\/span><\/span>\n        }<\/span><\/span>\n        <\/span>int<\/span> temp <\/span>=<\/span> numList.<\/span>get<\/span>(l);<\/span><\/span>\n        numList.<\/span>set<\/span>(l, numList.<\/span>get<\/span>(j));<\/span><\/span>\n        numList.<\/span>set<\/span>(j, temp);<\/span><\/span>\n        <\/span>return<\/span> j;<\/span><\/span>\n    }<\/span><\/span>\n<\/span>\n    <\/span>public<\/span> <\/span>static<\/span> <\/span>void<\/span> <\/span>main<\/span>(<\/span>String<\/span>[] <\/span>args<\/span>) {<\/span><\/span>\n        <\/span>long<\/span> startTime, endTime;<\/span><\/span>\n        <\/span>int<\/span> iChoice, iNum;<\/span><\/span>\n        QuickSort myListObj <\/span>=<\/span> <\/span>new<\/span> <\/span>QuickSort<\/span>();<\/span><\/span>\n<\/span>\n        <\/span>try<\/span> (PrintWriter fout <\/span>=<\/span> <\/span>new<\/span> <\/span>PrintWriter<\/span>(<\/span>new<\/span> <\/span>FileWriter<\/span>(<\/span>"QuickPlot.dat"<\/span>))) {<\/span><\/span>\n            <\/span>for<\/span> (;;) {<\/span><\/span>\n                System.out.<\/span>println<\/span>(<\/span>"<\/span>\\n<\/span>1.Quick Sort<\/span>\\n<\/span>2.Plot the Graph<\/span>\\n<\/span>3.Exit"<\/span>);<\/span><\/span>\n                System.out.<\/span>println<\/span>(<\/span>"Enter your choice"<\/span>);<\/span><\/span>\n                iChoice <\/span>=<\/span> Integer.<\/span>parseInt<\/span>(System.<\/span>console<\/span>().<\/span>readLine<\/span>());<\/span><\/span>\n<\/span>\n                <\/span>switch<\/span> (iChoice) {<\/span><\/span>\n                    <\/span>case<\/span> <\/span>1<\/span>:<\/span><\/span>\n                        System.out.<\/span>print<\/span>(<\/span>"Enter number of elements to sort : "<\/span>);<\/span><\/span>\n                        iNum <\/span>=<\/span> Integer.<\/span>parseInt<\/span>(System.<\/span>console<\/span>().<\/span>readLine<\/span>());<\/span><\/span>\n                        myListObj.<\/span>fnGenRandArray<\/span>(iNum);<\/span><\/span>\n<\/span>\n                        System.out.<\/span>println<\/span>(<\/span>"<\/span>\\n<\/span>Unsorted Array"<\/span>);<\/span><\/span>\n                        myListObj.<\/span>fnDispArray<\/span>(iNum);<\/span><\/span>\n<\/span>\n                        myListObj.<\/span>fnSortArray<\/span>(<\/span>0<\/span>, iNum <\/span>-<\/span> <\/span>1<\/span>);<\/span><\/span>\n<\/span>\n                        System.out.<\/span>println<\/span>(<\/span>"<\/span>\\n<\/span>Sorted Array"<\/span>);<\/span><\/span>\n                        myListObj.<\/span>fnDispArray<\/span>(iNum);<\/span><\/span>\n                        <\/span>break<\/span>;<\/span><\/span>\n                    <\/span>case<\/span> <\/span>2<\/span>:<\/span><\/span>\n                        <\/span>for<\/span> (<\/span>int<\/span> i <\/span>=<\/span> <\/span>100<\/span>; i <\/span><<\/span> <\/span>100000<\/span>; i <\/span>+=<\/span> <\/span>100<\/span>) {<\/span><\/span>\n                            myListObj.<\/span>fnGenRandArray<\/span>(i);<\/span><\/span>\n<\/span>\n                            startTime <\/span>=<\/span> System.<\/span>nanoTime<\/span>();<\/span><\/span>\n                            myListObj.<\/span>fnSortArray<\/span>(<\/span>0<\/span>, i <\/span>-<\/span> <\/span>1<\/span>);<\/span><\/span>\n                            endTime <\/span>=<\/span> System.<\/span>nanoTime<\/span>();<\/span><\/span>\n<\/span>\n                            fout.<\/span>println<\/span>(i <\/span>+<\/span> <\/span>"<\/span>\\t<\/span>"<\/span> <\/span>+<\/span> ((endTime <\/span>-<\/span> startTime) <\/span>\/<\/span> <\/span>1e9<\/span>));<\/span><\/span>\n                        }<\/span><\/span>\n<\/span>\n                        System.out.<\/span>println<\/span>(<\/span>"<\/span>\\n<\/span>Data File generated and stored in file < QuickPlot.dat >. Use a plotting utility"<\/span>);<\/span><\/span>\n                        <\/span>break<\/span>;<\/span><\/span>\n                    <\/span>case<\/span> <\/span>3<\/span>:<\/span><\/span>\n                        System.<\/span>exit<\/span>(<\/span>0<\/span>);<\/span><\/span>\n                }<\/span><\/span>\n            }<\/span><\/span>\n        } <\/span>catch<\/span> (IOException <\/span>e<\/span>) {<\/span><\/span>\n            System.out.<\/span>println<\/span>(<\/span>"Error: "<\/span> <\/span>+<\/span> e.<\/span>getMessage<\/span>());<\/span><\/span>\n        }<\/span><\/span>\n    }<\/span><\/span>\n}<\/span><\/span>\n<\/span><\/code><\/pre><\/div>\n\n\n\n
              Output<\/h4>\n\n\n\n
              <\/circle><\/circle><\/circle><\/g><\/svg><\/span><\/path><\/path><\/svg><\/span>
              1.Quick Sort<\/span><\/span>\n2.Plot the Graph<\/span><\/span>\n3.Exit<\/span><\/span>\nEnter your choice<\/span><\/span>\n1<\/span><\/span>\n<\/span>\nEnter number <\/span>of<\/span> elements to <\/span>sort<\/span> : <\/span>5<\/span><\/span>\n<\/span>\nUnsorted Array<\/span><\/span>\n    <\/span>2828<\/span><\/span>\n     <\/span>710<\/span><\/span>\n    <\/span>6721<\/span><\/span>\n    <\/span>2947<\/span><\/span>\n    <\/span>8353<\/span><\/span>\n<\/span>\nSorted Array<\/span><\/span>\n     <\/span>710<\/span><\/span>\n    <\/span>2828<\/span><\/span>\n    <\/span>2947<\/span><\/span>\n    <\/span>6721<\/span><\/span>\n    <\/span>8353<\/span><\/span>\n<\/span>\n1.Quick Sort<\/span><\/span>\n2.Plot the Graph<\/span><\/span>\n3.Exit<\/span><\/span>\nEnter your choice<\/span><\/span>\n2<\/span><\/span>\n<\/span>\nData File generated and stored <\/span>in<\/span> file <\/span><<\/span> QuickPlot.dat <\/span>><\/span>.<\/span><\/span>\n Use a plotting utility<\/span><\/span>\n<\/span>\n1.Quick Sort<\/span><\/span>\n2.Plot the Graph<\/span><\/span>\n3.Exit<\/span><\/span>\nEnter your choice<\/span><\/span>\n3<\/span><\/span>\n<\/span><\/code><\/pre><\/div>\n\n\n\n
              Plotting Script for Gnuplot<\/h3>\n\n\n\n
              We will now see how to generate a plot graph of data contained in QuickPlot.dat<\/strong> and store it as an image. Let’s write a gnuplot script file called 03QuickPlot.gpl<\/strong> to do the same. The contents of which are shown below<\/p>\n\n\n\n
              <\/circle><\/circle><\/circle><\/g><\/svg><\/span><\/path><\/path><\/svg><\/span>
              # Gnuplot script file for plotting data <\/span>in<\/span> file <\/span>"QuickPlot.dat"<\/span><\/span>\n# This file is called       03QuickPlot.gpl<\/span><\/span>\nset terminal png font arial<\/span><\/span>\nset title <\/span>"Time Complexity for Quick Sort"<\/span><\/span>\nset autoscale<\/span><\/span>\nset xlabel <\/span>"Size of Input"<\/span><\/span>\nset ylabel <\/span>"Sorting Time (microseconds)"<\/span><\/span>\nset grid<\/span><\/span>\nset output <\/span>"QuickPlot.png"<\/span><\/span>\nplot <\/span>"QuickPlot.dat"<\/span> t <\/span>'Quick Sort'<\/span> <\/span>with<\/span> lines<\/span><\/span><\/code><\/pre><\/div>\n\n\n\n
              To execute the Gnuplot script you have to give the following command:<\/p>\n\n\n\n
              <\/circle><\/circle><\/circle><\/g><\/svg><\/span><\/path><\/path><\/svg><\/span>
              $<\/span> <\/span>gnuplot<\/span> <\/span>03<\/span>QuickPlot.gpl<\/span><\/span><\/code><\/pre><\/div>\n\n\n\n
              You can now see that an image file by name QuickPlot.png<\/strong> containing the graph will be created in your local folder. <\/p>\n\n\n\n
              \"\"<\/a><\/figure>\n\n\n\n
              Time Complexity Analysis of Quick Sort<\/h3>\n\n\n\n
              Worst Case – O(n2<\/sup>)<\/strong><\/p>\n\n\n\n
              Average Case – O(n*log n)<\/strong><\/strong><\/p>\n\n\n\n
              Best Case – O(n*log n)<\/strong><\/strong><\/p>\n\n\n\n
              Merge Sort<\/h3>\n\n\n\n
              Sort a given set of n integer elements using Merge Sort method and compute its time complexity. Run the program for varied values of n> 5000, and record the time taken to sort. Plot a graph of the time taken versus n. The elements can be read from a file or can be generated using the random number generator. Demonstrate using C++\/Java how the divide-and-conquer method works along with its time complexity analysis: worst case, average case and best case.<\/p>\n\n\n\n
              C++ Code<\/h4>\n\n\n\n
              <\/circle><\/circle><\/circle><\/g><\/svg><\/span><\/path><\/path><\/svg><\/span>
              \/******************************************************************************<\/span><\/span>\n*File\t\t: 03MergeSort.cpp<\/span><\/span>\n*Description\t: Program to sort an array using Merge Sort<\/span><\/span>\n*Author: Prabodh C P<\/span><\/span>\n*Compiler: gcc compiler 7.5.0, Ubuntu 18.04<\/span><\/span>\n*Date: Friday 4 February 2020<\/span><\/span>\n******************************************************************************\/<\/span><\/span>\n#include<\/span> <\/span><iostream><\/span><\/span>\n#include<\/span> <\/span><fstream><\/span><\/span>\n#include<\/span> <\/span><iomanip><\/span><\/span>\n#include<\/span> <\/span><vector><\/span><\/span>\n#include<\/span> <\/span><ctime><\/span><\/span>\n#include<\/span> <\/span><cstdlib><\/span><\/span>\nusing<\/span> <\/span>namespace<\/span> <\/span>std<\/span>;<\/span><\/span>\n<\/span>\nclass<\/span> <\/span>MergeSort<\/span>{<\/span><\/span>\n    vector <\/span><int><\/span> numList;<\/span><\/span>\n    <\/span>int<\/span> iNum;<\/span><\/span>\n    <\/span>public:<\/span><\/span>\n<\/span>\n    <\/span>void<\/span> <\/span>fnGenRandArray<\/span>(<\/span>int<\/span>);<\/span><\/span>\n    <\/span>void<\/span> <\/span>fnSortArray<\/span>(<\/span>int<\/span>, <\/span>int<\/span>);<\/span><\/span>\n    <\/span>void<\/span> <\/span>fnDispArray<\/span>(<\/span>int<\/span>);<\/span><\/span>\n    <\/span>void<\/span> <\/span>fnMerge<\/span>(<\/span>int<\/span> ,<\/span>int<\/span> ,<\/span>int<\/span>);<\/span><\/span>\n};<\/span><\/span>\n<\/span>\nint<\/span> <\/span>main<\/span>( <\/span>int<\/span> <\/span>argc<\/span>, <\/span>char<\/span> <\/span>**<\/span>argv<\/span>)<\/span><\/span>\n{<\/span><\/span>\n<\/span>\n    <\/span>struct<\/span> <\/span>timespec<\/span> tv;<\/span><\/span>\n    <\/span>int<\/span> iChoice, i, iNum;<\/span><\/span>\n    <\/span>double<\/span> dStart, dEnd;<\/span><\/span>\n    MergeSort myListObj;<\/span><\/span>\n\tofstream <\/span>fout<\/span>(<\/span>"MergePlot.dat"<\/span>, <\/span>ios<\/span>::out);<\/span><\/span>\n    <\/span>for<\/span>(;;)<\/span><\/span>\n    {<\/span><\/span>\n        cout <\/span><<<\/span> <\/span>"<\/span>\\n<\/span>1.MergeSort<\/span>\\n<\/span>2.Plot the Graph<\/span>\\n<\/span>3.Exit"<\/span> ;<\/span><\/span>\n        cout <\/span><<<\/span> <\/span>"<\/span>\\n<\/span>Enter your choice<\/span>\\n<\/span>"<\/span>;<\/span><\/span>\n        cin <\/span>>><\/span> iChoice;<\/span><\/span>\n        <\/span>switch<\/span>(iChoice)<\/span><\/span>\n        {<\/span><\/span>\n            <\/span>case<\/span> <\/span>1<\/span>:<\/span><\/span>\n                    cout <\/span><<<\/span> <\/span>"<\/span>\\n<\/span>Enter number of elements to sort : "<\/span>; cin <\/span>>><\/span> iNum;<\/span><\/span>\n                    myListObj.<\/span>fnGenRandArray<\/span>(iNum);<\/span><\/span>\n                    cout <\/span><<<\/span> <\/span>"<\/span>\\n<\/span>Unsorted Array"<\/span> <\/span><<<\/span> endl;<\/span><\/span>\n                    myListObj.<\/span>fnDispArray<\/span>(iNum);<\/span><\/span>\n                    myListObj.<\/span>fnSortArray<\/span>(<\/span>0<\/span>,iNum<\/span>-<\/span>1<\/span>);<\/span><\/span>\n                    cout <\/span><<<\/span> <\/span>"<\/span>\\n<\/span>Sorted Array"<\/span> <\/span><<<\/span> endl;<\/span><\/span>\n                    myListObj.<\/span>fnDispArray<\/span>(iNum);<\/span><\/span>\n                    <\/span>break<\/span>;<\/span><\/span>\n<\/span>\n            <\/span>case<\/span> <\/span>2<\/span>: <\/span>for<\/span>(i<\/span>=<\/span>100<\/span>;i<\/span><<\/span>100000<\/span>;i<\/span>+=<\/span>100<\/span>)<\/span><\/span>\n                    {<\/span><\/span>\n                        myListObj.<\/span>fnGenRandArray<\/span>(i);<\/span><\/span>\n                        <\/span>clock_gettime<\/span>(CLOCK_REALTIME, <\/span>&<\/span>tv);<\/span><\/span>\n                        dStart <\/span>=<\/span> tv.tv_sec <\/span>+<\/span> tv.tv_nsec<\/span>\/<\/span>1000000000.0<\/span>;<\/span><\/span>\n                        myListObj.<\/span>fnSortArray<\/span>(<\/span>0<\/span>,i<\/span>-<\/span>1<\/span>);<\/span><\/span>\n                        <\/span>clock_gettime<\/span>(CLOCK_REALTIME, <\/span>&<\/span>tv);<\/span><\/span>\n                        dEnd <\/span>=<\/span> tv.tv_sec <\/span>+<\/span> tv.tv_nsec<\/span>\/<\/span>1000000000.0<\/span>;<\/span><\/span>\n<\/span>\n                        fout <\/span><<<\/span> i <\/span><<<\/span> <\/span>"<\/span>\\t<\/span>"<\/span> <\/span><<<\/span> <\/span>setprecision<\/span>(<\/span>10<\/span>) <\/span><<<\/span> dEnd <\/span>-<\/span> dStart <\/span><<<\/span> endl;<\/span><\/span>\n                    }<\/span><\/span>\n                    cout <\/span><<<\/span> <\/span>"<\/span>\\n<\/span>Data File generated and stored in file < MergePlot.dat >.<\/span>\\n<\/span> Use a plotting utility<\/span>\\n<\/span>"<\/span>;<\/span><\/span>\n                    <\/span>break<\/span>;<\/span><\/span>\n            <\/span>case<\/span> <\/span>3<\/span>:<\/span><\/span>\n                    <\/span>exit<\/span>(<\/span>0<\/span>);<\/span><\/span>\n        }<\/span><\/span>\n    }<\/span><\/span>\n    fout.<\/span>close<\/span>();<\/span><\/span>\n    <\/span>return<\/span> <\/span>0<\/span>;<\/span><\/span>\n}<\/span><\/span>\n<\/span>\nvoid<\/span> <\/span>MergeSort<\/span>::<\/span>fnGenRandArray<\/span>(<\/span>int<\/span> <\/span>n<\/span>)<\/span><\/span>\n{<\/span><\/span>\n    <\/span>int<\/span> i, iVal;<\/span><\/span>\n<\/span>\n\t<\/span>srand<\/span>(<\/span>time<\/span>(<\/span>NULL<\/span>));<\/span><\/span>\n\t<\/span>for<\/span>(i<\/span>=<\/span>0<\/span>;i<\/span><<\/span>n;i<\/span>++<\/span>)<\/span><\/span>\n\t{<\/span><\/span>\n        iVal <\/span>=<\/span> <\/span>rand<\/span>()<\/span>%<\/span>10000<\/span>;<\/span><\/span>\n        numList.<\/span>push_back<\/span>(iVal);<\/span><\/span>\n\t}<\/span><\/span>\n}<\/span><\/span>\n<\/span>\nvoid<\/span> <\/span>MergeSort<\/span>::<\/span>fnDispArray<\/span>(<\/span>int<\/span> <\/span>n<\/span>)<\/span><\/span>\n{<\/span><\/span>\n    <\/span>int<\/span> i;<\/span><\/span>\n\t<\/span>for<\/span>(i<\/span>=<\/span>0<\/span>;i<\/span><<\/span>n;i<\/span>++<\/span>)<\/span><\/span>\n\t{<\/span><\/span>\n        cout <\/span><<<\/span> <\/span>setw<\/span>(<\/span>8<\/span>) <\/span><<<\/span> numList[i] <\/span><<<\/span> endl;<\/span><\/span>\n    }<\/span><\/span>\n}<\/span><\/span>\n<\/span>\n<\/span>\nvoid<\/span> <\/span>MergeSort<\/span>::<\/span>fnSortArray<\/span>(<\/span>int<\/span> <\/span>low<\/span>,<\/span>int<\/span> <\/span>high<\/span>)<\/span><\/span>\n{<\/span><\/span>\n\t<\/span>int<\/span> mid;<\/span><\/span>\n\t<\/span>if<\/span>(low<\/span><<\/span>high)<\/span><\/span>\n\t{<\/span><\/span>\n\t\tmid<\/span>=<\/span>(low<\/span>+<\/span>high)<\/span>\/<\/span>2<\/span>;<\/span><\/span>\n\t\t<\/span>fnSortArray<\/span>(low,mid);<\/span><\/span>\n\t\t<\/span>fnSortArray<\/span>(mid<\/span>+<\/span>1<\/span>,high);<\/span><\/span>\n\t\t<\/span>fnMerge<\/span>(low,mid,high);<\/span><\/span>\n\t}<\/span><\/span>\n}<\/span><\/span>\n<\/span>\nvoid<\/span> <\/span>MergeSort<\/span>::<\/span>fnMerge<\/span>(<\/span>int<\/span> <\/span>low<\/span>,<\/span>int<\/span> <\/span>mid<\/span>,<\/span>int<\/span> <\/span>high<\/span>)<\/span><\/span>\n{<\/span><\/span>\n    vector <\/span><int><\/span> <\/span>b<\/span>(<\/span>0<\/span>);<\/span><\/span>\n\t<\/span>int<\/span>  i,j;<\/span><\/span>\n\ti<\/span>=<\/span>low;<\/span><\/span>\n\tj<\/span>=<\/span>mid<\/span>+<\/span>1<\/span>;<\/span><\/span>\n\t<\/span>int<\/span> k<\/span>=<\/span>0<\/span>;<\/span><\/span>\n\t<\/span>while<\/span>(i<\/span><=<\/span>mid <\/span>&&<\/span> j<\/span><=<\/span>high)<\/span><\/span>\n\t{<\/span><\/span>\n\t\t<\/span>if<\/span>(numList[i]<\/span><<\/span>numList[j])<\/span><\/span>\n            b.<\/span>push_back<\/span>(numList[i<\/span>++<\/span>]);<\/span><\/span>\n\t\t<\/span>else<\/span><\/span>\n            b.<\/span>push_back<\/span>(numList[j<\/span>++<\/span>]);<\/span><\/span>\n\t}<\/span><\/span>\n\t<\/span>while<\/span>(i<\/span><=<\/span>mid)<\/span><\/span>\n        b.<\/span>push_back<\/span>(numList[i<\/span>++<\/span>]);<\/span><\/span>\n\t<\/span>while<\/span>(j<\/span><=<\/span>high)<\/span><\/span>\n        b.<\/span>push_back<\/span>(numList[j<\/span>++<\/span>]);<\/span><\/span>\n    <\/span>for<\/span> (i<\/span>=<\/span>low;i<\/span><=<\/span>high;i<\/span>++<\/span>)<\/span><\/span>\n    {<\/span><\/span>\n    \tnumList[low<\/span>+<\/span>k] <\/span>=<\/span> b[k];<\/span><\/span>\n    \tk<\/span>++<\/span>;<\/span><\/span>\n    }<\/span><\/span>\n}<\/span><\/span>\n<\/span><\/code><\/pre><\/div>\n\n\n\n
              Java Code<\/h4>\n\n\n\n
              <\/circle><\/circle><\/circle><\/g><\/svg><\/span><\/path><\/path><\/svg><\/span>
              \/\/MergeSort.java<\/span><\/span>\nimport<\/span> java.util.ArrayList;<\/span><\/span>\nimport<\/span> java.util.List;<\/span><\/span>\nimport<\/span> java.io.FileWriter;<\/span><\/span>\nimport<\/span> java.io.IOException;<\/span><\/span>\nimport<\/span> java.io.PrintWriter;<\/span><\/span>\n<\/span>\npublic<\/span> <\/span>class<\/span> <\/span>MergeSort<\/span> {<\/span><\/span>\n    <\/span>private<\/span> List<<\/span>Integer<\/span>> numList;<\/span><\/span>\n<\/span>\n    <\/span>public<\/span> <\/span>MergeSort<\/span>() {<\/span><\/span>\n        numList <\/span>=<\/span> <\/span>new<\/span> ArrayList<>();<\/span><\/span>\n    }<\/span><\/span>\n<\/span>\n    <\/span>public<\/span> <\/span>void<\/span> <\/span>fnGenRandArray<\/span>(<\/span>int<\/span> <\/span>n<\/span>) {<\/span><\/span>\n        <\/span>int<\/span> i, iVal;<\/span><\/span>\n        <\/span>for<\/span> (i <\/span>=<\/span> <\/span>0<\/span>; i <\/span><<\/span> n; i<\/span>++<\/span>) {<\/span><\/span>\n            iVal <\/span>=<\/span> (<\/span>int<\/span>) (Math.<\/span>random<\/span>() <\/span>*<\/span> <\/span>10000<\/span>);<\/span><\/span>\n            numList.<\/span>add<\/span>(iVal);<\/span><\/span>\n        }<\/span><\/span>\n    }<\/span><\/span>\n<\/span>\n    <\/span>public<\/span> <\/span>void<\/span> <\/span>fnDispArray<\/span>(<\/span>int<\/span> <\/span>n<\/span>) {<\/span><\/span>\n        <\/span>for<\/span> (<\/span>int<\/span> i <\/span>=<\/span> <\/span>0<\/span>; i <\/span><<\/span> n; i<\/span>++<\/span>) {<\/span><\/span>\n            System.out.<\/span>println<\/span>(String.<\/span>format<\/span>(<\/span>"%8d"<\/span>, numList.<\/span>get<\/span>(i)));<\/span><\/span>\n        }<\/span><\/span>\n    }<\/span><\/span>\n<\/span>\n    <\/span>public<\/span> <\/span>void<\/span> <\/span>fnSortArray<\/span>(<\/span>int<\/span> <\/span>low<\/span>, <\/span>int<\/span> <\/span>high<\/span>) {<\/span><\/span>\n        <\/span>if<\/span> (low <\/span><<\/span> high) {<\/span><\/span>\n            <\/span>int<\/span> mid <\/span>=<\/span> (low <\/span>+<\/span> high) <\/span>\/<\/span> <\/span>2<\/span>;<\/span><\/span>\n            <\/span>fnSortArray<\/span>(low, mid);<\/span><\/span>\n            <\/span>fnSortArray<\/span>(mid <\/span>+<\/span> <\/span>1<\/span>, high);<\/span><\/span>\n            <\/span>fnMerge<\/span>(low, mid, high);<\/span><\/span>\n        }<\/span><\/span>\n    }<\/span><\/span>\n<\/span>\n    <\/span>public<\/span> <\/span>void<\/span> <\/span>fnMerge<\/span>(<\/span>int<\/span> <\/span>low<\/span>, <\/span>int<\/span> <\/span>mid<\/span>, <\/span>int<\/span> <\/span>high<\/span>) {<\/span><\/span>\n        List<<\/span>Integer<\/span>> b <\/span>=<\/span> <\/span>new<\/span> ArrayList<>();<\/span><\/span>\n        <\/span>int<\/span> i <\/span>=<\/span> low;<\/span><\/span>\n        <\/span>int<\/span> j <\/span>=<\/span> mid <\/span>+<\/span> <\/span>1<\/span>;<\/span><\/span>\n        <\/span>int<\/span> k <\/span>=<\/span> <\/span>0<\/span>;<\/span><\/span>\n        <\/span>while<\/span> (i <\/span><=<\/span> mid <\/span>&&<\/span> j <\/span><=<\/span> high) {<\/span><\/span>\n            <\/span>if<\/span> (numList.<\/span>get<\/span>(i) <\/span><<\/span> numList.<\/span>get<\/span>(j))<\/span><\/span>\n                b.<\/span>add<\/span>(numList.<\/span>get<\/span>(i<\/span>++<\/span>));<\/span><\/span>\n            <\/span>else<\/span><\/span>\n                b.<\/span>add<\/span>(numList.<\/span>get<\/span>(j<\/span>++<\/span>));<\/span><\/span>\n        }<\/span><\/span>\n        <\/span>while<\/span> (i <\/span><=<\/span> mid)<\/span><\/span>\n            b.<\/span>add<\/span>(numList.<\/span>get<\/span>(i<\/span>++<\/span>));<\/span><\/span>\n        <\/span>while<\/span> (j <\/span><=<\/span> high)<\/span><\/span>\n            b.<\/span>add<\/span>(numList.<\/span>get<\/span>(j<\/span>++<\/span>));<\/span><\/span>\n        <\/span>for<\/span> (i <\/span>=<\/span> low; i <\/span><=<\/span> high; i<\/span>++<\/span>) {<\/span><\/span>\n            numList.<\/span>set<\/span>(i, b.<\/span>get<\/span>(k));<\/span><\/span>\n            k<\/span>++<\/span>;<\/span><\/span>\n        }<\/span><\/span>\n    }<\/span><\/span>\n<\/span>\n    <\/span>public<\/span> <\/span>static<\/span> <\/span>void<\/span> <\/span>main<\/span>(<\/span>String<\/span>[] <\/span>args<\/span>) {<\/span><\/span>\n        <\/span>long<\/span> startTime, endTime;<\/span><\/span>\n        <\/span>int<\/span> iChoice, iNum;<\/span><\/span>\n        MergeSort myListObj <\/span>=<\/span> <\/span>new<\/span> <\/span>MergeSort<\/span>();<\/span><\/span>\n<\/span>\n        <\/span>try<\/span> (PrintWriter fout <\/span>=<\/span> <\/span>new<\/span> <\/span>PrintWriter<\/span>(<\/span>new<\/span> <\/span>FileWriter<\/span>(<\/span>"MergePlot.dat"<\/span>))) {<\/span><\/span>\n            <\/span>for<\/span> (;;) {<\/span><\/span>\n                System.out.<\/span>println<\/span>(<\/span>"<\/span>\\n<\/span>1.MergeSort<\/span>\\n<\/span>2.Plot the Graph<\/span>\\n<\/span>3.Exit"<\/span>);<\/span><\/span>\n                System.out.<\/span>println<\/span>(<\/span>"Enter your choice"<\/span>);<\/span><\/span>\n                iChoice <\/span>=<\/span> Integer.<\/span>parseInt<\/span>(System.<\/span>console<\/span>().<\/span>readLine<\/span>());<\/span><\/span>\n<\/span>\n                <\/span>switch<\/span> (iChoice) {<\/span><\/span>\n                    <\/span>case<\/span> <\/span>1<\/span>:<\/span><\/span>\n                        System.out.<\/span>print<\/span>(<\/span>"Enter number of elements to sort : "<\/span>);<\/span><\/span>\n                        iNum <\/span>=<\/span> Integer.<\/span>parseInt<\/span>(System.<\/span>console<\/span>().<\/span>readLine<\/span>());<\/span><\/span>\n                        myListObj.<\/span>fnGenRandArray<\/span>(iNum);<\/span><\/span>\n<\/span>\n                        System.out.<\/span>println<\/span>(<\/span>"<\/span>\\n<\/span>Unsorted Array"<\/span>);<\/span><\/span>\n                        myListObj.<\/span>fnDispArray<\/span>(iNum);<\/span><\/span>\n<\/span>\n                        myListObj.<\/span>fnSortArray<\/span>(<\/span>0<\/span>, iNum <\/span>-<\/span> <\/span>1<\/span>);<\/span><\/span>\n<\/span>\n                        System.out.<\/span>println<\/span>(<\/span>"<\/span>\\n<\/span>Sorted Array"<\/span>);<\/span><\/span>\n                        myListObj.<\/span>fnDispArray<\/span>(iNum);<\/span><\/span>\n                        <\/span>break<\/span>;<\/span><\/span>\n                    <\/span>case<\/span> <\/span>2<\/span>:<\/span><\/span>\n                        <\/span>for<\/span> (<\/span>int<\/span> i <\/span>=<\/span> <\/span>100<\/span>; i <\/span><<\/span> <\/span>100000<\/span>; i <\/span>+=<\/span> <\/span>100<\/span>) {<\/span><\/span>\n                            myListObj.<\/span>fnGenRandArray<\/span>(i);<\/span><\/span>\n<\/span>\n                            startTime <\/span>=<\/span> System.<\/span>nanoTime<\/span>();<\/span><\/span>\n                            myListObj.<\/span>fnSortArray<\/span>(<\/span>0<\/span>, i <\/span>-<\/span> <\/span>1<\/span>);<\/span><\/span>\n                            endTime <\/span>=<\/span> System.<\/span>nanoTime<\/span>();<\/span><\/span>\n<\/span>\n                            fout.<\/span>println<\/span>(i <\/span>+<\/span> <\/span>"<\/span>\\t<\/span>"<\/span> <\/span>+<\/span> ((endTime <\/span>-<\/span> startTime) <\/span>\/<\/span> <\/span>1e9<\/span>));<\/span><\/span>\n                        }<\/span><\/span>\n<\/span>\n                        System.out.<\/span>println<\/span>(<\/span>"<\/span>\\n<\/span>Data File generated and stored in file < MergePlot.dat >. Use a plotting utility"<\/span>);<\/span><\/span>\n                        <\/span>break<\/span>;<\/span><\/span>\n                    <\/span>case<\/span> <\/span>3<\/span>:<\/span><\/span>\n                        System.<\/span>exit<\/span>(<\/span>0<\/span>);<\/span><\/span>\n                }<\/span><\/span>\n            }<\/span><\/span>\n        } <\/span>catch<\/span> (IOException <\/span>e<\/span>) {<\/span><\/span>\n            System.out.<\/span>println<\/span>(<\/span>"Error: "<\/span> <\/span>+<\/span> e.<\/span>getMessage<\/span>());<\/span><\/span>\n        }<\/span><\/span>\n    }<\/span><\/span>\n}<\/span><\/span>\n<\/span><\/code><\/pre><\/div>\n\n\n\n
              Output<\/h4>\n\n\n\n
              <\/circle><\/circle><\/circle><\/g><\/svg><\/span><\/path><\/path><\/svg><\/span>
              Enter a <\/span>number<\/span> : 5<\/span>nfn<\/span>(<\/span>5<\/span>) <\/span>=<\/span> 31.MergeSort<\/span><\/span>\n2.Plot the Graph<\/span><\/span>\n3.Exit<\/span><\/span>\nEnter your choice<\/span><\/span>\n1<\/span><\/span>\n<\/span>\nEnter number <\/span>of<\/span> elements to <\/span>sort<\/span> : <\/span>4<\/span><\/span>\n<\/span>\nUnsorted Array<\/span><\/span>\n    <\/span>6356<\/span><\/span>\n     <\/span>627<\/span><\/span>\n    <\/span>4088<\/span><\/span>\n    <\/span>4843<\/span><\/span>\n<\/span>\nSorted Array<\/span><\/span>\n     <\/span>627<\/span><\/span>\n    <\/span>4088<\/span><\/span>\n    <\/span>4843<\/span><\/span>\n    <\/span>6356<\/span><\/span>\n<\/span>\n1.MergeSort<\/span><\/span>\n2.Plot the Graph<\/span><\/span>\n3.Exit<\/span><\/span>\nEnter your choice<\/span><\/span>\n2<\/span><\/span>\n<\/span>\nData File generated and stored <\/span>in<\/span> file <\/span><<\/span> MergePlot.dat <\/span>><\/span>.<\/span><\/span>\n Use a plotting utility<\/span><\/span>\n<\/span>\n1.MergeSort<\/span><\/span>\n2.Plot the Graph<\/span><\/span>\n3.Exit<\/span><\/span>\nEnter your choice<\/span><\/span>\n3<\/span><\/span>\n<\/span><\/code><\/pre><\/div>\n\n\n\n
              Plotting Script for Gnuplot<\/h3>\n\n\n\n
              We will now see how to generate a plot graph of data contained in MergePlot.dat<\/strong> and store it as an image. For that let’s write a gnuplot script file called 03MergePlot.gpl<\/strong>. The contents of which are shown below<\/p>\n\n\n\n
              <\/circle><\/circle><\/circle><\/g><\/svg><\/span><\/path><\/path><\/svg><\/span>
              # Gnuplot script file for plotting data <\/span>in<\/span> file <\/span>"MergePlot.dat"<\/span><\/span>\n# This file is called       03MergePlot.gpl<\/span><\/span>\nset terminal png font arial<\/span><\/span>\nset title <\/span>"Time Complexity for Merge Sort"<\/span><\/span>\nset autoscale<\/span><\/span>\nset xlabel <\/span>"Size of Input"<\/span><\/span>\nset ylabel <\/span>"Sorting Time (microseconds)"<\/span><\/span>\nset grid<\/span><\/span>\nset output <\/span>"MergePlot.png"<\/span><\/span>\nplot <\/span>"MergePlot.dat"<\/span> t <\/span>'Merge Sort'<\/span> <\/span>with<\/span> lines<\/span><\/span><\/code><\/pre><\/div>\n\n\n\n
              To execute the Gnuplot script you have to give the following command:<\/p>\n\n\n\n
              <\/circle><\/circle><\/circle><\/g><\/svg><\/span><\/path><\/path><\/svg><\/span>
              $<\/span> <\/span>gnuplot<\/span> <\/span>03<\/span>MergePlot.gpl<\/span><\/span><\/code><\/pre><\/div>\n\n\n\n
              You can now see that an image file by name MergePlot.png containing the graph will be created in your local folder. <\/p>\n\n\n\n
              \"\"<\/a><\/figure>\n\n\n\n
              Time Complexity Analysis of Merge Sort<\/h3>\n\n\n\n
              Worst Case – O(n*log n)<\/strong><\/p>\n\n\n\n
              Average Case – O(n*log n)<\/strong><\/strong><\/p>\n\n\n\n
              Best Case – O(n*log n)<\/strong><\/strong><\/p>\n\n\n\n
              \n\n\n\n
              Module 3<\/h2>\n\n\n\n
              Knapsack problem using Greedy method.<\/h3>\n\n\n\n
              Write & Execute C++\/Java Program to solve Knapsack problem using Greedy method.<\/p>\n\n\n\n
              C++ Code<\/h4>\n\n\n\n
              <\/circle><\/circle><\/circle><\/g><\/svg><\/span><\/path><\/path><\/svg><\/span>
              #include<\/span> <\/span><iostream><\/span><\/span>\n#include<\/span> <\/span><fstream><\/span><\/span>\n#include<\/span> <\/span><iomanip><\/span><\/span>\n#include<\/span> <\/span><vector><\/span><\/span>\n#include<\/span> <\/span><ctime><\/span><\/span>\n#include<\/span> <\/span><cstdlib><\/span><\/span>\nusing<\/span> <\/span>namespace<\/span> <\/span>std<\/span>;<\/span><\/span>\n<\/span>\n<\/span>\ntypedef<\/span> <\/span>struct<\/span>{<\/span><\/span>\n    <\/span>int<\/span> profit;<\/span><\/span>\n    <\/span>int<\/span> weight;<\/span><\/span>\n    <\/span>float<\/span> profitRatio;<\/span><\/span>\n    <\/span>float<\/span> fraction;<\/span><\/span>\n}<\/span>Item<\/span>;<\/span><\/span>\nint<\/span> <\/span>main<\/span>()<\/span><\/span>\n{<\/span><\/span>\n    vector <\/span><<\/span>Item<\/span>><\/span> itemList;<\/span><\/span>\n    <\/span>int<\/span> iNum, i, pos;<\/span><\/span>\n    <\/span>float<\/span> knCap, remCap, totProfit;<\/span><\/span>\n    Item a;<\/span><\/span>\n<\/span>\n    cout <\/span><<<\/span> <\/span>"Enter the number of items : "<\/span> ;<\/span><\/span>\n    cin <\/span>>><\/span> iNum;<\/span><\/span>\n<\/span>\n    cout <\/span><<<\/span> <\/span>"Enter Knapsack capacity : "<\/span>;<\/span><\/span>\n    cin <\/span>>><\/span> knCap;<\/span><\/span>\n<\/span>\n    <\/span>for<\/span>(i<\/span>=<\/span>0<\/span>;i<\/span><<\/span>iNum;i<\/span>++<\/span>)<\/span><\/span>\n    {<\/span><\/span>\n<\/span>\n        cout <\/span><<<\/span> <\/span>"Enter profit : "<\/span>; cin <\/span>>><\/span> a.profit;<\/span><\/span>\n        cout <\/span><<<\/span> <\/span>"Enter weight : "<\/span>; cin <\/span>>><\/span> a.weight;<\/span><\/span>\n        a.profitRatio <\/span>=<\/span> (<\/span>float<\/span>)a.profit <\/span>\/<\/span> a.weight;<\/span><\/span>\n        a.fraction <\/span>=<\/span> <\/span>0.0<\/span>f<\/span>;<\/span><\/span>\n        \/\/cout << a.profitRatio << endl;<\/span><\/span>\n        <\/span>if<\/span> (itemList.<\/span>size<\/span>() <\/span>==<\/span> <\/span>0<\/span>)<\/span><\/span>\n        {<\/span><\/span>\n            itemList.<\/span>push_back<\/span>(a);<\/span><\/span>\n        }<\/span><\/span>\n        <\/span>else<\/span><\/span>\n        {<\/span><\/span>\n            pos<\/span>=<\/span>0<\/span>;<\/span><\/span>\n            <\/span>while<\/span>(a.profitRatio <\/span><<\/span> itemList[pos].profitRatio) pos<\/span>++<\/span>;<\/span><\/span>\n            itemList.<\/span>insert<\/span>(itemList.<\/span>begin<\/span>() <\/span>+<\/span> pos,a);<\/span><\/span>\n        }<\/span><\/span>\n    }<\/span><\/span>\n<\/span>\n    remCap <\/span>=<\/span> knCap;<\/span><\/span>\n    totProfit <\/span>=<\/span> <\/span>0.0<\/span>;<\/span><\/span>\n    <\/span>for<\/span>(i<\/span>=<\/span>0<\/span>;i<\/span><<\/span>iNum;i<\/span>++<\/span>)<\/span><\/span>\n    {<\/span><\/span>\n        a <\/span>=<\/span> itemList[i];<\/span><\/span>\n        <\/span>if<\/span>(a.weight <\/span><<\/span> remCap)<\/span><\/span>\n        {<\/span><\/span>\n            itemList[i].fraction <\/span>=<\/span> <\/span>1.0<\/span>;<\/span><\/span>\n            remCap <\/span>-=<\/span> itemList[i].weight;<\/span><\/span>\n            totProfit <\/span>+=<\/span> itemList[i].profit;<\/span><\/span>\n        }<\/span><\/span>\n        <\/span>else<\/span><\/span>\n        {<\/span><\/span>\n            itemList[i].fraction <\/span>=<\/span> remCap <\/span>\/<\/span> itemList[i].weight;<\/span><\/span>\n            remCap <\/span>-=<\/span> itemList[i].weight <\/span>*<\/span> itemList[i].fraction;<\/span><\/span>\n            totProfit <\/span>+=<\/span> itemList[i].profit <\/span>*<\/span> itemList[i].fraction;<\/span><\/span>\n        }<\/span><\/span>\n        <\/span>if<\/span>(remCap <\/span>==<\/span> <\/span>0<\/span>)<\/span><\/span>\n            <\/span>break<\/span>;<\/span><\/span>\n    }<\/span><\/span>\n    cout <\/span><<<\/span> <\/span>"<\/span>\\n<\/span>KNAPSACK SOLUTION<\/span>\\n<\/span>"<\/span>;<\/span><\/span>\n    cout <\/span><<<\/span> <\/span>"Item<\/span>\\t<\/span>Weight<\/span>\\t<\/span>Profit<\/span>\\t<\/span>Fraction Chosen<\/span>\\n<\/span>"<\/span>;<\/span><\/span>\n    <\/span>for<\/span>(i<\/span>=<\/span>0<\/span>;i<\/span><<\/span>iNum;i<\/span>++<\/span>)<\/span><\/span>\n    {<\/span><\/span>\n        cout <\/span><<<\/span> i<\/span>+<\/span>1<\/span> <\/span><<<\/span> <\/span>"<\/span>\\t<\/span>"<\/span> <\/span><<<\/span> itemList[i].weight <\/span><<<\/span> <\/span>"<\/span>\\t<\/span>"<\/span> <\/span><<<\/span> itemList[i].profit <\/span><<<\/span> <\/span>"<\/span>\\t<\/span>"<\/span> <\/span><<<\/span> itemList[i].fraction <\/span><<<\/span> endl;<\/span><\/span>\n    }<\/span><\/span>\n    cout  <\/span><<<\/span> <\/span>"<\/span>\\n<\/span>Total Profit Earned : "<\/span> <\/span><<<\/span> totProfit <\/span><<<\/span> endl;<\/span><\/span>\n<\/span>\n    <\/span>return<\/span> <\/span>0<\/span>;<\/span><\/span>\n}<\/span><\/span>\n<\/span><\/code><\/pre><\/div>\n\n\n\n
              Java Code<\/h4>\n\n\n\n
              <\/circle><\/circle><\/circle><\/g><\/svg><\/span><\/path><\/path><\/svg><\/span>
              import<\/span> java.util.ArrayList;<\/span><\/span>\nimport<\/span> java.util.Comparator;<\/span><\/span>\nimport<\/span> java.util.List;<\/span><\/span>\nimport<\/span> java.util.Scanner;<\/span><\/span>\n<\/span>\nclass<\/span> <\/span>Item<\/span> {<\/span><\/span>\n    <\/span>int<\/span> profit;<\/span><\/span>\n    <\/span>int<\/span> weight;<\/span><\/span>\n    <\/span>float<\/span> profitRatio;<\/span><\/span>\n    <\/span>float<\/span> fraction;<\/span><\/span>\n}<\/span><\/span>\n<\/span>\npublic<\/span> <\/span>class<\/span> <\/span>KnapsackProblem<\/span> {<\/span><\/span>\n    <\/span>public<\/span> <\/span>static<\/span> <\/span>void<\/span> <\/span>main<\/span>(<\/span>String<\/span>[] <\/span>args<\/span>) {<\/span><\/span>\n        List<<\/span>Item<\/span>> itemList <\/span>=<\/span> <\/span>new<\/span> ArrayList<>();<\/span><\/span>\n        <\/span>int<\/span> iNum, i;<\/span><\/span>\n        <\/span>float<\/span> knCap, remCap, totProfit;<\/span><\/span>\n        Item a;<\/span><\/span>\n<\/span>\n        Scanner scanner <\/span>=<\/span> <\/span>new<\/span> <\/span>Scanner<\/span>(System.in);<\/span><\/span>\n<\/span>\n        System.out.<\/span>print<\/span>(<\/span>"Enter the number of items: "<\/span>);<\/span><\/span>\n        iNum <\/span>=<\/span> scanner.<\/span>nextInt<\/span>();<\/span><\/span>\n<\/span>\n        System.out.<\/span>print<\/span>(<\/span>"Enter Knapsack capacity: "<\/span>);<\/span><\/span>\n        knCap <\/span>=<\/span> scanner.<\/span>nextFloat<\/span>();<\/span><\/span>\n<\/span>\n        <\/span>for<\/span> (i <\/span>=<\/span> <\/span>0<\/span>; i <\/span><<\/span> iNum; i<\/span>++<\/span>) {<\/span><\/span>\n            a <\/span>=<\/span> <\/span>new<\/span> <\/span>Item<\/span>();<\/span><\/span>\n<\/span>\n            System.out.<\/span>print<\/span>(<\/span>"Enter profit: "<\/span>);<\/span><\/span>\n            a.profit <\/span>=<\/span> scanner.<\/span>nextInt<\/span>();<\/span><\/span>\n<\/span>\n            System.out.<\/span>print<\/span>(<\/span>"Enter weight: "<\/span>);<\/span><\/span>\n            a.weight <\/span>=<\/span> scanner.<\/span>nextInt<\/span>();<\/span><\/span>\n<\/span>\n            a.profitRatio <\/span>=<\/span> (<\/span>float<\/span>) a.profit <\/span>\/<\/span> a.weight;<\/span><\/span>\n            a.fraction <\/span>=<\/span> <\/span>0.0f<\/span>;<\/span><\/span>\n<\/span>\n            itemList.<\/span>add<\/span>(a);<\/span><\/span>\n        }<\/span><\/span>\n<\/span>\n        itemList.<\/span>sort<\/span>(Comparator.<\/span>comparing<\/span>((Item item) <\/span>-><\/span> item.profitRatio).<\/span>reversed<\/span>());<\/span><\/span>\n<\/span>\n        remCap <\/span>=<\/span> knCap;<\/span><\/span>\n        totProfit <\/span>=<\/span> <\/span>0.0f<\/span>;<\/span><\/span>\n<\/span>\n        <\/span>for<\/span> (i <\/span>=<\/span> <\/span>0<\/span>; i <\/span><<\/span> iNum; i<\/span>++<\/span>) {<\/span><\/span>\n            a <\/span>=<\/span> itemList.<\/span>get<\/span>(i);<\/span><\/span>\n<\/span>\n            <\/span>if<\/span> (a.weight <\/span><<\/span> remCap) {<\/span><\/span>\n                a.fraction <\/span>=<\/span> <\/span>1.0f<\/span>;<\/span><\/span>\n                remCap <\/span>-=<\/span> a.weight;<\/span><\/span>\n                totProfit <\/span>+=<\/span> a.profit;<\/span><\/span>\n            } <\/span>else<\/span> {<\/span><\/span>\n                a.fraction <\/span>=<\/span> remCap <\/span>\/<\/span> a.weight;<\/span><\/span>\n                remCap <\/span>=<\/span> <\/span>0<\/span>;<\/span><\/span>\n                totProfit <\/span>+=<\/span> a.profit <\/span>*<\/span> a.fraction;<\/span><\/span>\n                <\/span>break<\/span>;<\/span><\/span>\n            }<\/span><\/span>\n        }<\/span><\/span>\n<\/span>\n        System.out.<\/span>println<\/span>(<\/span>"<\/span>\\n<\/span>KNAPSACK SOLUTION"<\/span>);<\/span><\/span>\n        System.out.<\/span>println<\/span>(<\/span>"Item<\/span>\\t<\/span>Weight<\/span>\\t<\/span>Profit<\/span>\\t<\/span>Fraction Chosen"<\/span>);<\/span><\/span>\n<\/span>\n        <\/span>for<\/span> (i <\/span>=<\/span> <\/span>0<\/span>; i <\/span><<\/span> iNum; i<\/span>++<\/span>) {<\/span><\/span>\n            a <\/span>=<\/span> itemList.<\/span>get<\/span>(i);<\/span><\/span>\n            System.out.<\/span>printf<\/span>(<\/span>"%d<\/span>\\t<\/span>%d<\/span>\\t<\/span>%d<\/span>\\t<\/span>%.2f<\/span>\\n<\/span>"<\/span>, i <\/span>+<\/span> <\/span>1<\/span>, a.weight, a.profit, a.fraction);<\/span><\/span>\n        }<\/span><\/span>\n<\/span>\n        System.out.<\/span>println<\/span>(<\/span>"<\/span>\\n<\/span>Total Profit Earned: "<\/span> <\/span>+<\/span> totProfit);<\/span><\/span>\n<\/span>\n        scanner.<\/span>close<\/span>();<\/span><\/span>\n    }<\/span><\/span>\n}<\/span><\/span>\n<\/span><\/code><\/pre><\/div>\n\n\n\n
              Input sample<\/h4>\n\n\n\n
              Lets consider this sample input for the 0\/1 Knapsack Problem.<\/p>\n\n\n\n
              Knapsack Capacity : 5<\/strong><\/p>\n\n\n\n
              Item<\/strong><\/td>Weight<\/strong><\/td>Profit<\/strong><\/td><\/tr>
              1<\/td>5<\/td>30<\/td><\/tr>
              2<\/td>10<\/td>40<\/td><\/tr>
              3<\/td>15<\/td>45<\/td><\/tr>
              4<\/td>22<\/td>77<\/td><\/tr>
              5<\/td>25<\/td>90<\/td><\/tr><\/tbody><\/table><\/figure>\n\n\n\n
              Output<\/h4>\n\n\n\n
              <\/circle><\/circle><\/circle><\/g><\/svg><\/span><\/path><\/path><\/svg><\/span>
              Enter the number <\/span>of<\/span> <\/span>items<\/span> : <\/span>5<\/span><\/span>\nEnter Knapsack <\/span>capacity<\/span> : <\/span>60<\/span><\/span>\nEnter <\/span>profit<\/span> : <\/span>30<\/span><\/span>\nEnter <\/span>weight<\/span> : <\/span>5<\/span><\/span>\nEnter <\/span>profit<\/span> : <\/span>40<\/span><\/span>\nEnter <\/span>weight<\/span> : <\/span>10<\/span><\/span>\nEnter <\/span>profit<\/span> : <\/span>45<\/span><\/span>\nEnter <\/span>weight<\/span> : <\/span>15<\/span><\/span>\nEnter <\/span>profit<\/span> : <\/span>77<\/span><\/span>\nEnter <\/span>weight<\/span> : <\/span>22<\/span><\/span>\nEnter <\/span>profit<\/span> : <\/span>90<\/span><\/span>\nEnter <\/span>weight<\/span> : <\/span>25<\/span><\/span>\n<\/span>\nKNAPSACK<\/span> <\/span>SOLUTION<\/span><\/span>\nItem\tWeight\tProfit\tFraction Chosen<\/span><\/span>\n  <\/span>1<\/span>\t      <\/span>5<\/span>\t      <\/span>30<\/span>\t    <\/span>1.00<\/span><\/span>\n  <\/span>2<\/span>\t      <\/span>10<\/span>\t  <\/span>40<\/span>\t    <\/span>1.00<\/span><\/span>\n  <\/span>3<\/span>\t      <\/span>25<\/span>\t  <\/span>90<\/span>\t    <\/span>1.00<\/span><\/span>\n  <\/span>4<\/span>\t      <\/span>22<\/span>\t  <\/span>77<\/span>\t    <\/span>0.91<\/span><\/span>\n  <\/span>5<\/span>\t      <\/span>15<\/span>\t  <\/span>45<\/span>\t    <\/span>0.00<\/span><\/span>\n<\/span>\nTotal Profit <\/span>Earned<\/span>: <\/span>230.0<\/span><\/span>\n<\/span>\n<\/span><\/code><\/pre><\/div>\n\n\n\n
              \n\n\n\n
              Dijkstra’s Algorithm<\/h3>\n\n\n\n
              Write & Execute C++\/Java Program to find shortest paths to other vertices from a given vertex in a weighted connected graph, using Dijkstra’s algorithm.<\/p>\n\n\n\n
              C++ Code<\/h4>\n\n\n\n
              <\/circle><\/circle><\/circle><\/g><\/svg><\/span><\/path><\/path><\/svg><\/span>
              \/******************************************************************************<\/span><\/span>\n*File\t\t: 05Dijkstra.cpp<\/span><\/span>\n*Description: Program to find shortest paths to other vertices using <\/span><\/span>\n*\t\t\t\tDijkstra's algorithm.<\/span><\/span>\n*Author\t\t: Prabodh C P<\/span><\/span>\n*Compiler\t: g++ compiler 7.5.0, Ubuntu 18.04<\/span><\/span>\n*Date\t\t: 31 Mar 2020<\/span><\/span>\n******************************************************************************\/<\/span><\/span>\n#include<\/span> <\/span><iostream><\/span><\/span>\n#include<\/span> <\/span><cstdio><\/span><\/span>\nusing<\/span> <\/span>namespace<\/span> <\/span>std<\/span>;<\/span><\/span>\nconst<\/span> <\/span>int<\/span> MAXNODES <\/span>=<\/span> <\/span>10<\/span>,INF <\/span>=<\/span> <\/span>9999<\/span>;<\/span><\/span>\nvoid<\/span> <\/span>fnDijkstra<\/span>(<\/span>int<\/span> [][MAXNODES], <\/span>int<\/span> [], <\/span>int<\/span> [], <\/span>int<\/span>[], <\/span>int<\/span>, <\/span>int<\/span>, <\/span>int<\/span>);<\/span><\/span>\n\/******************************************************************************<\/span><\/span>\n*Function\t: main<\/span><\/span>\n*Input parameters: no parameters<\/span><\/span>\n*RETURNS\t: 0 on success<\/span><\/span>\n******************************************************************************\/<\/span><\/span>\nint<\/span> <\/span>main<\/span>(<\/span>void<\/span>)<\/span><\/span>\n{<\/span><\/span>\n\t<\/span>int<\/span> n,cost[MAXNODES][MAXNODES],dist[MAXNODES],visited[MAXNODES],path[MAXNODES],i,j,source,dest;<\/span><\/span>\n\tcout <\/span><<<\/span> <\/span>"<\/span>\\n<\/span>Enter the number of nodes<\/span>\\n<\/span>"<\/span>;<\/span><\/span>\n\tcin <\/span>>><\/span> n;<\/span><\/span>\n\tcout <\/span><<<\/span> <\/span>"Enter the Cost Matrix<\/span>\\n<\/span>"<\/span> <\/span><<<\/span> endl;<\/span><\/span>\n\t<\/span>for<\/span> (i<\/span>=<\/span>0<\/span>;i<\/span><<\/span>n;i<\/span>++<\/span>)<\/span><\/span>\n\t\t<\/span>for<\/span> (j<\/span>=<\/span>0<\/span>;j<\/span><<\/span>n;j<\/span>++<\/span>)<\/span><\/span>\n\t\t\tcin <\/span>>><\/span> cost[i][j];<\/span><\/span>\n\tcout <\/span><<<\/span> <\/span>"Enter the Source vertex"<\/span> <\/span><<<\/span> endl;<\/span><\/span>\n\tcin <\/span>>><\/span> source;<\/span><\/span>\n\t<\/span><\/span>\n\tcout <\/span><<<\/span> <\/span>"<\/span>\\n<\/span>\/\/For Source Vertex : "<\/span> <\/span><<<\/span> source <\/span><<<\/span> <\/span>" shortest path to other vertices\/\/"<\/span><<<\/span> endl;<\/span><\/span>\n\t<\/span>for<\/span> (dest<\/span>=<\/span>0<\/span>; dest <\/span><<\/span> n; dest<\/span>++<\/span>)<\/span><\/span>\n\t{<\/span><\/span>\n\t\t<\/span>fnDijkstra<\/span>(cost,dist,path,visited,source,dest,n);<\/span><\/span>\n\t\t<\/span>if<\/span> (dist[dest] <\/span>==<\/span> INF)<\/span><\/span>\n\t\tcout <\/span><<<\/span> dest <\/span><<<\/span> <\/span>" not reachable"<\/span> <\/span><<<\/span> endl;<\/span><\/span>\n\t\t<\/span>else<\/span><\/span>\n\t\t{<\/span><\/span>\n\t\t\tcout <\/span><<<\/span> endl;<\/span><\/span>\n\t\t\ti <\/span>=<\/span> dest;<\/span><\/span>\n\t\t\t<\/span>do<\/span><\/span>\n\t\t\t{<\/span><\/span>\n\t\t\t\tcout <\/span><<<\/span> i <\/span><<<\/span> <\/span>"<--"<\/span>;<\/span><\/span>\n\t\t\t\ti <\/span>=<\/span> path[i];<\/span><\/span>\n\t\t\t}<\/span>while<\/span> (i<\/span>!=<\/span> source);<\/span><\/span>\n\t\t\tcout <\/span><<<\/span> i <\/span><<<\/span> <\/span>" = "<\/span> <\/span><<<\/span> dist[dest] <\/span><<<\/span> endl;<\/span><\/span>\n\t\t}<\/span><\/span>\n\t}<\/span><\/span>\n\t<\/span><\/span>\n\t<\/span>return<\/span> <\/span>0<\/span>;<\/span><\/span>\n}<\/span><\/span>\n<\/span>\n\/******************************************************************************<\/span><\/span>\n*Function\t: fnDijkstra<\/span><\/span>\n*Description\t: Function to find shortest paths to other vertices<\/span><\/span>\n* using Dijkstra's algorithm.<\/span><\/span>\n*Input parameters:<\/span><\/span>\n*\tint c[][] - cost adjacency matrix of the graph<\/span><\/span>\n*\tint d[] - distance vector<\/span><\/span>\n*\tint p[] - path vector<\/span><\/span>\n*\tint s[] - vector to store visited information<\/span><\/span>\n*\tint so\t- source vertex<\/span><\/span>\n*\tint de\t- destination vertex<\/span><\/span>\n*\tint n - no of vertices in the graph<\/span><\/span>\n*RETURNS\t: no value<\/span><\/span>\n******************************************************************************\/<\/span><\/span>\nvoid<\/span> <\/span>fnDijkstra<\/span>(<\/span>int<\/span> <\/span>c<\/span>[MAXNODES][MAXNODES], <\/span>int<\/span> <\/span>d<\/span>[MAXNODES], <\/span>int<\/span> <\/span>p<\/span>[MAXNODES],<\/span><\/span>\nint<\/span> <\/span>s<\/span>[MAXNODES], <\/span>int<\/span> <\/span>so<\/span>, <\/span>int<\/span> <\/span>de<\/span>, <\/span>int<\/span> <\/span>n<\/span>)<\/span><\/span>\n{<\/span><\/span>\n\t<\/span>int<\/span> i,j,a,b,min;<\/span><\/span>\n\t<\/span>for<\/span> (i<\/span>=<\/span>0<\/span>;i<\/span><<\/span>n;i<\/span>++<\/span>)<\/span><\/span>\n\t{<\/span><\/span>\n\t\ts[i] <\/span>=<\/span> <\/span>0<\/span>;<\/span><\/span>\n\t\td[i] <\/span>=<\/span> c[so][i];<\/span><\/span>\n\t\tp[i] <\/span>=<\/span> so;<\/span><\/span>\n\t}<\/span><\/span>\n\ts[so] <\/span>=<\/span> <\/span>1<\/span>;<\/span><\/span>\n\t<\/span>for<\/span> (i<\/span>=<\/span>1<\/span>;i<\/span><<\/span>n;i<\/span>++<\/span>)<\/span><\/span>\n\t{<\/span><\/span>\n\t\tmin <\/span>=<\/span> INF;<\/span><\/span>\n\t\ta <\/span>=<\/span> <\/span>-<\/span>1<\/span>;<\/span><\/span>\n\t\t<\/span>for<\/span> (j<\/span>=<\/span>0<\/span>;j<\/span><<\/span>n;j<\/span>++<\/span>)<\/span><\/span>\n\t\t{<\/span><\/span>\n\t\t\t<\/span>if<\/span> (s[j] <\/span>==<\/span> <\/span>0<\/span>)<\/span><\/span>\n\t\t\t{<\/span><\/span>\n\t\t\t\t<\/span>if<\/span> (d[j] <\/span><<\/span> min)<\/span><\/span>\n\t\t\t\t{<\/span><\/span>\n\t\t\t\t\tmin <\/span>=<\/span> d[j];<\/span><\/span>\n\t\t\t\t\ta <\/span>=<\/span> j;<\/span><\/span>\n\t\t\t\t}<\/span><\/span>\n\t\t\t}<\/span><\/span>\n\t\t}<\/span><\/span>\n\t\t<\/span>if<\/span> (a <\/span>==<\/span> <\/span>-<\/span>1<\/span>) <\/span>return<\/span>;<\/span><\/span>\n\t\ts[a] <\/span>=<\/span> <\/span>1<\/span>;<\/span><\/span>\n\t\t<\/span>if<\/span> (a <\/span>==<\/span> de) <\/span>return<\/span>;<\/span><\/span>\n<\/span>\n\t\t<\/span>for<\/span> (b<\/span>=<\/span>0<\/span>;b<\/span><<\/span>n;b<\/span>++<\/span>)<\/span><\/span>\n\t\t{<\/span><\/span>\n\t\t\t<\/span>if<\/span> (s[b] <\/span>==<\/span> <\/span>0<\/span>)<\/span><\/span>\n\t\t\t{<\/span><\/span>\n\t\t\t\t<\/span>if<\/span> (d[a] <\/span>+<\/span> c[a][b] <\/span><<\/span> d[b])<\/span><\/span>\n\t\t\t\t{<\/span><\/span>\n\t\t\t\t\td[b] <\/span>=<\/span> d[a] <\/span>+<\/span> c[a][b];<\/span><\/span>\n\t\t\t\t\tp[b] <\/span>=<\/span> a;<\/span><\/span>\n\t\t\t\t}<\/span><\/span>\n\t\t\t}<\/span><\/span>\n\t\t}<\/span><\/span>\n\t}<\/span><\/span>\n}<\/span><\/span><\/code><\/pre><\/div>\n\n\n\n
              Java Code<\/h4>\n\n\n\n
              <\/circle><\/circle><\/circle><\/g><\/svg><\/span><\/path><\/path><\/svg><\/span>
              import<\/span> java.util.Scanner;<\/span><\/span>\n<\/span>\npublic<\/span> <\/span>class<\/span> <\/span>DijkstraAlgorithm<\/span> {<\/span><\/span>\n    <\/span>private<\/span> <\/span>static<\/span> <\/span>final<\/span> <\/span>int<\/span> MAXNODES <\/span>=<\/span> <\/span>10<\/span>;<\/span><\/span>\n    <\/span>private<\/span> <\/span>static<\/span> <\/span>final<\/span> <\/span>int<\/span> INF <\/span>=<\/span> <\/span>9999<\/span>;<\/span><\/span>\n<\/span>\n    <\/span>public<\/span> <\/span>static<\/span> <\/span>void<\/span> <\/span>main<\/span>(<\/span>String<\/span>[] <\/span>args<\/span>) {<\/span><\/span>\n        <\/span>int<\/span> n, cost[][] <\/span>=<\/span> <\/span>new<\/span> <\/span>int<\/span>[MAXNODES][MAXNODES], dist[] <\/span>=<\/span> <\/span>new<\/span> <\/span>int<\/span>[MAXNODES], visited[] <\/span>=<\/span> <\/span>new<\/span> <\/span>int<\/span>[MAXNODES], path[] <\/span>=<\/span> <\/span>new<\/span> <\/span>int<\/span>[MAXNODES], i, j, source, dest;<\/span><\/span>\n        Scanner scanner <\/span>=<\/span> <\/span>new<\/span> <\/span>Scanner<\/span>(System.in);<\/span><\/span>\n<\/span>\n        System.out.<\/span>print<\/span>(<\/span>"Enter the number of nodes: "<\/span>);<\/span><\/span>\n        n <\/span>=<\/span> scanner.<\/span>nextInt<\/span>();<\/span><\/span>\n<\/span>\n        System.out.<\/span>println<\/span>(<\/span>"Enter the Cost Matrix:"<\/span>);<\/span><\/span>\n        <\/span>for<\/span> (i <\/span>=<\/span> <\/span>0<\/span>; i <\/span><<\/span> n; i<\/span>++<\/span>) {<\/span><\/span>\n            <\/span>for<\/span> (j <\/span>=<\/span> <\/span>0<\/span>; j <\/span><<\/span> n; j<\/span>++<\/span>) {<\/span><\/span>\n                cost[i][j] <\/span>=<\/span> scanner.<\/span>nextInt<\/span>();<\/span><\/span>\n            }<\/span><\/span>\n        }<\/span><\/span>\n<\/span>\n        System.out.<\/span>print<\/span>(<\/span>"Enter the Source vertex: "<\/span>);<\/span><\/span>\n        source <\/span>=<\/span> scanner.<\/span>nextInt<\/span>();<\/span><\/span>\n<\/span>\n        System.out.<\/span>println<\/span>(<\/span>"<\/span>\\n<\/span>Shortest paths from Source Vertex "<\/span> <\/span>+<\/span> source <\/span>+<\/span> <\/span>" to other vertices:"<\/span>);<\/span><\/span>\n<\/span>\n        <\/span>for<\/span> (dest <\/span>=<\/span> <\/span>0<\/span>; dest <\/span><<\/span> n; dest<\/span>++<\/span>) {<\/span><\/span>\n            <\/span>fnDijkstra<\/span>(cost, dist, path, visited, source, dest, n);<\/span><\/span>\n<\/span>\n            <\/span>if<\/span> (dist[dest] <\/span>==<\/span> INF) {<\/span><\/span>\n                System.out.<\/span>println<\/span>(dest <\/span>+<\/span> <\/span>" is not reachable"<\/span>);<\/span><\/span>\n            } <\/span>else<\/span> {<\/span><\/span>\n                System.out.<\/span>println<\/span>();<\/span><\/span>\n                i <\/span>=<\/span> dest;<\/span><\/span>\n<\/span>\n                <\/span>do<\/span> {<\/span><\/span>\n                    System.out.<\/span>print<\/span>(i <\/span>+<\/span> <\/span>" <-- "<\/span>);<\/span><\/span>\n                    i <\/span>=<\/span> path[i];<\/span><\/span>\n                } <\/span>while<\/span> (i <\/span>!=<\/span> source);<\/span><\/span>\n<\/span>\n                System.out.<\/span>println<\/span>(i <\/span>+<\/span> <\/span>" = "<\/span> <\/span>+<\/span> dist[dest]);<\/span><\/span>\n            }<\/span><\/span>\n        }<\/span><\/span>\n    }<\/span><\/span>\n<\/span>\n    <\/span>private<\/span> <\/span>static<\/span> <\/span>void<\/span> <\/span>fnDijkstra<\/span>(<\/span>int<\/span>[][] <\/span>cost<\/span>, <\/span>int<\/span>[] <\/span>dist<\/span>, <\/span>int<\/span>[] <\/span>path<\/span>, <\/span>int<\/span>[] <\/span>visited<\/span>, <\/span>int<\/span> <\/span>source<\/span>, <\/span>int<\/span> <\/span>dest<\/span>, <\/span>int<\/span> <\/span>n<\/span>) {<\/span><\/span>\n        <\/span>int<\/span> i, j, a, b, min;<\/span><\/span>\n<\/span>\n        <\/span>for<\/span> (i <\/span>=<\/span> <\/span>0<\/span>; i <\/span><<\/span> n; i<\/span>++<\/span>) {<\/span><\/span>\n            visited[i] <\/span>=<\/span> <\/span>0<\/span>;<\/span><\/span>\n            dist[i] <\/span>=<\/span> cost[source][i];<\/span><\/span>\n            path[i] <\/span>=<\/span> source;<\/span><\/span>\n        }<\/span><\/span>\n<\/span>\n        visited[source] <\/span>=<\/span> <\/span>1<\/span>;<\/span><\/span>\n<\/span>\n        <\/span>for<\/span> (i <\/span>=<\/span> <\/span>1<\/span>; i <\/span><<\/span> n; i<\/span>++<\/span>) {<\/span><\/span>\n            min <\/span>=<\/span> INF;<\/span><\/span>\n            a <\/span>=<\/span> <\/span>-<\/span>1<\/span>;<\/span><\/span>\n<\/span>\n            <\/span>for<\/span> (j <\/span>=<\/span> <\/span>0<\/span>; j <\/span><<\/span> n; j<\/span>++<\/span>) {<\/span><\/span>\n                <\/span>if<\/span> (visited[j] <\/span>==<\/span> <\/span>0<\/span> <\/span>&&<\/span> dist[j] <\/span><<\/span> min) {<\/span><\/span>\n                    min <\/span>=<\/span> dist[j];<\/span><\/span>\n                    a <\/span>=<\/span> j;<\/span><\/span>\n                }<\/span><\/span>\n            }<\/span><\/span>\n<\/span>\n            <\/span>if<\/span> (a <\/span>==<\/span> <\/span>-<\/span>1<\/span>) {<\/span><\/span>\n                <\/span>return<\/span>;<\/span><\/span>\n            }<\/span><\/span>\n<\/span>\n            visited[a] <\/span>=<\/span> <\/span>1<\/span>;<\/span><\/span>\n<\/span>\n            <\/span>if<\/span> (a <\/span>==<\/span> dest) {<\/span><\/span>\n                <\/span>return<\/span>;<\/span><\/span>\n            }<\/span><\/span>\n<\/span>\n            <\/span>for<\/span> (b <\/span>=<\/span> <\/span>0<\/span>; b <\/span><<\/span> n; b<\/span>++<\/span>) {<\/span><\/span>\n                <\/span>if<\/span> (visited[b] <\/span>==<\/span> <\/span>0<\/span> <\/span>&&<\/span> dist[a] <\/span>+<\/span> cost[a][b] <\/span><<\/span> dist[b]) {<\/span><\/span>\n                    dist[b] <\/span>=<\/span> dist[a] <\/span>+<\/span> cost[a][b];<\/span><\/span>\n                    path[b] <\/span>=<\/span> a;<\/span><\/span>\n                }<\/span><\/span>\n            }<\/span><\/span>\n        }<\/span><\/span>\n    }<\/span><\/span>\n}<\/span><\/span>\n<\/span><\/code><\/pre><\/div>\n\n\n\n
              Input Graph<\/h4>\n\n\n\n
              For this program lets consider the following graph<\/p>\n\n\n\n
              \"\"<\/a><\/figure>\n\n\n\n
              Output:<\/h4>\n\n\n\n
              <\/circle><\/circle><\/circle><\/g><\/svg><\/span><\/path><\/path><\/svg><\/span>
              Enter the number <\/span>of<\/span> nodes<\/span><\/span>\n6<\/span><\/span>\nEnter the Cost Matrix<\/span><\/span>\n<\/span>\n0<\/span>\t<\/span>4<\/span>\t<\/span>4<\/span>\t<\/span>9999<\/span>\t<\/span>9999<\/span>\t<\/span>9999<\/span><\/span>\n4<\/span>\t<\/span>0<\/span>\t<\/span>2<\/span>\t<\/span>9999<\/span>\t<\/span>9999<\/span>\t<\/span>9999<\/span><\/span>\n4<\/span>\t<\/span>2<\/span>\t<\/span>0<\/span>\t<\/span>3<\/span>\t<\/span>1<\/span>\t<\/span>6<\/span><\/span>\n9999<\/span>\t<\/span>9999<\/span>\t<\/span>3<\/span>\t<\/span>0<\/span>\t<\/span>9999<\/span>\t<\/span>2<\/span><\/span>\n9999<\/span>\t<\/span>9999<\/span>\t<\/span>1<\/span>\t<\/span>9999<\/span>\t<\/span>0<\/span>\t<\/span>3<\/span><\/span>\n9999<\/span>\t<\/span>9999<\/span>\t<\/span>6<\/span>\t<\/span>2<\/span>\t<\/span>3<\/span>\t<\/span>0<\/span><\/span>\nEnter the Source vertex<\/span><\/span>\n0<\/span><\/span>\n<\/span>\n\/\/For Source Vertex : 0 shortest path to other vertices\/\/<\/span><\/span>\n<\/span>\n0<\/span><--<\/span>0<\/span> <\/span>=<\/span> <\/span>0<\/span><\/span>\n<\/span>\n1<\/span><--<\/span>0<\/span> <\/span>=<\/span> <\/span>4<\/span><\/span>\n<\/span>\n2<\/span><--<\/span>0<\/span> <\/span>=<\/span> <\/span>4<\/span><\/span>\n<\/span>\n3<\/span><--<\/span>2<\/span><--<\/span>0<\/span> <\/span>=<\/span> <\/span>7<\/span><\/span>\n<\/span>\n4<\/span><--<\/span>2<\/span><--<\/span>0<\/span> <\/span>=<\/span> <\/span>5<\/span><\/span>\n<\/span>\n5<\/span><--<\/span>4<\/span><--<\/span>2<\/span><--<\/span>0<\/span> <\/span>=<\/span> <\/span>8<\/span><\/span><\/code><\/pre><\/div>\n\n\n\n
              \n\n\n\n
              Kruskal’s Algorithm<\/h3>\n\n\n\n
              Write & Execute C++\/Java Program to find Minimum Cost Spanning Tree of a given connected undirected graph using Kruskal’s algorithm. Use Union-Find algorithms in your program.<\/p>\n\n\n\n
              C++ Code<\/h4>\n\n\n\n
              <\/circle><\/circle><\/circle><\/g><\/svg><\/span><\/path><\/path><\/svg><\/span>
              \/******************************************************************************<\/span><\/span>\n*File\t: 06Kruskal.cpp<\/span><\/span>\n*Description\t: Program to find Minimum Cost Spanning Tree of a given<\/span><\/span>\n*\t\t\tundirected graph using Kruskal's algorithm.<\/span><\/span>\n*Author\t\t: Prabodh C P<\/span><\/span>\n*Compiler\t: g++ compiler 7.5.0, Ubuntu 18.04<\/span><\/span>\n*Date\t\t: 31 Mar 2020<\/span><\/span>\n******************************************************************************\/<\/span><\/span>\n#include<\/span> <\/span><iostream><\/span><\/span>\nusing<\/span> <\/span>namespace<\/span> <\/span>std<\/span>;<\/span><\/span>\nconst<\/span> <\/span>int<\/span> MAXNODES <\/span>=<\/span> <\/span>10<\/span>;<\/span><\/span>\nconst<\/span> <\/span>int<\/span> INF <\/span>=<\/span> <\/span>9999<\/span>;<\/span><\/span>\n\/\/ Structure to represent an edge<\/span><\/span>\nstruct<\/span> <\/span>edge<\/span><\/span>\n{<\/span><\/span>\n\t<\/span>int<\/span> u, v, cost;<\/span><\/span>\n};<\/span><\/span>\nint<\/span> <\/span>fnFindParent<\/span>(<\/span>int<\/span> <\/span>v<\/span>, <\/span>int<\/span> <\/span>parent<\/span>[]);<\/span><\/span>\nvoid<\/span> <\/span>fnUnion_ij<\/span>(<\/span>int<\/span> <\/span>i<\/span>, <\/span>int<\/span> <\/span>j<\/span>, <\/span>int<\/span> <\/span>parent<\/span>[]);<\/span><\/span>\nvoid<\/span> <\/span>fnInputGraph<\/span>(<\/span>int<\/span> <\/span>m<\/span>, <\/span>edge<\/span> <\/span>e<\/span>[]);<\/span><\/span>\nint<\/span> <\/span>fnGetMinEdge<\/span>(<\/span>edge<\/span> <\/span>e<\/span>[], <\/span>int<\/span> <\/span>n<\/span>);<\/span><\/span>\nvoid<\/span> <\/span>fnKruskal<\/span>(<\/span>int<\/span> <\/span>n<\/span>, <\/span>edge<\/span> <\/span>e<\/span>[], <\/span>int<\/span> <\/span>m<\/span>);<\/span><\/span>\n\/******************************************************************************<\/span><\/span>\n*Function\t: main<\/span><\/span>\n*Input parameters:<\/span><\/span>\n*\tint argc - no of commamd line arguments<\/span><\/span>\n*<\/span><\/span>\nchar **argv - vector to store command line argumennts<\/span><\/span>\n*RETURNS\t:\t0 on success<\/span><\/span>\n******************************************************************************\/<\/span><\/span>\nint<\/span> <\/span>main<\/span>( <\/span>int<\/span> <\/span>argc<\/span>, <\/span>char<\/span> <\/span>**<\/span>argv<\/span>)<\/span><\/span>\n{<\/span><\/span>\n\t<\/span>int<\/span> n <\/span>=<\/span> <\/span>6<\/span>, m <\/span>=<\/span> <\/span>20<\/span>;<\/span><\/span>\n\tedge e[<\/span>2<\/span>*<\/span>MAXNODES] <\/span>=<\/span> {{<\/span>0<\/span>,<\/span>1<\/span>,<\/span>6<\/span>},{<\/span>1<\/span>,<\/span>4<\/span>,<\/span>4<\/span>},{<\/span>4<\/span>,<\/span>5<\/span>,<\/span>6<\/span>},{<\/span>5<\/span>,<\/span>3<\/span>,<\/span>2<\/span>},{<\/span>3<\/span>,<\/span>0<\/span>,<\/span>5<\/span>},{<\/span>0<\/span>,<\/span>2<\/span>,<\/span>1<\/span>},<\/span><\/span>\n\t{<\/span>1<\/span>,<\/span>2<\/span>,<\/span>5<\/span>},{<\/span>3<\/span>,<\/span>2<\/span>,<\/span>2<\/span>},{<\/span>4<\/span>,<\/span>2<\/span>,<\/span>6<\/span>},{<\/span>5<\/span>,<\/span>2<\/span>,<\/span>3<\/span>} };<\/span><\/span>\n\tcout <\/span><<<\/span> <\/span>"Enter the number of nodes : "<\/span>;<\/span><\/span>\n\tcin <\/span>>><\/span> n;<\/span><\/span>\n\tcout <\/span><<<\/span> <\/span>"Enter the number of edges : "<\/span>;<\/span><\/span>\n\tcin <\/span>>><\/span> m;<\/span><\/span>\n\t<\/span>fnInputGraph<\/span>(m, e);<\/span><\/span>\n\t<\/span>fnKruskal<\/span>(n, e, m);<\/span><\/span>\n\t<\/span>return<\/span> <\/span>0<\/span>;<\/span><\/span>\n}<\/span><\/span>\n\/******************************************************************************<\/span><\/span>\n*Function\t: fnFindParent<\/span><\/span>\n*Description\t: Function to find parent of a given vertex<\/span><\/span>\n*Input parameters:<\/span><\/span>\n*\tint v - vertex for whom parent has to be found<\/span><\/span>\n*\tint parent[] - parent vector<\/span><\/span>\n*RETURNS\t: parent vertex<\/span><\/span>\n******************************************************************************\/<\/span><\/span>\nint<\/span> <\/span>fnFindParent<\/span>(<\/span>int<\/span> <\/span>v<\/span>, <\/span>int<\/span> <\/span>parent<\/span>[])<\/span><\/span>\n{<\/span><\/span>\n\t<\/span>while<\/span> (parent[v] <\/span>!=<\/span> v)<\/span><\/span>\n\t\tv <\/span>=<\/span> parent[v];<\/span><\/span>\n\t<\/span>return<\/span> v;<\/span><\/span>\n}<\/span><\/span>\n<\/span>\n\/******************************************************************************<\/span><\/span>\n*Function\t: fnUnion_ij<\/span><\/span>\n*Description\t: Function to merge two trees<\/span><\/span>\n*Input parameters:<\/span><\/span>\n*\tint i, j - vertices to be merged<\/span><\/span>\n*\tint parent[] - parent vector<\/span><\/span>\n*RETURNS\t: no value<\/span><\/span>\n******************************************************************************\/<\/span><\/span>\nvoid<\/span> <\/span>fnUnion_ij<\/span>(<\/span>int<\/span> <\/span>i<\/span>, <\/span>int<\/span> <\/span>j<\/span>, <\/span>int<\/span> <\/span>parent<\/span>[])<\/span><\/span>\n{<\/span><\/span>\n\t<\/span>if<\/span>(i <\/span><<\/span> j)<\/span><\/span>\n\t\tparent[j] <\/span>=<\/span> i;<\/span><\/span>\n\t<\/span>else<\/span><\/span>\n\t\tparent[i] <\/span>=<\/span> j;<\/span><\/span>\n}<\/span><\/span>\n<\/span>\n\/******************************************************************************<\/span><\/span>\n*Function\t: fnInputGraph<\/span><\/span>\n*Description\t: Function to read a graph<\/span><\/span>\n*Input parameters:<\/span><\/span>\n*\tint m - no of edges in the graph<\/span><\/span>\n*\tedge e[] - set of edges in the graph<\/span><\/span>\n*RETURNS\t: no value<\/span><\/span>\n******************************************************************************\/<\/span><\/span>\nvoid<\/span> <\/span>fnInputGraph<\/span>(<\/span>int<\/span> <\/span>m<\/span>, <\/span>edge<\/span> <\/span>e<\/span>[])<\/span><\/span>\n{<\/span><\/span>\n\t<\/span>int<\/span> i, j, k, cost;<\/span><\/span>\n\t<\/span>for<\/span>(k<\/span>=<\/span>0<\/span>; k<\/span><<\/span>m; k<\/span>++<\/span>)<\/span><\/span>\n\t{<\/span><\/span>\n\t\tcout <\/span><<<\/span> <\/span>"Enter edge and cost in the form u, v, w : <\/span>\\n<\/span>"<\/span>;<\/span><\/span>\n\t\tcin <\/span>>><\/span> i <\/span>>><\/span> j <\/span>>><\/span> cost;<\/span><\/span>\n\t}<\/span><\/span>\n\te[k].u <\/span>=<\/span> i;<\/span><\/span>\n\te[k].v <\/span>=<\/span> j;<\/span><\/span>\n\te[k].cost <\/span>=<\/span> cost;<\/span><\/span>\n}<\/span><\/span>\n<\/span>\n\/******************************************************************************<\/span><\/span>\n*Function\t: fnGetMinEdge<\/span><\/span>\n*Description\t: Function to find the least cost edge in the edge set<\/span><\/span>\n*Input parameters:<\/span><\/span>\n*\tedge e[] - set of edges in the graph<\/span><\/span>\n*\tint n - no of vertices in the graph<\/span><\/span>\n*RETURNS\t: index of least cost edge in the edge set<\/span><\/span>\n******************************************************************************\/<\/span><\/span>\nint<\/span> <\/span>fnGetMinEdge<\/span>(<\/span>edge<\/span> <\/span>e<\/span>[], <\/span>int<\/span> <\/span>n<\/span>)<\/span><\/span>\n{<\/span><\/span>\n\t<\/span>int<\/span> i, small, pos;<\/span><\/span>\n\tsmall <\/span>=<\/span> INF;<\/span><\/span>\n\tpos <\/span>=<\/span> <\/span>-<\/span>1<\/span>;<\/span><\/span>\n\t<\/span>for<\/span>(i<\/span>=<\/span>0<\/span>; i<\/span><<\/span>n; i<\/span>++<\/span>)<\/span><\/span>\n\t{<\/span><\/span>\n\t\t<\/span>if<\/span>(e[i].cost <\/span><<\/span> small)<\/span><\/span>\n\t\t{<\/span><\/span>\n\t\t\tsmall <\/span>=<\/span> e[i].cost;<\/span><\/span>\n\t\t\tpos <\/span>=<\/span> i;<\/span><\/span>\n\t\t}<\/span><\/span>\n\t}<\/span><\/span>\n\t<\/span>return<\/span> pos;<\/span><\/span>\n}<\/span><\/span>\n<\/span>\n\/******************************************************************************<\/span><\/span>\n*Function\t: fnKruskal<\/span><\/span>\n*Description\t: Function to find MST of a graph<\/span><\/span>\n*Input parameters:<\/span><\/span>\n*\tint n - no of vertices in the graph<\/span><\/span>\n*\tint m - no of edges in the graph<\/span><\/span>\n*\tedge e[] - set of edges in the graph<\/span><\/span>\n*RETURNS\t: no value<\/span><\/span>\n******************************************************************************\/<\/span><\/span>\n<\/span>\nvoid<\/span> <\/span>fnKruskal<\/span>(<\/span>int<\/span> <\/span>n<\/span>, <\/span>edge<\/span> <\/span>e<\/span>[], <\/span>int<\/span> <\/span>m<\/span>)<\/span><\/span>\n{<\/span><\/span>\n\t<\/span>int<\/span> i, j, count, k, sum, u, v, t[MAXNODES][<\/span>2<\/span>], pos;<\/span><\/span>\n\t<\/span>int<\/span> parent[MAXNODES];<\/span><\/span>\n\tcount <\/span>=<\/span> <\/span>0<\/span>;<\/span><\/span>\n\tk <\/span>=<\/span> <\/span>0<\/span>;<\/span><\/span>\n\tsum <\/span>=<\/span> <\/span>0<\/span>;<\/span><\/span>\n\t<\/span>for<\/span>(i<\/span>=<\/span>0<\/span>; i<\/span><<\/span>n; i<\/span>++<\/span>)<\/span><\/span>\n\t{<\/span><\/span>\n\t\tparent[i] <\/span>=<\/span> i;<\/span><\/span>\n\t}<\/span><\/span>\n\t<\/span>while<\/span>(count <\/span>!=<\/span> n<\/span>-<\/span>1<\/span>)<\/span><\/span>\n\t{<\/span><\/span>\n\t\tpos <\/span>=<\/span> <\/span>fnGetMinEdge<\/span>(e,m);<\/span><\/span>\n\t\t<\/span>if<\/span>(pos <\/span>==<\/span> <\/span>-<\/span>1<\/span>)<\/span><\/span>\n\t\t{<\/span><\/span>\n\t\t\t<\/span>break<\/span>;<\/span><\/span>\n\t\t}<\/span><\/span>\n\t\tu <\/span>=<\/span> e[pos].u;<\/span><\/span>\n\t\tv <\/span>=<\/span> e[pos].v;<\/span><\/span>\n\t\ti <\/span>=<\/span> <\/span>fnFindParent<\/span>(u,parent);<\/span><\/span>\n\t\tj <\/span>=<\/span> <\/span>fnFindParent<\/span>(v,parent);<\/span><\/span>\n\t\t<\/span>if<\/span>(i <\/span>!=<\/span> j)<\/span><\/span>\n\t\t{<\/span><\/span>\n\t\t\tt[k][<\/span>0<\/span>] <\/span>=<\/span> u;<\/span><\/span>\n\t\t\tt[k][<\/span>1<\/span>] <\/span>=<\/span> v;<\/span><\/span>\n\t\t\tk<\/span>++<\/span>;<\/span><\/span>\n\t\t\tcount<\/span>++<\/span>;<\/span><\/span>\n\t\t\tsum <\/span>+=<\/span> e[pos].cost;<\/span><\/span>\n\t\t\t<\/span>fnUnion_ij<\/span>(i, j, parent);<\/span><\/span>\n\t\t}<\/span><\/span>\n\t\te[pos].cost <\/span>=<\/span> INF;<\/span><\/span>\n\t}<\/span><\/span>\n\t<\/span><\/span>\n\t<\/span>if<\/span>(count <\/span>==<\/span> n<\/span>-<\/span>1<\/span>)<\/span><\/span>\n\t{<\/span><\/span>\n\t\tcout <\/span><<<\/span> <\/span>"<\/span>\\n<\/span>Spanning tree exists"<\/span>;<\/span><\/span>\n\t\tcout <\/span><<<\/span> <\/span>"<\/span>\\n<\/span>The Spanning tree is shown below<\/span>\\n<\/span>"<\/span>;<\/span><\/span>\n\t\t<\/span>for<\/span>(i<\/span>=<\/span>0<\/span>; i<\/span><<\/span>n<\/span>-<\/span>1<\/span>; i<\/span>++<\/span>)<\/span><\/span>\n\t\t\tcout <\/span><<<\/span> t[i][<\/span>0<\/span>] <\/span><<<\/span> <\/span>" "<\/span> <\/span><<<\/span> t[i][<\/span>1<\/span>] <\/span><<<\/span> endl;<\/span><\/span>\n\t\tcout <\/span><<<\/span> <\/span>"<\/span>\\n<\/span>Cost of the spanning tree : "<\/span> <\/span><<<\/span> sum <\/span><<<\/span> endl;<\/span><\/span>\n\t}<\/span><\/span>\n\t<\/span>else<\/span><\/span>\n\t\tcout <\/span><<<\/span> <\/span>"<\/span>\\n<\/span>The spanning tree does not exist"<\/span> <\/span><<<\/span> endl;<\/span><\/span>\n}<\/span><\/span><\/code><\/pre><\/div>\n\n\n\n
              Java Code<\/h4>\n\n\n\n
              <\/circle><\/circle><\/circle><\/g><\/svg><\/span><\/path><\/path><\/svg><\/span>
              import<\/span> java.util.Scanner;<\/span><\/span>\n<\/span>\nclass<\/span> <\/span>Kruskal<\/span> {<\/span><\/span>\n    <\/span>static<\/span> <\/span>class<\/span> <\/span>Edge<\/span> {<\/span><\/span>\n        <\/span>int<\/span> u, v, cost;<\/span><\/span>\n    }<\/span><\/span>\n<\/span>\n    <\/span>private<\/span> <\/span>static<\/span> <\/span>final<\/span> <\/span>int<\/span> MAXNODES <\/span>=<\/span> <\/span>10<\/span>;<\/span><\/span>\n    <\/span>private<\/span> <\/span>static<\/span> <\/span>final<\/span> <\/span>int<\/span> INF <\/span>=<\/span> <\/span>9999<\/span>;<\/span><\/span>\n<\/span>\n    <\/span>private<\/span> <\/span>static<\/span> <\/span>int<\/span> <\/span>findParent<\/span>(<\/span>int<\/span> <\/span>v<\/span>, <\/span>int<\/span>[] <\/span>parent<\/span>) {<\/span><\/span>\n        <\/span>while<\/span> (parent[v] <\/span>!=<\/span> v)<\/span><\/span>\n            v <\/span>=<\/span> parent[v];<\/span><\/span>\n        <\/span>return<\/span> v;<\/span><\/span>\n    }<\/span><\/span>\n<\/span>\n    <\/span>private<\/span> <\/span>static<\/span> <\/span>void<\/span> <\/span>union<\/span>(<\/span>int<\/span> <\/span>i<\/span>, <\/span>int<\/span> <\/span>j<\/span>, <\/span>int<\/span>[] <\/span>parent<\/span>) {<\/span><\/span>\n        <\/span>if<\/span> (i <\/span><<\/span> j)<\/span><\/span>\n            parent[j] <\/span>=<\/span> i;<\/span><\/span>\n        <\/span>else<\/span><\/span>\n            parent[i] <\/span>=<\/span> j;<\/span><\/span>\n    }<\/span><\/span>\n<\/span>\n    <\/span>private<\/span> <\/span>static<\/span> <\/span>void<\/span> <\/span>inputGraph<\/span>(<\/span>int<\/span> <\/span>m<\/span>, <\/span>Edge<\/span>[] <\/span>e<\/span>) {<\/span><\/span>\n        Scanner scanner <\/span>=<\/span> <\/span>new<\/span> <\/span>Scanner<\/span>(System.in);<\/span><\/span>\n        <\/span>for<\/span> (<\/span>int<\/span> k <\/span>=<\/span> <\/span>0<\/span>; k <\/span><<\/span> m; k<\/span>++<\/span>) {<\/span><\/span>\n            System.out.<\/span>println<\/span>(<\/span>"Enter edge and cost in the form u, v, w :"<\/span>);<\/span><\/span>\n            <\/span>int<\/span> i <\/span>=<\/span> scanner.<\/span>nextInt<\/span>();<\/span><\/span>\n            <\/span>int<\/span> j <\/span>=<\/span> scanner.<\/span>nextInt<\/span>();<\/span><\/span>\n            <\/span>int<\/span> cost <\/span>=<\/span> scanner.<\/span>nextInt<\/span>();<\/span><\/span>\n            e[k] <\/span>=<\/span> <\/span>new<\/span> <\/span>Edge<\/span>();<\/span><\/span>\n            e[k].u <\/span>=<\/span> i;<\/span><\/span>\n            e[k].v <\/span>=<\/span> j;<\/span><\/span>\n            e[k].cost <\/span>=<\/span> cost;<\/span><\/span>\n        }<\/span><\/span>\n        scanner.<\/span>close<\/span>();<\/span><\/span>\n    }<\/span><\/span>\n<\/span>\n    <\/span>private<\/span> <\/span>static<\/span> <\/span>int<\/span> <\/span>getMinEdge<\/span>(<\/span>Edge<\/span>[] <\/span>e<\/span>, <\/span>int<\/span> <\/span>n<\/span>) {<\/span><\/span>\n        <\/span>int<\/span> small <\/span>=<\/span> INF;<\/span><\/span>\n        <\/span>int<\/span> pos <\/span>=<\/span> <\/span>-<\/span>1<\/span>;<\/span><\/span>\n        <\/span>for<\/span> (<\/span>int<\/span> i <\/span>=<\/span> <\/span>0<\/span>; i <\/span><<\/span> n; i<\/span>++<\/span>) {<\/span><\/span>\n            <\/span>if<\/span> (e[i].cost <\/span><<\/span> small) {<\/span><\/span>\n                small <\/span>=<\/span> e[i].cost;<\/span><\/span>\n                pos <\/span>=<\/span> i;<\/span><\/span>\n            }<\/span><\/span>\n        }<\/span><\/span>\n        <\/span>return<\/span> pos;<\/span><\/span>\n    }<\/span><\/span>\n<\/span>\n    <\/span>private<\/span> <\/span>static<\/span> <\/span>void<\/span> <\/span>kruskal<\/span>(<\/span>int<\/span> <\/span>n<\/span>, <\/span>Edge<\/span>[] <\/span>e<\/span>, <\/span>int<\/span> <\/span>m<\/span>) {<\/span><\/span>\n        <\/span>int<\/span> count <\/span>=<\/span> <\/span>0<\/span>;<\/span><\/span>\n        <\/span>int<\/span> k <\/span>=<\/span> <\/span>0<\/span>;<\/span><\/span>\n        <\/span>int<\/span> sum <\/span>=<\/span> <\/span>0<\/span>;<\/span><\/span>\n        <\/span>int<\/span>[][] t <\/span>=<\/span> <\/span>new<\/span> <\/span>int<\/span>[MAXNODES][<\/span>2<\/span>];<\/span><\/span>\n        <\/span>int<\/span>[] parent <\/span>=<\/span> <\/span>new<\/span> <\/span>int<\/span>[MAXNODES];<\/span><\/span>\n<\/span>\n        <\/span>for<\/span> (<\/span>int<\/span> i <\/span>=<\/span> <\/span>0<\/span>; i <\/span><<\/span> n; i<\/span>++<\/span>) {<\/span><\/span>\n            parent[i] <\/span>=<\/span> i;<\/span><\/span>\n        }<\/span><\/span>\n<\/span>\n        <\/span>while<\/span> (count <\/span>!=<\/span> n <\/span>-<\/span> <\/span>1<\/span>) {<\/span><\/span>\n            <\/span>int<\/span> pos <\/span>=<\/span> <\/span>getMinEdge<\/span>(e, m);<\/span><\/span>\n            <\/span>if<\/span> (pos <\/span>==<\/span> <\/span>-<\/span>1<\/span>) {<\/span><\/span>\n                <\/span>break<\/span>;<\/span><\/span>\n            }<\/span><\/span>\n            <\/span>int<\/span> u <\/span>=<\/span> e[pos].u;<\/span><\/span>\n            <\/span>int<\/span> v <\/span>=<\/span> e[pos].v;<\/span><\/span>\n            <\/span>int<\/span> i <\/span>=<\/span> <\/span>findParent<\/span>(u, parent);<\/span><\/span>\n            <\/span>int<\/span> j <\/span>=<\/span> <\/span>findParent<\/span>(v, parent);<\/span><\/span>\n            <\/span>if<\/span> (i <\/span>!=<\/span> j) {<\/span><\/span>\n                t[k][<\/span>0<\/span>] <\/span>=<\/span> u;<\/span><\/span>\n                t[k][<\/span>1<\/span>] <\/span>=<\/span> v;<\/span><\/span>\n                k<\/span>++<\/span>;<\/span><\/span>\n                count<\/span>++<\/span>;<\/span><\/span>\n                sum <\/span>+=<\/span> e[pos].cost;<\/span><\/span>\n                <\/span>union<\/span>(i, j, parent);<\/span><\/span>\n            }<\/span><\/span>\n            e[pos].cost <\/span>=<\/span> INF;<\/span><\/span>\n        }<\/span><\/span>\n<\/span>\n        <\/span>if<\/span> (count <\/span>==<\/span> n <\/span>-<\/span> <\/span>1<\/span>) {<\/span><\/span>\n            System.out.<\/span>println<\/span>(<\/span>"<\/span>\\n<\/span>Spanning tree exists"<\/span>);<\/span><\/span>\n            System.out.<\/span>println<\/span>(<\/span>"The Spanning tree is shown below"<\/span>);<\/span><\/span>\n            <\/span>for<\/span> (<\/span>int<\/span> i <\/span>=<\/span> <\/span>0<\/span>; i <\/span><<\/span> n <\/span>-<\/span> <\/span>1<\/span>; i<\/span>++<\/span>)<\/span><\/span>\n                System.out.<\/span>println<\/span>(t[i][<\/span>0<\/span>] <\/span>+<\/span> <\/span>" "<\/span> <\/span>+<\/span> t[i][<\/span>1<\/span>]);<\/span><\/span>\n            System.out.<\/span>println<\/span>(<\/span>"Cost of the spanning tree: "<\/span> <\/span>+<\/span> sum);<\/span><\/span>\n        } <\/span>else<\/span> {<\/span><\/span>\n            System.out.<\/span>println<\/span>(<\/span>"<\/span>\\n<\/span>The spanning tree does not exist"<\/span>);<\/span><\/span>\n        }<\/span><\/span>\n    }<\/span><\/span>\n<\/span>\n    <\/span>public<\/span> <\/span>static<\/span> <\/span>void<\/span> <\/span>main<\/span>(<\/span>String<\/span>[] <\/span>args<\/span>) {<\/span><\/span>\n        <\/span>int<\/span> n <\/span>=<\/span> <\/span>6<\/span>, m <\/span>=<\/span> <\/span>20<\/span>;<\/span><\/span>\n        <\/span>Edge<\/span>[] e <\/span>=<\/span> <\/span>new<\/span> <\/span>Edge<\/span>[<\/span>2<\/span> <\/span>*<\/span> MAXNODES];<\/span><\/span>\n        Scanner scanner <\/span>=<\/span> <\/span>new<\/span> <\/span>Scanner<\/span>(System.in);<\/span><\/span>\n        System.out.<\/span>print<\/span>(<\/span>"Enter the number of nodes : "<\/span>);<\/span><\/span>\n        n <\/span>=<\/span> scanner.<\/span>nextInt<\/span>();<\/span><\/span>\n        System.out.<\/span>print<\/span>(<\/span>"Enter the number of edges : "<\/span>);<\/span><\/span>\n        m <\/span>=<\/span> scanner.<\/span>nextInt<\/span>();<\/span><\/span>\n        <\/span>inputGraph<\/span>(m, e);<\/span><\/span>\n        <\/span>kruskal<\/span>(n, e, m);<\/span><\/span>\n    }<\/span><\/span>\n}<\/span><\/span>\n<\/span><\/code><\/pre><\/div>\n\n\n\n
              Input Graph<\/h4>\n\n\n\n
              For this program lets consider the following graph<\/p>\n\n\n\n
              \"\"<\/a><\/figure>\n\n\n\n
              Output<\/h4>\n\n\n\n
              <\/circle><\/circle><\/circle><\/g><\/svg><\/span><\/path><\/path><\/svg><\/span>
              Enter the number <\/span>of<\/span> <\/span>nodes<\/span> : <\/span>6<\/span><\/span>\nEnter the number <\/span>of<\/span> <\/span>edges<\/span> : <\/span>10<\/span><\/span>\nEnter edge and cost <\/span>in<\/span> the form u, v, <\/span>w<\/span> : <\/span><\/span>\n0<\/span> <\/span>1<\/span> <\/span>6<\/span><\/span>\nEnter edge and cost <\/span>in<\/span> the form u, v, <\/span>w<\/span> : <\/span><\/span>\n1<\/span> <\/span>4<\/span> <\/span>4<\/span><\/span>\nEnter edge and cost <\/span>in<\/span> the form u, v, <\/span>w<\/span> : <\/span><\/span>\n4<\/span> <\/span>5<\/span> <\/span>6<\/span><\/span>\nEnter edge and cost <\/span>in<\/span> the form u, v, <\/span>w<\/span> : <\/span><\/span>\n5<\/span> <\/span>3<\/span> <\/span>2<\/span><\/span>\nEnter edge and cost <\/span>in<\/span> the form u, v, <\/span>w<\/span> : <\/span><\/span>\n3<\/span> <\/span>0<\/span> <\/span>5<\/span><\/span>\nEnter edge and cost <\/span>in<\/span> the form u, v, <\/span>w<\/span> : <\/span><\/span>\n0<\/span> <\/span>2<\/span> <\/span>1<\/span><\/span>\nEnter edge and cost <\/span>in<\/span> the form u, v, <\/span>w<\/span> : <\/span><\/span>\n1<\/span> <\/span>2<\/span> <\/span>5<\/span><\/span>\nEnter edge and cost <\/span>in<\/span> the form u, v, <\/span>w<\/span> : <\/span><\/span>\n3<\/span> <\/span>2<\/span> <\/span>2<\/span><\/span>\nEnter edge and cost <\/span>in<\/span> the form u, v, <\/span>w<\/span> : <\/span><\/span>\n4<\/span> <\/span>2<\/span> <\/span>6<\/span><\/span>\nEnter edge and cost <\/span>in<\/span> the form u, v, <\/span>w<\/span> : <\/span><\/span>\n5<\/span> <\/span>2<\/span> <\/span>3<\/span><\/span>\n<\/span>\nSpanning tree exists<\/span><\/span>\nThe Spanning tree is shown below<\/span><\/span>\n0<\/span> <\/span>2<\/span><\/span>\n5<\/span> <\/span>3<\/span><\/span>\n3<\/span> <\/span>2<\/span><\/span>\n1<\/span> <\/span>4<\/span><\/span>\n1<\/span> <\/span>2<\/span><\/span>\n<\/span>\nCost <\/span>of<\/span> the spanning <\/span>tree<\/span> : <\/span>14<\/span><\/span>\n<\/span><\/code><\/pre><\/div>\n\n\n\n
              Spanning Tree of the graph<\/h4>\n\n\n\n
              \"\"<\/a><\/figure>\n\n\n\n
              \n\n\n\n
              Prim’s Algorithm<\/h3>\n\n\n\n
              Write & Execute C++\/Java Program to find Minimum Cost Spanning Tree of a given connected undirected graph using Prim’s algorithm.<\/p>\n\n\n\n
              C++ Code<\/h4>\n\n\n\n
              <\/circle><\/circle><\/circle><\/g><\/svg><\/span><\/path><\/path><\/svg><\/span>
              \/******************************************************************************<\/span><\/span>\n*File\t\t: 07PrimMST.cpp<\/span><\/span>\n*Description: Program to find Minimum Cost Spanning Tree of a given<\/span><\/span>\n*\tundirected graph using Prim's algorithm.<\/span><\/span>\n*Author\t\t: Prabodh C P<\/span><\/span>\n*Compiler\t: g++ compiler 7.5.0, Ubuntu 18.04<\/span><\/span>\n*Date\t\t: 31 Mar 2020<\/span><\/span>\n******************************************************************************\/<\/span><\/span>\n#include<\/span> <\/span><iostream><\/span><\/span>\nusing<\/span> <\/span>namespace<\/span> <\/span>std<\/span>;<\/span><\/span>\nconst<\/span> <\/span>int<\/span> MAXNODES <\/span>=<\/span> <\/span>10<\/span>;<\/span><\/span>\nvoid<\/span> <\/span>fnPrims<\/span>(<\/span>int<\/span> <\/span>n<\/span>, <\/span>int<\/span> <\/span>cost<\/span>[MAXNODES][MAXNODES]);<\/span><\/span>\nvoid<\/span> <\/span>fnGetMatrix<\/span>(<\/span>int<\/span> <\/span>n<\/span>,<\/span>int<\/span> <\/span>a<\/span>[MAXNODES][MAXNODES]);<\/span><\/span>\n\/******************************************************************************\t<\/span><\/span>\n*Function\t: main<\/span><\/span>\n*Input parameters:<\/span><\/span>\n*\tint argc - no of commamd line arguments<\/span><\/span>\n*\tchar **argv - vector to store command line argumennts<\/span><\/span>\n*RETURNS\t: 0 on success<\/span><\/span>\n******************************************************************************\/<\/span><\/span>\nint<\/span> <\/span>main<\/span>( <\/span>int<\/span> <\/span>argc<\/span>, <\/span>char<\/span> <\/span>**<\/span>argv<\/span>)<\/span><\/span>\n{<\/span><\/span>\n\t<\/span>int<\/span> a[MAXNODES][MAXNODES] <\/span>=<\/span> {<\/span><\/span>\n\t{<\/span>0<\/span>, <\/span>3<\/span>, <\/span>9999<\/span>, <\/span>7<\/span>, <\/span>9<\/span>},\t{<\/span>3<\/span>, <\/span>0<\/span>, <\/span>4<\/span>, <\/span>2<\/span>, <\/span>9999<\/span>},\t{<\/span>9999<\/span>, <\/span>4<\/span>, <\/span>0<\/span>, <\/span>5<\/span>, <\/span>6<\/span>},<\/span><\/span>\n\t{<\/span>7<\/span>, <\/span>2<\/span>, <\/span>5<\/span>, <\/span>0<\/span>, <\/span>4<\/span>},\t{<\/span>9<\/span>, <\/span>9999<\/span>, <\/span>6<\/span>, <\/span>4<\/span>, <\/span>0<\/span>}};<\/span><\/span>\n\t<\/span>int<\/span> n <\/span>=<\/span> <\/span>5<\/span>;<\/span><\/span>\n\tcout <\/span><<<\/span> <\/span>"Enter the number of vertices : "<\/span>;<\/span><\/span>\n\tcin <\/span>>><\/span> n;<\/span><\/span>\n\t<\/span>fnGetMatrix<\/span>(n,a);<\/span><\/span>\n\t<\/span>fnPrims<\/span>(n,a);<\/span><\/span>\n\t<\/span>return<\/span> <\/span>0<\/span>;<\/span><\/span>\n}<\/span><\/span>\n\/******************************************************************************<\/span><\/span>\n*Function\t: fnPrims<\/span><\/span>\n*Description\t: Function to find Minimum Cost Spanning Tree of a given<\/span><\/span>\n*\tundirected graph using Prims algorithm.<\/span><\/span>\n*Input parameters:<\/span><\/span>\n*\tint n - no of vertices in the graph<\/span><\/span>\n*\tint cost[][] - cost adjacency matrix of the graph<\/span><\/span>\n*RETURNS\t: no value<\/span><\/span>\n******************************************************************************\/<\/span><\/span>\nvoid<\/span> <\/span>fnPrims<\/span>(<\/span>int<\/span> <\/span>n<\/span>, <\/span>int<\/span> <\/span>cost<\/span>[MAXNODES][MAXNODES])<\/span><\/span>\n{<\/span><\/span>\n\t<\/span>int<\/span> i, j, u, v, min;<\/span><\/span>\n\t<\/span>int<\/span> sum, k, t[MAXNODES][<\/span>2<\/span>], p[MAXNODES], d[MAXNODES], s[MAXNODES];<\/span><\/span>\n\t<\/span>int<\/span> source, count;<\/span><\/span>\n<\/span>\n\tmin <\/span>=<\/span> <\/span>9999<\/span>;<\/span><\/span>\n\tsource <\/span>=<\/span> <\/span>0<\/span>;<\/span><\/span>\n\t<\/span>for<\/span>(i<\/span>=<\/span>0<\/span>; i<\/span><<\/span>n; i<\/span>++<\/span>)<\/span><\/span>\n\t{<\/span><\/span>\n\t\t<\/span>for<\/span>(j<\/span>=<\/span>0<\/span>; j<\/span><<\/span>n; j<\/span>++<\/span>)<\/span><\/span>\n\t\t{<\/span><\/span>\n\t\t\t<\/span>if<\/span>(cost[i][j] <\/span>!=<\/span> <\/span>0<\/span> <\/span>&&<\/span> cost[i][j] <\/span><=<\/span> min)<\/span><\/span>\n\t\t\t{<\/span><\/span>\n\t\t\t\tmin <\/span>=<\/span> cost[i][j];<\/span><\/span>\n\t\t\t\tsource <\/span>=<\/span> i;<\/span><\/span>\n\t\t\t}<\/span><\/span>\n\t\t}<\/span><\/span>\n\t}<\/span><\/span>\n\t<\/span>for<\/span>(i<\/span>=<\/span>0<\/span>; i<\/span><<\/span>n; i<\/span>++<\/span>)<\/span><\/span>\n\t{<\/span><\/span>\n\t\td[i] <\/span>=<\/span> cost[source][i];<\/span><\/span>\n\t\ts[i] <\/span>=<\/span> <\/span>0<\/span>;<\/span><\/span>\n\t\tp[i] <\/span>=<\/span> source;<\/span><\/span>\n\t}<\/span><\/span>\n\ts[source] <\/span>=<\/span> <\/span>1<\/span>;<\/span><\/span>\n\tsum <\/span>=<\/span> <\/span>0<\/span>;<\/span><\/span>\n\tk <\/span>=<\/span> <\/span>0<\/span>;<\/span><\/span>\n\tcount <\/span>=<\/span> <\/span>0<\/span>;<\/span><\/span>\n\t<\/span>while<\/span> (count <\/span>!=<\/span> n<\/span>-<\/span>1<\/span>)<\/span><\/span>\n\t{<\/span><\/span>\n\t\tmin <\/span>=<\/span> <\/span>9999<\/span>;<\/span><\/span>\n\t\tu <\/span>=<\/span> <\/span>-<\/span>1<\/span>;<\/span><\/span>\n\t\t<\/span>for<\/span>(j<\/span>=<\/span>0<\/span>; j<\/span><<\/span>n; j<\/span>++<\/span>)<\/span><\/span>\n\t\t{<\/span><\/span>\n\t\t\t<\/span>if<\/span>(s[j] <\/span>==<\/span> <\/span>0<\/span>)<\/span><\/span>\n\t\t\t{<\/span><\/span>\n\t\t\t\t<\/span>if<\/span>(d[j] <\/span><=<\/span> min)<\/span><\/span>\n\t\t\t\t{<\/span><\/span>\n\t\t\t\t\tmin <\/span>=<\/span> d[j];<\/span><\/span>\n\t\t\t\t\tu <\/span>=<\/span> j;<\/span><\/span>\n\t\t\t\t}<\/span><\/span>\n\t\t\t}<\/span><\/span>\n\t\t}<\/span><\/span>\n\t\tt[k][<\/span>0<\/span>] <\/span>=<\/span> u;<\/span><\/span>\n\t\tt[k][<\/span>1<\/span>] <\/span>=<\/span> p[u];<\/span><\/span>\n\t\tk<\/span>++<\/span>;<\/span><\/span>\n\t\tcount<\/span>++<\/span>;<\/span><\/span>\n\t\tsum <\/span>+=<\/span> cost[u][p[u]];<\/span><\/span>\n\t\ts[u] <\/span>=<\/span> <\/span>1<\/span>;<\/span><\/span>\n\t\t<\/span>for<\/span>(v<\/span>=<\/span>0<\/span>; v<\/span><<\/span>n; v<\/span>++<\/span>)<\/span><\/span>\n\t\t{<\/span><\/span>\n\t\t\t<\/span>if<\/span>(s[v]<\/span>==<\/span>0<\/span> <\/span>&&<\/span> cost[u][v]<\/span><<\/span>d[v])<\/span><\/span>\n\t\t\t{<\/span><\/span>\n\t\t\t\td[v] <\/span>=<\/span> cost[u][v];<\/span><\/span>\n\t\t\t\tp[v] <\/span>=<\/span> u;<\/span><\/span>\n\t\t\t}<\/span><\/span>\n\t\t}<\/span><\/span>\n\t}<\/span><\/span>\n\t<\/span>if<\/span>(sum <\/span>>=<\/span> <\/span>9999<\/span>)<\/span><\/span>\n\tcout <\/span><<<\/span> <\/span>"<\/span>\\n<\/span>Spanning tree does not exist<\/span>\\n<\/span>"<\/span>;<\/span><\/span>\n\t<\/span>else<\/span><\/span>\n\t{<\/span><\/span>\n\tcout <\/span><<<\/span> <\/span>"<\/span>\\n<\/span>The spanning tree exists and minimum cost spanning tree is <\/span>\\n<\/span>"<\/span>;<\/span><\/span>\n\t<\/span>for<\/span>(i<\/span>=<\/span>0<\/span>; i<\/span><<\/span>k; i<\/span>++<\/span>)<\/span><\/span>\n\tcout <\/span><<<\/span> t[i][<\/span>1<\/span>] <\/span><<<\/span> <\/span>" "<\/span> <\/span><<<\/span> t[i][<\/span>0<\/span>] <\/span><<<\/span> endl;<\/span><\/span>\n\tcout <\/span><<<\/span> <\/span>"<\/span>\\n<\/span>The cost of the minimum cost spanning tree is "<\/span> <\/span><<<\/span> sum <\/span><<<\/span> endl;<\/span><\/span>\n\t}<\/span><\/span>\n}<\/span><\/span>\n<\/span>\n\/******************************************************************************<\/span><\/span>\n*Function : fnGetMatrix<\/span><\/span>\n*Description : Function to read cost adjacency matrix of the graph<\/span><\/span>\n*Input parameters:<\/span><\/span>\n*\tint n - no of vertices in the graph<\/span><\/span>\n*\tint a[][] - cost adjacency matrix of the graph<\/span><\/span>\n*RETURNS\t: no value<\/span><\/span>\n******************************************************************************\/<\/span><\/span>\nvoid<\/span> <\/span>fnGetMatrix<\/span>(<\/span>int<\/span> <\/span>n<\/span>,<\/span>int<\/span> <\/span>a<\/span>[MAXNODES][MAXNODES])<\/span><\/span>\n{<\/span><\/span>\n\t<\/span>int<\/span> i, j;<\/span><\/span>\n\tcout <\/span><<<\/span> <\/span>"Enter the Cost Adjacency Matrix"<\/span> <\/span><<<\/span> endl;<\/span><\/span>\n\t<\/span>for<\/span>(i<\/span>=<\/span>0<\/span>; i<\/span><<\/span>n; i<\/span>++<\/span>)<\/span><\/span>\n\t\t<\/span>for<\/span>(j<\/span>=<\/span>0<\/span>; j<\/span><<\/span>n; j<\/span>++<\/span>)<\/span><\/span>\n\t\t\tcin <\/span>>><\/span> a[i][j];<\/span><\/span>\n}<\/span><\/span><\/code><\/pre><\/div>\n\n\n\n
              Java Code<\/h4>\n\n\n\n
              <\/circle><\/circle><\/circle><\/g><\/svg><\/span><\/path><\/path><\/svg><\/span>
              import<\/span> java.util.Scanner;<\/span><\/span>\n<\/span>\nclass<\/span> <\/span>Prims<\/span> {<\/span><\/span>\n    <\/span>static<\/span> <\/span>final<\/span> <\/span>int<\/span> MAXNODES <\/span>=<\/span> <\/span>10<\/span>;<\/span><\/span>\n<\/span>\n    <\/span>static<\/span> <\/span>void<\/span> <\/span>fnPrims<\/span>(<\/span>int<\/span> <\/span>n<\/span>, <\/span>int<\/span>[][] <\/span>cost<\/span>) {<\/span><\/span>\n        <\/span>int<\/span> i, j, u, v, min;<\/span><\/span>\n        <\/span>int<\/span> sum, k, t[][] <\/span>=<\/span> <\/span>new<\/span> <\/span>int<\/span>[MAXNODES][<\/span>2<\/span>], p[] <\/span>=<\/span> <\/span>new<\/span> <\/span>int<\/span>[MAXNODES], d[] <\/span>=<\/span> <\/span>new<\/span> <\/span>int<\/span>[MAXNODES], s[] <\/span>=<\/span> <\/span>new<\/span> <\/span>int<\/span>[MAXNODES];<\/span><\/span>\n        <\/span>int<\/span> source, count;<\/span><\/span>\n<\/span>\n        min <\/span>=<\/span> <\/span>9999<\/span>;<\/span><\/span>\n        source <\/span>=<\/span> <\/span>0<\/span>;<\/span><\/span>\n        <\/span>for<\/span> (i <\/span>=<\/span> <\/span>0<\/span>; i <\/span><<\/span> n; i<\/span>++<\/span>) {<\/span><\/span>\n            <\/span>for<\/span> (j <\/span>=<\/span> <\/span>0<\/span>; j <\/span><<\/span> n; j<\/span>++<\/span>) {<\/span><\/span>\n                <\/span>if<\/span> (cost[i][j] <\/span>!=<\/span> <\/span>0<\/span> <\/span>&&<\/span> cost[i][j] <\/span><=<\/span> min) {<\/span><\/span>\n                    min <\/span>=<\/span> cost[i][j];<\/span><\/span>\n                    source <\/span>=<\/span> i;<\/span><\/span>\n                }<\/span><\/span>\n            }<\/span><\/span>\n        }<\/span><\/span>\n        <\/span>for<\/span> (i <\/span>=<\/span> <\/span>0<\/span>; i <\/span><<\/span> n; i<\/span>++<\/span>) {<\/span><\/span>\n            d[i] <\/span>=<\/span> cost[source][i];<\/span><\/span>\n            s[i] <\/span>=<\/span> <\/span>0<\/span>;<\/span><\/span>\n            p[i] <\/span>=<\/span> source;<\/span><\/span>\n        }<\/span><\/span>\n        s[source] <\/span>=<\/span> <\/span>1<\/span>;<\/span><\/span>\n        sum <\/span>=<\/span> <\/span>0<\/span>;<\/span><\/span>\n        k <\/span>=<\/span> <\/span>0<\/span>;<\/span><\/span>\n        count <\/span>=<\/span> <\/span>0<\/span>;<\/span><\/span>\n        <\/span>while<\/span> (count <\/span>!=<\/span> n <\/span>-<\/span> <\/span>1<\/span>) {<\/span><\/span>\n            min <\/span>=<\/span> <\/span>9999<\/span>;<\/span><\/span>\n            u <\/span>=<\/span> <\/span>-<\/span>1<\/span>;<\/span><\/span>\n            <\/span>for<\/span> (j <\/span>=<\/span> <\/span>0<\/span>; j <\/span><<\/span> n; j<\/span>++<\/span>) {<\/span><\/span>\n                <\/span>if<\/span> (s[j] <\/span>==<\/span> <\/span>0<\/span>) {<\/span><\/span>\n                    <\/span>if<\/span> (d[j] <\/span><=<\/span> min) {<\/span><\/span>\n                        min <\/span>=<\/span> d[j];<\/span><\/span>\n                        u <\/span>=<\/span> j;<\/span><\/span>\n                    }<\/span><\/span>\n                }<\/span><\/span>\n            }<\/span><\/span>\n            t[k][<\/span>0<\/span>] <\/span>=<\/span> u;<\/span><\/span>\n            t[k][<\/span>1<\/span>] <\/span>=<\/span> p[u];<\/span><\/span>\n            k<\/span>++<\/span>;<\/span><\/span>\n            count<\/span>++<\/span>;<\/span><\/span>\n            sum <\/span>+=<\/span> cost[u][p[u]];<\/span><\/span>\n            s[u] <\/span>=<\/span> <\/span>1<\/span>;<\/span><\/span>\n            <\/span>for<\/span> (v <\/span>=<\/span> <\/span>0<\/span>; v <\/span><<\/span> n; v<\/span>++<\/span>) {<\/span><\/span>\n                <\/span>if<\/span> (s[v] <\/span>==<\/span> <\/span>0<\/span> <\/span>&&<\/span> cost[u][v] <\/span><<\/span> d[v]) {<\/span><\/span>\n                    d[v] <\/span>=<\/span> cost[u][v];<\/span><\/span>\n                    p[v] <\/span>=<\/span> u;<\/span><\/span>\n                }<\/span><\/span>\n            }<\/span><\/span>\n        }<\/span><\/span>\n        <\/span>if<\/span> (sum <\/span>>=<\/span> <\/span>9999<\/span>)<\/span><\/span>\n            System.out.<\/span>println<\/span>(<\/span>"<\/span>\\n<\/span>Spanning tree does not exist"<\/span>);<\/span><\/span>\n        <\/span>else<\/span> {<\/span><\/span>\n            System.out.<\/span>println<\/span>(<\/span>"<\/span>\\n<\/span>The spanning tree exists and the minimum cost spanning tree is:"<\/span>);<\/span><\/span>\n            <\/span>for<\/span> (i <\/span>=<\/span> <\/span>0<\/span>; i <\/span><<\/span> k; i<\/span>++<\/span>)<\/span><\/span>\n                System.out.<\/span>println<\/span>(t[i][<\/span>1<\/span>] <\/span>+<\/span> <\/span>" "<\/span> <\/span>+<\/span> t[i][<\/span>0<\/span>]);<\/span><\/span>\n            System.out.<\/span>println<\/span>(<\/span>"<\/span>\\n<\/span>The cost of the minimum cost spanning tree is "<\/span> <\/span>+<\/span> sum);<\/span><\/span>\n        }<\/span><\/span>\n    }<\/span><\/span>\n<\/span>\n    <\/span>public<\/span> <\/span>static<\/span> <\/span>void<\/span> <\/span>main<\/span>(<\/span>String<\/span>[] <\/span>args<\/span>) {<\/span><\/span>\n        Scanner scanner <\/span>=<\/span> <\/span>new<\/span> <\/span>Scanner<\/span>(System.in);<\/span><\/span>\n        <\/span>int<\/span> a[][] <\/span>=<\/span> { { <\/span>0<\/span>, <\/span>3<\/span>, <\/span>9999<\/span>, <\/span>7<\/span>, <\/span>9<\/span> }, { <\/span>3<\/span>, <\/span>0<\/span>, <\/span>4<\/span>, <\/span>2<\/span>, <\/span>9999<\/span> }, { <\/span>9999<\/span>, <\/span>4<\/span>, <\/span>0<\/span>, <\/span>5<\/span>, <\/span>6<\/span> }, { <\/span>7<\/span>, <\/span>2<\/span>, <\/span>5<\/span>, <\/span>0<\/span>, <\/span>4<\/span> },<\/span><\/span>\n                { <\/span>9<\/span>, <\/span>9999<\/span>, <\/span>6<\/span>, <\/span>4<\/span>, <\/span>0<\/span> } };<\/span><\/span>\n        <\/span>int<\/span> n <\/span>=<\/span> <\/span>5<\/span>;<\/span><\/span>\n        System.out.<\/span>print<\/span>(<\/span>"Enter the number of vertices: "<\/span>);<\/span><\/span>\n        n <\/span>=<\/span> scanner.<\/span>nextInt<\/span>();<\/span><\/span>\n        <\/span>fnGetMatrix<\/span>(n, a);<\/span><\/span>\n        <\/span>fnPrims<\/span>(n, a);<\/span><\/span>\n    }<\/span><\/span>\n<\/span>\n    <\/span>static<\/span> <\/span>void<\/span> <\/span>fnGetMatrix<\/span>(<\/span>int<\/span> <\/span>n<\/span>, <\/span>int<\/span> <\/span>a<\/span>[][]) {<\/span><\/span>\n        Scanner scanner <\/span>=<\/span> <\/span>new<\/span> <\/span>Scanner<\/span>(System.in);<\/span><\/span>\n        System.out.<\/span>println<\/span>(<\/span>"Enter the Cost Adjacency Matrix:"<\/span>);<\/span><\/span>\n        <\/span>for<\/span> (<\/span>int<\/span> i <\/span>=<\/span> <\/span>0<\/span>; i <\/span><<\/span> n; i<\/span>++<\/span>)<\/span><\/span>\n            <\/span>for<\/span> (<\/span>int<\/span> j <\/span>=<\/span> <\/span>0<\/span>; j <\/span><<\/span> n; j<\/span>++<\/span>)<\/span><\/span>\n                a[i][j] <\/span>=<\/span> scanner.<\/span>nextInt<\/span>();<\/span><\/span>\n        scanner.<\/span>close<\/span>();<\/span><\/span>\n    }<\/span><\/span>\n}<\/span><\/span>\n<\/span><\/code><\/pre><\/div>\n\n\n\n
              Input Graph<\/h4>\n\n\n\n
              For this program lets consider the following graph<\/p>\n\n\n\n
              \"\"<\/a><\/figure>\n\n\n\n
              Output<\/h4>\n\n\n\n
              <\/circle><\/circle><\/circle><\/g><\/svg><\/span><\/path><\/path><\/svg><\/span>
              Enter the number <\/span>of<\/span> <\/span>vertices<\/span> : <\/span>5<\/span><\/span>\nEnter the Cost Adjacency Matrix<\/span><\/span>\n0<\/span> <\/span>3<\/span> <\/span>9999<\/span> <\/span>7<\/span> <\/span>9<\/span><\/span>\n3<\/span> <\/span>0<\/span> <\/span>4<\/span> <\/span>2<\/span> <\/span>9999<\/span><\/span>\n9999<\/span> <\/span>4<\/span> <\/span>0<\/span> <\/span>5<\/span> <\/span>6<\/span><\/span>\n7<\/span> <\/span>2<\/span> <\/span>5<\/span> <\/span>0<\/span> <\/span>4<\/span><\/span>\n9<\/span> <\/span>9999<\/span> <\/span>6<\/span> <\/span>4<\/span> <\/span>0<\/span><\/span>\n<\/span>\nThe spanning tree exists and minimum cost spanning tree is <\/span><\/span>\n3<\/span> <\/span>1<\/span><\/span>\n1<\/span> <\/span>0<\/span><\/span>\n3<\/span> <\/span>4<\/span><\/span>\n1<\/span> <\/span>2<\/span><\/span>\n<\/span>\nThe cost <\/span>of<\/span> the minimum cost spanning tree is <\/span>13<\/span><\/span>\n<\/span><\/code><\/pre><\/div>\n\n\n\n
              Spanning Tree of the graph<\/h4>\n\n\n\n
              \"\"<\/a><\/figure>\n\n\n\n
              Module 4<\/h2>\n\n\n\n
              Floyd’s Algorithm<\/h3>\n\n\n\n
              Write C++\/ Java programs to solve All-Pairs Shortest Paths problem using Floyd’s algorithm.<\/p>\n\n\n\n
              C++ Code<\/h4>\n\n\n\n
              <\/circle><\/circle><\/circle><\/g><\/svg><\/span><\/path><\/path><\/svg><\/span>
              \/***************************************************************************<\/span><\/span>\n*File\t\t: Floyd.c<\/span><\/span>\n*Description: Program to implement Floyd's Algorithm<\/span><\/span>\n*Author\t\t: Prabodh C P<\/span><\/span>\n*Compiler\t: gcc compiler 7.5.0, Ubuntu 18.04<\/span><\/span>\n*Date\t\t: 31 Mar 2020<\/span><\/span>\n***************************************************************************\/<\/span><\/span>\n#include <\/span><<\/span>iostream<\/span>><\/span><\/span>\nusing<\/span> <\/span>namespace<\/span> std;<\/span><\/span>\n\/******************************************************************************<\/span><\/span>\n*Function\t: \tmain<\/span><\/span>\n*Input parameters: no parameters<\/span><\/span>\n*RETURNS\t:\t0 on success<\/span><\/span>\n******************************************************************************\/<\/span><\/span>\nint <\/span>main<\/span>(<\/span>void<\/span>)<\/span><\/span>\n{<\/span><\/span>\n\tint iN, i, j, k;<\/span><\/span>\n\tint iaFloyd[<\/span>10<\/span>][<\/span>10<\/span>], iaCost[<\/span>10<\/span>][<\/span>10<\/span>];<\/span><\/span>\n\tcout <\/span><<<\/span> <\/span>"<\/span>\\n<\/span>*********************************************************"<\/span>;<\/span><\/span>\n\tcout <\/span><<<\/span> <\/span>"<\/span>\\n<\/span>*<\/span>\\t<\/span>PROGRAM TO IMPLEMENT FLOYD'S ALGORITHM<\/span>\\t<\/span>*<\/span>\\n<\/span>"<\/span>;<\/span><\/span>\n\tcout <\/span><<<\/span> <\/span>"*********************************************************"<\/span>;<\/span><\/span>\n\tcout <\/span><<<\/span> <\/span>"<\/span>\\n<\/span>Enter the number of vertices<\/span>\\n<\/span>"<\/span>;<\/span><\/span>\n\tcin <\/span>>><\/span> iN;<\/span><\/span>\n\tcout <\/span><<<\/span> <\/span>"<\/span>\\n<\/span>Enter the Cost adjacency Matrix<\/span>\\n<\/span>"<\/span>;<\/span><\/span>\n\t<\/span>for<\/span>(i<\/span>=<\/span>0<\/span>;i<\/span><<\/span>iN;i<\/span>++<\/span>)<\/span><\/span>\n\t\t<\/span>for<\/span>(j<\/span>=<\/span>0<\/span>;j<\/span><<\/span>iN;j<\/span>++<\/span>)<\/span><\/span>\n\t\t\tcin <\/span>>><\/span> iaCost[i][j];<\/span><\/span>\n\tcout <\/span><<<\/span> <\/span>"<\/span>\\n<\/span>Input Graph<\/span>\\n<\/span>"<\/span>;<\/span><\/span>\n\t<\/span>for<\/span>(i<\/span>=<\/span>0<\/span>;i<\/span><<\/span>iN;i<\/span>++<\/span>)<\/span><\/span>\n\t{<\/span><\/span>\n\t\t<\/span>for<\/span>(j<\/span>=<\/span>0<\/span>;j<\/span><<\/span>iN;j<\/span>++<\/span>)<\/span><\/span>\n\t\t{<\/span><\/span>\n\t\t\tcout <\/span><<<\/span> iaCost[i][j] <\/span><<<\/span> <\/span>"<\/span>\\t<\/span>"<\/span>;<\/span><\/span>\n\t\t}<\/span><\/span>\n\t\tcout <\/span><<<\/span> endl;<\/span><\/span>\n\t}<\/span><\/span>\n\tcout <\/span><<<\/span> endl;<\/span><\/span>\n<\/span>\n\t<\/span>for<\/span>(i<\/span>=<\/span>0<\/span>;i<\/span><<\/span>iN;i<\/span>++<\/span>)<\/span><\/span>\n\t{<\/span><\/span>\n\t\t<\/span>for<\/span>(j<\/span>=<\/span>0<\/span>;j<\/span><<\/span>iN;j<\/span>++<\/span>)<\/span><\/span>\n\t\t{<\/span><\/span>\n\t\t\tiaFloyd[i][j] <\/span>=<\/span> iaCost[i][j];<\/span><\/span>\n\t\t}<\/span><\/span>\n\t}<\/span><\/span>\n<\/span>\n\t<\/span>for<\/span>(k<\/span>=<\/span>0<\/span>;k<\/span><<\/span>iN;k<\/span>++<\/span>)<\/span><\/span>\n\t{<\/span><\/span>\n\t\t<\/span>for<\/span>(i<\/span>=<\/span>0<\/span>;i<\/span><<\/span>iN;i<\/span>++<\/span>)<\/span><\/span>\n\t\t{<\/span><\/span>\n\t\t\t<\/span>for<\/span>(j<\/span>=<\/span>0<\/span>;j<\/span><<\/span>iN;j<\/span>++<\/span>)<\/span><\/span>\n\t\t\t{<\/span><\/span>\n\t\t\t\t<\/span>if<\/span>(iaFloyd[i][j] <\/span>><\/span> (iaFloyd[i][k] <\/span>+<\/span> iaFloyd[k][j]))<\/span><\/span>\n\t\t\t\t\tiaFloyd[i][j] <\/span>=<\/span> (iaFloyd[i][k] <\/span>+<\/span> iaFloyd[k][j]);<\/span><\/span>\n\t\t\t}<\/span><\/span>\n\t\t}<\/span><\/span>\n\t}<\/span><\/span>\n\tcout <\/span><<<\/span> <\/span>"<\/span>\\n<\/span>All Pair Shortest Path Matrix<\/span>\\n<\/span>"<\/span>;<\/span><\/span>\n\t<\/span>for<\/span>(i<\/span>=<\/span>0<\/span>;i<\/span><<\/span>iN;i<\/span>++<\/span>)<\/span><\/span>\n\t{<\/span><\/span>\n\t\t<\/span>for<\/span>(j<\/span>=<\/span>0<\/span>;j<\/span><<\/span>iN;j<\/span>++<\/span>)<\/span><\/span>\n\t\t{<\/span><\/span>\n\t\t\tcout <\/span><<<\/span> iaFloyd[i][j] <\/span><<<\/span> <\/span>"<\/span>\\t<\/span>"<\/span>;<\/span><\/span>\n\t\t}<\/span><\/span>\n\t\tcout <\/span><<<\/span> endl;<\/span><\/span>\n\t}<\/span><\/span>\n\tcout <\/span><<<\/span> <\/span>"<\/span>\\n<\/span>"<\/span>;<\/span><\/span>\n\t<\/span>return<\/span> <\/span>0<\/span>;<\/span><\/span>\n}<\/span><\/span><\/code><\/pre><\/div>\n\n\n\n
              Java Code<\/h4>\n\n\n\n
              <\/circle><\/circle><\/circle><\/g><\/svg><\/span><\/path><\/path><\/svg><\/span>
              import<\/span> java.util.Scanner;<\/span><\/span>\n<\/span>\npublic<\/span> <\/span>class<\/span> <\/span>FloydAlgorithm<\/span> {<\/span><\/span>\n    <\/span>public<\/span> <\/span>static<\/span> <\/span>void<\/span> <\/span>main<\/span>(<\/span>String<\/span>[] <\/span>args<\/span>) {<\/span><\/span>\n        <\/span>int<\/span> iN, i, j, k;<\/span><\/span>\n        <\/span>int<\/span>[][] iaFloyd <\/span>=<\/span> <\/span>new<\/span> <\/span>int<\/span>[<\/span>10<\/span>][<\/span>10<\/span>];<\/span><\/span>\n        <\/span>int<\/span>[][] iaCost <\/span>=<\/span> <\/span>new<\/span> <\/span>int<\/span>[<\/span>10<\/span>][<\/span>10<\/span>];<\/span><\/span>\n<\/span>\n        System.out.<\/span>println<\/span>(<\/span>"<\/span>\\n<\/span>*********************************************************"<\/span>);<\/span><\/span>\n        System.out.<\/span>println<\/span>(<\/span>"*<\/span>\\t<\/span>PROGRAM TO IMPLEMENT FLOYD'S ALGORITHM<\/span>\\t<\/span>*"<\/span>);<\/span><\/span>\n        System.out.<\/span>println<\/span>(<\/span>"*********************************************************"<\/span>);<\/span><\/span>\n        System.out.<\/span>println<\/span>(<\/span>"<\/span>\\n<\/span>Enter the number of vertices"<\/span>);<\/span><\/span>\n        Scanner scanner <\/span>=<\/span> <\/span>new<\/span> <\/span>Scanner<\/span>(System.in);<\/span><\/span>\n        iN <\/span>=<\/span> scanner.<\/span>nextInt<\/span>();<\/span><\/span>\n<\/span>\n        System.out.<\/span>println<\/span>(<\/span>"<\/span>\\n<\/span>Enter the Cost adjacency Matrix"<\/span>);<\/span><\/span>\n        <\/span>for<\/span> (i <\/span>=<\/span> <\/span>0<\/span>; i <\/span><<\/span> iN; i<\/span>++<\/span>) {<\/span><\/span>\n            <\/span>for<\/span> (j <\/span>=<\/span> <\/span>0<\/span>; j <\/span><<\/span> iN; j<\/span>++<\/span>) {<\/span><\/span>\n                iaCost[i][j] <\/span>=<\/span> scanner.<\/span>nextInt<\/span>();<\/span><\/span>\n            }<\/span><\/span>\n        }<\/span><\/span>\n        System.out.<\/span>println<\/span>(<\/span>"<\/span>\\n<\/span>Input Graph"<\/span>);<\/span><\/span>\n        <\/span>for<\/span> (i <\/span>=<\/span> <\/span>0<\/span>; i <\/span><<\/span> iN; i<\/span>++<\/span>) {<\/span><\/span>\n            <\/span>for<\/span> (j <\/span>=<\/span> <\/span>0<\/span>; j <\/span><<\/span> iN; j<\/span>++<\/span>) {<\/span><\/span>\n                System.out.<\/span>print<\/span>(iaCost[i][j] <\/span>+<\/span> <\/span>"<\/span>\\t<\/span>"<\/span>);<\/span><\/span>\n            }<\/span><\/span>\n            System.out.<\/span>println<\/span>();<\/span><\/span>\n        }<\/span><\/span>\n        System.out.<\/span>println<\/span>();<\/span><\/span>\n<\/span>\n        <\/span>for<\/span> (i <\/span>=<\/span> <\/span>0<\/span>; i <\/span><<\/span> iN; i<\/span>++<\/span>) {<\/span><\/span>\n            <\/span>for<\/span> (j <\/span>=<\/span> <\/span>0<\/span>; j <\/span><<\/span> iN; j<\/span>++<\/span>) {<\/span><\/span>\n                iaFloyd[i][j] <\/span>=<\/span> iaCost[i][j];<\/span><\/span>\n            }<\/span><\/span>\n        }<\/span><\/span>\n<\/span>\n        <\/span>for<\/span> (k <\/span>=<\/span> <\/span>0<\/span>; k <\/span><<\/span> iN; k<\/span>++<\/span>) {<\/span><\/span>\n            <\/span>for<\/span> (i <\/span>=<\/span> <\/span>0<\/span>; i <\/span><<\/span> iN; i<\/span>++<\/span>) {<\/span><\/span>\n                <\/span>for<\/span> (j <\/span>=<\/span> <\/span>0<\/span>; j <\/span><<\/span> iN; j<\/span>++<\/span>) {<\/span><\/span>\n                    <\/span>if<\/span> (iaFloyd[i][j] <\/span>><\/span> (iaFloyd[i][k] <\/span>+<\/span> iaFloyd[k][j]))<\/span><\/span>\n                        iaFloyd[i][j] <\/span>=<\/span> (iaFloyd[i][k] <\/span>+<\/span> iaFloyd[k][j]);<\/span><\/span>\n                }<\/span><\/span>\n            }<\/span><\/span>\n        }<\/span><\/span>\n<\/span>\n        System.out.<\/span>println<\/span>(<\/span>"<\/span>\\n<\/span>All Pair Shortest Path Matrix"<\/span>);<\/span><\/span>\n        <\/span>for<\/span> (i <\/span>=<\/span> <\/span>0<\/span>; i <\/span><<\/span> iN; i<\/span>++<\/span>) {<\/span><\/span>\n            <\/span>for<\/span> (j <\/span>=<\/span> <\/span>0<\/span>; j <\/span><<\/span> iN; j<\/span>++<\/span>) {<\/span><\/span>\n                System.out.<\/span>print<\/span>(iaFloyd[i][j] <\/span>+<\/span> <\/span>"<\/span>\\t<\/span>"<\/span>);<\/span><\/span>\n            }<\/span><\/span>\n            System.out.<\/span>println<\/span>();<\/span><\/span>\n        }<\/span><\/span>\n        System.out.<\/span>println<\/span>();<\/span><\/span>\n    }<\/span><\/span>\n}<\/span><\/span>\n<\/span><\/code><\/pre><\/div>\n\n\n\n
              Input Graph<\/h4>\n\n\n\n
              For this program lets consider the following graph<\/p>\n\n\n\n
              \"\"<\/a><\/figure>\n\n\n\n
              Output<\/h4>\n\n\n\n
              <\/circle><\/circle><\/circle><\/g><\/svg><\/span><\/path><\/path><\/svg><\/span>
              *********************************************************<\/span><\/span>\n*<\/span>\t<\/span>PROGRAM<\/span> <\/span>TO<\/span> <\/span>IMPLEMENT<\/span> <\/span>FLOYD<\/span>'S ALGORITHM\t<\/span>*<\/span><\/span>\n*********************************************************<\/span><\/span>\nEnter the number <\/span>of<\/span> vertices<\/span><\/span>\n5<\/span><\/span>\n<\/span>\nEnter the Cost adjacency Matrix<\/span><\/span>\n0<\/span> <\/span>3<\/span> <\/span>9999<\/span> <\/span>7<\/span> <\/span>9<\/span><\/span>\n3<\/span> <\/span>0<\/span> <\/span>4<\/span> <\/span>2<\/span> <\/span>9999<\/span><\/span>\n9999<\/span> <\/span>4<\/span> <\/span>0<\/span> <\/span>5<\/span> <\/span>6<\/span><\/span>\n7<\/span> <\/span>2<\/span> <\/span>5<\/span> <\/span>0<\/span> <\/span>4<\/span><\/span>\n9<\/span> <\/span>9999<\/span> <\/span>6<\/span> <\/span>4<\/span> <\/span>0<\/span><\/span>\n<\/span>\n<\/span>\nInput Graph<\/span><\/span>\n0<\/span>\t<\/span>3<\/span>\t<\/span>9999<\/span>\t<\/span>7<\/span>\t<\/span>9<\/span>\t<\/span><\/span>\n3<\/span>\t<\/span>0<\/span>\t<\/span>4<\/span>\t<\/span>2<\/span>\t<\/span>9999<\/span>\t<\/span><\/span>\n9999<\/span>\t<\/span>4<\/span>\t<\/span>0<\/span>\t<\/span>5<\/span>\t<\/span>6<\/span>\t<\/span><\/span>\n7<\/span>\t<\/span>2<\/span>\t<\/span>5<\/span>\t<\/span>0<\/span>\t<\/span>4<\/span>\t<\/span><\/span>\n9<\/span>\t<\/span>9999<\/span>\t<\/span>6<\/span>\t<\/span>4<\/span>\t<\/span>0<\/span>\t<\/span><\/span>\n<\/span>\n<\/span>\nAll Pair Shortest Path Matrix<\/span><\/span>\n0<\/span>\t<\/span>3<\/span>\t<\/span>7<\/span>\t<\/span>5<\/span>\t<\/span>9<\/span>\t<\/span><\/span>\n3<\/span>\t<\/span>0<\/span>\t<\/span>4<\/span>\t<\/span>2<\/span>\t<\/span>6<\/span>\t<\/span><\/span>\n7<\/span>\t<\/span>4<\/span>\t<\/span>0<\/span>\t<\/span>5<\/span>\t<\/span>6<\/span>\t<\/span><\/span>\n5<\/span>\t<\/span>2<\/span>\t<\/span>5<\/span>\t<\/span>0<\/span>\t<\/span>4<\/span>\t<\/span><\/span>\n9<\/span>\t<\/span>6<\/span>\t<\/span>6<\/span>\t<\/span>4<\/span>\t<\/span>0<\/span>\t<\/span><\/span>\n<\/span><\/code><\/pre><\/div>\n\n\n\n
              \n\n\n\n
              Travelling Sales Person Problem<\/h3>\n\n\n\n
              Write C++\/ Java programs to solve Travelling Sales Person problem using Dynamic programming.<\/p>\n\n\n\n
              C++ Code<\/h4>\n\n\n\n
              <\/circle><\/circle><\/circle><\/g><\/svg><\/span><\/path><\/path><\/svg><\/span>
              #include<\/span><<\/span>iostream<\/span>><\/span><\/span>\n#include<\/span><<\/span>iomanip<\/span>><\/span><\/span>\n <\/span><\/span>\nusing<\/span> <\/span>namespace<\/span> std;<\/span><\/span>\n <\/span><\/span>\nint cities[<\/span>10<\/span>][<\/span>10<\/span>],completed[<\/span>10<\/span>],n,cost<\/span>=<\/span>0<\/span>;<\/span><\/span>\n <\/span><\/span>\nvoid<\/span> <\/span>takeInput<\/span>()<\/span><\/span>\n{<\/span><\/span>\n\tint i,j;<\/span><\/span>\n\t <\/span><\/span>\n\tcout <\/span><<<\/span> <\/span>"Enter the number of cities: "<\/span>;<\/span><\/span>\n\tcin <\/span>>><\/span> n;<\/span><\/span>\n\t <\/span><\/span>\n\tcout <\/span><<<\/span> <\/span>"<\/span>\\n<\/span>Enter the Cost Matrix<\/span>\\n<\/span>"<\/span>;<\/span><\/span>\n\t <\/span><\/span>\n\t<\/span>for<\/span>(i<\/span>=<\/span>0<\/span>;i<\/span><<\/span>n;i<\/span>++<\/span>)<\/span><\/span>\n\t{<\/span><\/span>\n\t\t<\/span>for<\/span>(j<\/span>=<\/span>0<\/span>;j<\/span><<\/span>n;j<\/span>++<\/span>)<\/span><\/span>\n\t\t\tcin <\/span>>><\/span> cities[i][j];\t\t <\/span><\/span>\n\t\tcompleted[i]<\/span>=<\/span>0<\/span>;<\/span><\/span>\n\t}<\/span><\/span>\n\t <\/span><\/span>\n\tcout <\/span><<<\/span> <\/span>"<\/span>\\n\\n<\/span>The cost list is:"<\/span>;<\/span><\/span>\n\t <\/span><\/span>\n\t<\/span>for<\/span>( i<\/span>=<\/span>0<\/span>;i <\/span><<\/span> n;i<\/span>++<\/span>)<\/span><\/span>\n\t{<\/span><\/span>\n\t\tcout <\/span><<<\/span> endl;<\/span><\/span>\n\t\t<\/span>for<\/span>(j<\/span>=<\/span>0<\/span>;j <\/span><<\/span> n;j<\/span>++<\/span>)<\/span><\/span>\n\t\t\tcout <\/span><<<\/span> <\/span>"<\/span>\\t<\/span>"<\/span> <\/span><<<\/span> cities[i][j];<\/span><\/span>\n\t}<\/span><\/span>\n}<\/span><\/span>\n <\/span><\/span>\nint <\/span>least<\/span>(int c)<\/span><\/span>\n{<\/span><\/span>\n\tint i,nc<\/span>=<\/span>999<\/span>;<\/span><\/span>\n\tint min<\/span>=<\/span>999<\/span>,kmin;<\/span><\/span>\n\t <\/span><\/span>\n\t<\/span>for<\/span>(i<\/span>=<\/span>0<\/span>;i <\/span><<\/span> n;i<\/span>++<\/span>)<\/span><\/span>\n\t{<\/span><\/span>\n\t\t<\/span>if<\/span>((cities[c][i]<\/span>!=<\/span>0<\/span>)<\/span>&&<\/span>(completed[i]<\/span>==<\/span>0<\/span>))<\/span><\/span>\n\t\t{<\/span><\/span>\n\t\t\t<\/span>if<\/span>(cities[c][i]<\/span>+<\/span>cities[i][c] <\/span><<\/span> min)<\/span><\/span>\n\t\t\t{<\/span><\/span>\n\t\t\t\tmin<\/span>=<\/span>cities[i][<\/span>0<\/span>]<\/span>+<\/span>cities[c][i];<\/span><\/span>\n\t\t\t\tkmin<\/span>=<\/span>cities[c][i];<\/span><\/span>\n\t\t\t\tnc<\/span>=<\/span>i;<\/span><\/span>\n\t\t\t}\t\t<\/span><\/span>\n\t\t}<\/span><\/span>\n\t}\t <\/span><\/span>\n\t<\/span>if<\/span>(min<\/span>!=<\/span>999<\/span>)<\/span><\/span>\n\t\tcost<\/span>+=<\/span>kmin;<\/span><\/span>\n\t <\/span><\/span>\n\t<\/span>return<\/span> nc;<\/span><\/span>\n}<\/span><\/span>\n <\/span><\/span>\nvoid<\/span> <\/span>mincost<\/span>(int city)<\/span><\/span>\n{<\/span><\/span>\n\tint ncity;<\/span><\/span>\n\t <\/span><\/span>\n\tcompleted[city]<\/span>=<\/span>1<\/span>;<\/span><\/span>\n\t <\/span><\/span>\n\tcout <\/span><<<\/span> city <\/span><<<\/span> <\/span>"--->"<\/span>;<\/span><\/span>\n\tncity<\/span>=<\/span>least<\/span>(city);<\/span><\/span>\n\t <\/span><\/span>\n\t<\/span>if<\/span>(ncity<\/span>==<\/span>999<\/span>)<\/span><\/span>\n\t{<\/span><\/span>\n\t\tncity<\/span>=<\/span>0<\/span>;<\/span><\/span>\n\t\tcout <\/span><<<\/span> ncity;<\/span><\/span>\n\t\tcost<\/span>+=<\/span>cities[city][ncity];<\/span><\/span>\n\t\t <\/span><\/span>\n\t\t<\/span>return<\/span>;<\/span><\/span>\n\t}<\/span><\/span>\n\t <\/span><\/span>\n\t<\/span>mincost<\/span>(ncity);<\/span><\/span>\n}<\/span><\/span>\n <\/span><\/span>\nint <\/span>main<\/span>()<\/span><\/span>\n{<\/span><\/span>\n\t<\/span>takeInput<\/span>();<\/span><\/span>\n\t <\/span><\/span>\n\tcout <\/span><<<\/span> <\/span>"<\/span>\\n\\n<\/span>The Path is:<\/span>\\n<\/span>"<\/span>;<\/span><\/span>\n\t<\/span>mincost<\/span>(<\/span>0<\/span>); <\/span>\/\/passing 0 because starting vertex<\/span><\/span>\n\t <\/span><\/span>\n\tcout <\/span><<<\/span> <\/span>"<\/span>\\n\\n<\/span>Minimum cost is "<\/span> <\/span><<<\/span> cost <\/span><<<\/span> endl;<\/span><\/span>\n\t <\/span><\/span>\n\t<\/span>return<\/span> <\/span>0<\/span>;<\/span><\/span>\n}<\/span><\/span><\/code><\/pre><\/div>\n\n\n\n
              Java Code<\/h4>\n\n\n\n
              <\/circle><\/circle><\/circle><\/g><\/svg><\/span><\/path><\/path><\/svg><\/span>
              import<\/span> java.util.Scanner;<\/span><\/span>\n<\/span>\npublic<\/span> <\/span>class<\/span> <\/span>TravelingSalesmanProblem<\/span> {<\/span><\/span>\n    <\/span>private<\/span> <\/span>static<\/span> <\/span>int<\/span>[][] cities;<\/span><\/span>\n    <\/span>private<\/span> <\/span>static<\/span> <\/span>int<\/span>[] completed;<\/span><\/span>\n    <\/span>private<\/span> <\/span>static<\/span> <\/span>int<\/span> n;<\/span><\/span>\n    <\/span>private<\/span> <\/span>static<\/span> <\/span>int<\/span> cost;<\/span><\/span>\n<\/span>\n    <\/span>public<\/span> <\/span>static<\/span> <\/span>void<\/span> <\/span>main<\/span>(<\/span>String<\/span>[] <\/span>args<\/span>) {<\/span><\/span>\n        <\/span>takeInput<\/span>();<\/span><\/span>\n<\/span>\n        System.out.<\/span>println<\/span>(<\/span>"<\/span>\\n\\n<\/span>The Path is:"<\/span>);<\/span><\/span>\n        <\/span>minCost<\/span>(<\/span>0<\/span>); <\/span>\/\/ Start from vertex 0<\/span><\/span>\n<\/span>\n        System.out.<\/span>println<\/span>(<\/span>"<\/span>\\n\\n<\/span>Minimum cost is "<\/span> <\/span>+<\/span> cost);<\/span><\/span>\n    }<\/span><\/span>\n<\/span>\n    <\/span>private<\/span> <\/span>static<\/span> <\/span>void<\/span> <\/span>takeInput<\/span>() {<\/span><\/span>\n        Scanner scanner <\/span>=<\/span> <\/span>new<\/span> <\/span>Scanner<\/span>(System.in);<\/span><\/span>\n<\/span>\n        System.out.<\/span>print<\/span>(<\/span>"Enter the number of cities: "<\/span>);<\/span><\/span>\n        n <\/span>=<\/span> scanner.<\/span>nextInt<\/span>();<\/span><\/span>\n<\/span>\n        cities <\/span>=<\/span> <\/span>new<\/span> <\/span>int<\/span>[n][n];<\/span><\/span>\n        completed <\/span>=<\/span> <\/span>new<\/span> <\/span>int<\/span>[n];<\/span><\/span>\n<\/span>\n        System.out.<\/span>println<\/span>(<\/span>"<\/span>\\n<\/span>Enter the Cost Matrix"<\/span>);<\/span><\/span>\n<\/span>\n        <\/span>for<\/span> (<\/span>int<\/span> i <\/span>=<\/span> <\/span>0<\/span>; i <\/span><<\/span> n; i<\/span>++<\/span>) {<\/span><\/span>\n            <\/span>for<\/span> (<\/span>int<\/span> j <\/span>=<\/span> <\/span>0<\/span>; j <\/span><<\/span> n; j<\/span>++<\/span>)<\/span><\/span>\n                cities[i][j] <\/span>=<\/span> scanner.<\/span>nextInt<\/span>();<\/span><\/span>\n<\/span>\n            completed[i] <\/span>=<\/span> <\/span>0<\/span>;<\/span><\/span>\n        }<\/span><\/span>\n<\/span>\n        System.out.<\/span>println<\/span>(<\/span>"<\/span>\\n\\n<\/span>The cost list is:"<\/span>);<\/span><\/span>\n<\/span>\n        <\/span>for<\/span> (<\/span>int<\/span> i <\/span>=<\/span> <\/span>0<\/span>; i <\/span><<\/span> n; i<\/span>++<\/span>) {<\/span><\/span>\n            System.out.<\/span>println<\/span>();<\/span><\/span>\n            <\/span>for<\/span> (<\/span>int<\/span> j <\/span>=<\/span> <\/span>0<\/span>; j <\/span><<\/span> n; j<\/span>++<\/span>)<\/span><\/span>\n                System.out.<\/span>print<\/span>(<\/span>"<\/span>\\t<\/span>"<\/span> <\/span>+<\/span> cities[i][j]);<\/span><\/span>\n        }<\/span><\/span>\n    }<\/span><\/span>\n<\/span>\n    <\/span>private<\/span> <\/span>static<\/span> <\/span>int<\/span> <\/span>least<\/span>(<\/span>int<\/span> <\/span>c<\/span>) {<\/span><\/span>\n        <\/span>int<\/span> nc <\/span>=<\/span> <\/span>999<\/span>;<\/span><\/span>\n        <\/span>int<\/span> min <\/span>=<\/span> <\/span>999<\/span>;<\/span><\/span>\n        <\/span>int<\/span> kmin <\/span>=<\/span> <\/span>0<\/span>;<\/span><\/span>\n<\/span>\n        <\/span>for<\/span> (<\/span>int<\/span> i <\/span>=<\/span> <\/span>0<\/span>; i <\/span><<\/span> n; i<\/span>++<\/span>) {<\/span><\/span>\n            <\/span>if<\/span> (cities[c][i] <\/span>!=<\/span> <\/span>0<\/span> <\/span>&&<\/span> completed[i] <\/span>==<\/span> <\/span>0<\/span>) {<\/span><\/span>\n                <\/span>if<\/span> (cities[c][i] <\/span>+<\/span> cities[i][c] <\/span><<\/span> min) {<\/span><\/span>\n                    min <\/span>=<\/span> cities[i][<\/span>0<\/span>] <\/span>+<\/span> cities[c][i];<\/span><\/span>\n                    kmin <\/span>=<\/span> cities[c][i];<\/span><\/span>\n                    nc <\/span>=<\/span> i;<\/span><\/span>\n                }<\/span><\/span>\n            }<\/span><\/span>\n        }<\/span><\/span>\n<\/span>\n        <\/span>if<\/span> (min <\/span>!=<\/span> <\/span>999<\/span>)<\/span><\/span>\n            cost <\/span>+=<\/span> kmin;<\/span><\/span>\n<\/span>\n        <\/span>return<\/span> nc;<\/span><\/span>\n    }<\/span><\/span>\n<\/span>\n    <\/span>private<\/span> <\/span>static<\/span> <\/span>void<\/span> <\/span>minCost<\/span>(<\/span>int<\/span> <\/span>city<\/span>) {<\/span><\/span>\n        completed[city] <\/span>=<\/span> <\/span>1<\/span>;<\/span><\/span>\n<\/span>\n        System.out.<\/span>print<\/span>(city <\/span>+<\/span> <\/span>"--->"<\/span>);<\/span><\/span>\n<\/span>\n        <\/span>int<\/span> ncity <\/span>=<\/span> <\/span>least<\/span>(city);<\/span><\/span>\n<\/span>\n        <\/span>if<\/span> (ncity <\/span>==<\/span> <\/span>999<\/span>) {<\/span><\/span>\n            ncity <\/span>=<\/span> <\/span>0<\/span>;<\/span><\/span>\n            System.out.<\/span>print<\/span>(ncity);<\/span><\/span>\n            cost <\/span>+=<\/span> cities[city][ncity];<\/span><\/span>\n            <\/span>return<\/span>;<\/span><\/span>\n        }<\/span><\/span>\n<\/span>\n        <\/span>minCost<\/span>(ncity);<\/span><\/span>\n    }<\/span><\/span>\n}<\/span><\/span>\n<\/span><\/code><\/pre><\/div>\n\n\n\n
              Input Graph<\/h4>\n\n\n\n
              For this program lets consider the following graph<\/p>\n\n\n\n
              \"\"<\/a><\/figure>\n\n\n\n
              Output<\/h4>\n\n\n\n
              <\/circle><\/circle><\/circle><\/g><\/svg><\/span><\/path><\/path><\/svg><\/span>
              Enter the number <\/span>of<\/span> <\/span>cities<\/span>: <\/span>5<\/span><\/span>\n<\/span>\nEnter the Cost Matrix<\/span><\/span>\n0<\/span> <\/span>3<\/span> <\/span>1<\/span> <\/span>7<\/span> <\/span>9<\/span><\/span>\n3<\/span> <\/span>0<\/span> <\/span>4<\/span> <\/span>2<\/span> <\/span>5<\/span><\/span>\n1<\/span> <\/span>4<\/span> <\/span>0<\/span> <\/span>5<\/span> <\/span>6<\/span><\/span>\n7<\/span> <\/span>2<\/span> <\/span>5<\/span> <\/span>0<\/span> <\/span>4<\/span><\/span>\n9<\/span> <\/span>5<\/span> <\/span>6<\/span> <\/span>4<\/span> <\/span>0<\/span><\/span>\n<\/span>\n<\/span>\nThe cost list <\/span>is<\/span>:<\/span><\/span>\n\t<\/span>0<\/span>\t<\/span>3<\/span>\t<\/span>1<\/span>\t<\/span>7<\/span>\t<\/span>9<\/span><\/span>\n\t<\/span>3<\/span>\t<\/span>0<\/span>\t<\/span>4<\/span>\t<\/span>2<\/span>\t<\/span>5<\/span><\/span>\n\t<\/span>1<\/span>\t<\/span>4<\/span>\t<\/span>0<\/span>\t<\/span>5<\/span>\t<\/span>6<\/span><\/span>\n\t<\/span>7<\/span>\t<\/span>2<\/span>\t<\/span>5<\/span>\t<\/span>0<\/span>\t<\/span>4<\/span><\/span>\n\t<\/span>9<\/span>\t<\/span>5<\/span>\t<\/span>6<\/span>\t<\/span>4<\/span>\t<\/span>0<\/span><\/span>\n<\/span>\nThe Path <\/span>is<\/span>:<\/span><\/span>\n0<\/span>---><\/span>2<\/span>---><\/span>1<\/span>---><\/span>3<\/span>---><\/span>4<\/span>---><\/span>0<\/span><\/span>\n<\/span>\nMinimum cost is <\/span>20<\/span><\/span>\n<\/span><\/code><\/pre><\/div>\n\n\n\n
              Minimum Cost Tour<\/h4>\n\n\n\n
              \"\"<\/a><\/figure>\n\n\n\n
              0\/1 Knapsack problem<\/h3>\n\n\n\n
              Write C++\/ Java programs to solve 0\/1 Knapsack problem using Dynamic Programming method.<\/p>\n\n\n\n
              C++ Code<\/h4>\n\n\n\n
              <\/circle><\/circle><\/circle><\/g><\/svg><\/span><\/path><\/path><\/svg><\/span>
              \/********************************************************************************<\/span><\/span>\n*File\t\t: 10AKnapsack.cpp<\/span><\/span>\n*Description: Program to find Binomial Coefficient<\/span><\/span>\n*Author\t\t: Prabodh C P<\/span><\/span>\n*Compiler\t: g++ compiler 7.5.0, Ubuntu 18.04<\/span><\/span>\n*Date\t\t: 31 Mar 2020<\/span><\/span>\n********************************************************************************\/<\/span><\/span>\n#include <\/span><<\/span>iostream<\/span>><\/span><\/span>\n#include <\/span><<\/span>vector<\/span>><\/span><\/span>\nusing<\/span> <\/span>namespace<\/span> std;<\/span><\/span>\n<\/span>\nconst<\/span> <\/span>int<\/span> MAX <\/span>=<\/span> <\/span>10<\/span>;<\/span><\/span>\n<\/span>\ninline int <\/span>max<\/span>(int x, int y)<\/span><\/span>\n{<\/span><\/span>\n    <\/span>return<\/span> (x<\/span>><\/span>y)<\/span>?<\/span>x<\/span>:<\/span>y;<\/span><\/span>\n}<\/span><\/span>\nclass<\/span> <\/span>Knapsack<\/span><\/span>\n{<\/span><\/span>\n    int <\/span>totalProfit<\/span>;<\/span><\/span>\n    int weight[<\/span>MAX<\/span>];<\/span><\/span>\n    int profit[<\/span>MAX<\/span>];<\/span><\/span>\n    int <\/span>capacity<\/span>;<\/span><\/span>\n    int <\/span>numOfObj<\/span>;<\/span><\/span>\n    int subset[<\/span>MAX<\/span>];<\/span><\/span>\n    int table[<\/span>MAX<\/span>][<\/span>MAX<\/span>];<\/span><\/span>\n<\/span>\n    <\/span>public<\/span>:<\/span><\/span>\n    <\/span>Knapsack<\/span>();<\/span><\/span>\n    <\/span>void<\/span> <\/span>fnReadKnapDetails<\/span>();<\/span><\/span>\n    <\/span>void<\/span> <\/span>fnCalcProfit<\/span>();<\/span><\/span>\n    <\/span>void<\/span> <\/span>fnFindSubSet<\/span>();<\/span><\/span>\n};<\/span><\/span>\n<\/span>\nvoid<\/span> <\/span>Knapsack<\/span>::<\/span>fnReadKnapDetails<\/span>()<\/span><\/span>\n{<\/span><\/span>\n    int i;<\/span><\/span>\n    cout <\/span><<<\/span> <\/span>"Enter the maxium number of objects : "<\/span>;<\/span><\/span>\n    cin <\/span>>><\/span> numOfObj;<\/span><\/span>\n<\/span>\n    cout <\/span><<<\/span> <\/span>"Enter the weights : <\/span>\\n<\/span>"<\/span>;<\/span><\/span>\n    <\/span>for<\/span> (i<\/span>=<\/span>1<\/span>; i<\/span><=<\/span>numOfObj; i<\/span>++<\/span>)<\/span><\/span>\n    {<\/span><\/span>\n        cout <\/span><<<\/span> <\/span>"<\/span>\\n<\/span>Weight "<\/span> <\/span><<<\/span> i <\/span><<<\/span> <\/span>": "<\/span>;<\/span><\/span>\n        cin <\/span>>><\/span> weight[i];<\/span><\/span>\n    }<\/span><\/span>\n    cout <\/span><<<\/span> <\/span>"<\/span>\\n<\/span>Enter the profits : <\/span>\\n<\/span>"<\/span>;<\/span><\/span>\n    <\/span>for<\/span> (i<\/span>=<\/span>1<\/span>; i<\/span><=<\/span>numOfObj; i<\/span>++<\/span>)<\/span><\/span>\n    {<\/span><\/span>\n        cout <\/span><<<\/span> <\/span>"<\/span>\\n<\/span>Profit "<\/span> <\/span><<<\/span> i <\/span><<<\/span> <\/span>": "<\/span>;<\/span><\/span>\n        cin <\/span>>><\/span> profit[i];<\/span><\/span>\n    }<\/span><\/span>\n    cout <\/span><<<\/span> <\/span>"<\/span>\\n<\/span>Enter the maximum capacity : "<\/span>;<\/span><\/span>\n    cin <\/span>>><\/span> capacity;<\/span><\/span>\n}<\/span><\/span>\n<\/span>\nKnapsack<\/span> :: <\/span>Knapsack<\/span>()<\/span><\/span>\n{<\/span><\/span>\n    int i;<\/span><\/span>\n    totalProfit <\/span>=<\/span> <\/span>0<\/span>;<\/span><\/span>\n    <\/span>for<\/span>( i<\/span>=<\/span>1<\/span>; i<\/span><=<\/span>numOfObj; i<\/span>++<\/span>)<\/span><\/span>\n        subset[i] <\/span>=<\/span> <\/span>0<\/span>;<\/span><\/span>\n}<\/span><\/span>\nvoid<\/span> <\/span>Knapsack<\/span>::<\/span>fnCalcProfit<\/span>()<\/span><\/span>\n{<\/span><\/span>\n    int i,j;<\/span><\/span>\n    <\/span>for<\/span> (j<\/span>=<\/span>0<\/span>; j<\/span><=<\/span>capacity; j<\/span>++<\/span>)<\/span><\/span>\n        table[<\/span>0<\/span>][j] <\/span>=<\/span> <\/span>0<\/span>;<\/span><\/span>\n    <\/span>for<\/span> (i<\/span>=<\/span>0<\/span>; i<\/span><=<\/span>numOfObj; i<\/span>++<\/span>)<\/span><\/span>\n        table[i][<\/span>0<\/span>] <\/span>=<\/span> <\/span>0<\/span>;<\/span><\/span>\n    <\/span>for<\/span> (i<\/span>=<\/span>1<\/span>; i<\/span><=<\/span>numOfObj; i<\/span>++<\/span>)<\/span><\/span>\n    {<\/span><\/span>\n        <\/span>for<\/span> (j<\/span>=<\/span>1<\/span>; j<\/span><=<\/span>capacity; j<\/span>++<\/span>)<\/span><\/span>\n        {<\/span><\/span>\n            <\/span>if<\/span> (j<\/span>-<\/span>weight[i] <\/span><<\/span> <\/span>0<\/span>)<\/span><\/span>\n                table[i][j] <\/span>=<\/span> table[i<\/span>-<\/span>1<\/span>][j];<\/span><\/span>\n            <\/span>else<\/span><\/span>\n                table[i][j] <\/span>=<\/span> <\/span>max<\/span>(table[i<\/span>-<\/span>1<\/span>][j], profit[i] <\/span>+<\/span> table[i<\/span>-<\/span>1<\/span>][j<\/span>-<\/span>weight[i]]);<\/span><\/span>\n        }<\/span><\/span>\n    }<\/span><\/span>\n    totalProfit <\/span>=<\/span> table[numOfObj][capacity];<\/span><\/span>\n}<\/span><\/span>\n<\/span>\nvoid<\/span> <\/span>Knapsack<\/span>::<\/span>fnFindSubSet<\/span>()<\/span><\/span>\n{<\/span><\/span>\n    int i,j;<\/span><\/span>\n    i <\/span>=<\/span> numOfObj;<\/span><\/span>\n    j <\/span>=<\/span> capacity;<\/span><\/span>\n    <\/span>while<\/span> (i <\/span>>=<\/span> <\/span>1<\/span> <\/span>&&<\/span> j <\/span>>=<\/span> <\/span>1<\/span>)<\/span><\/span>\n    {<\/span><\/span>\n        <\/span>if<\/span> (table[i][j] <\/span>!=<\/span> table[i<\/span>-<\/span>1<\/span>][j])<\/span><\/span>\n        {<\/span><\/span>\n            subset[i] <\/span>=<\/span> <\/span>1<\/span>;<\/span><\/span>\n            j <\/span>=<\/span> j <\/span>-<\/span> weight[i];<\/span><\/span>\n        }<\/span><\/span>\n        i<\/span>--<\/span>;<\/span><\/span>\n    }<\/span><\/span>\n<\/span>\n    cout <\/span><<<\/span> <\/span>"Items selected for the Knapsack are : "<\/span> ;<\/span><\/span>\n    <\/span>for<\/span>(i<\/span>=<\/span>1<\/span>;i<\/span><=<\/span>numOfObj;i<\/span>++<\/span>)<\/span><\/span>\n    {<\/span><\/span>\n        <\/span>if<\/span>(subset[i] <\/span>==<\/span> <\/span>1<\/span>)<\/span><\/span>\n        cout <\/span><<<\/span> i <\/span><<<\/span> <\/span>" "<\/span>;<\/span><\/span>\n    }<\/span><\/span>\n    cout <\/span><<<\/span> endl;<\/span><\/span>\n    cout <\/span><<<\/span> <\/span>"Total Profit earned is "<\/span> <\/span><<<\/span> totalProfit <\/span><<<\/span> endl;<\/span><\/span>\n}<\/span><\/span>\nint <\/span>main<\/span>()<\/span><\/span>\n{<\/span><\/span>\n    Knapsack knapsackObj;<\/span><\/span>\n<\/span>\n    knapsackObj.<\/span>fnReadKnapDetails<\/span>();<\/span><\/span>\n    knapsackObj.<\/span>fnCalcProfit<\/span>();<\/span><\/span>\n    knapsackObj.<\/span>fnFindSubSet<\/span>();<\/span><\/span>\n    <\/span>return<\/span> <\/span>0<\/span>;<\/span><\/span>\n}<\/span><\/span>\n<\/span><\/code><\/pre><\/div>\n\n\n\n
              Java Code<\/h4>\n\n\n\n
              <\/circle><\/circle><\/circle><\/g><\/svg><\/span><\/path><\/path><\/svg><\/span>
              import<\/span> java.util.Scanner;<\/span><\/span>\n<\/span>\nclass<\/span> <\/span>Knapsack<\/span> {<\/span><\/span>\n    <\/span>private<\/span> <\/span>int<\/span> totalProfit;<\/span><\/span>\n    <\/span>private<\/span> <\/span>int<\/span>[] weight;<\/span><\/span>\n    <\/span>private<\/span> <\/span>int<\/span>[] profit;<\/span><\/span>\n    <\/span>private<\/span> <\/span>int<\/span> capacity;<\/span><\/span>\n    <\/span>private<\/span> <\/span>int<\/span> numOfObj;<\/span><\/span>\n    <\/span>private<\/span> <\/span>int<\/span>[] subset;<\/span><\/span>\n    <\/span>private<\/span> <\/span>int<\/span>[][] table;<\/span><\/span>\n<\/span>\n    <\/span>public<\/span> <\/span>Knapsack<\/span>() {<\/span><\/span>\n        totalProfit <\/span>=<\/span> <\/span>0<\/span>;<\/span><\/span>\n    }<\/span><\/span>\n<\/span>\n    <\/span>public<\/span> <\/span>void<\/span> <\/span>fnReadKnapDetails<\/span>() {<\/span><\/span>\n        Scanner scanner <\/span>=<\/span> <\/span>new<\/span> <\/span>Scanner<\/span>(System.in);<\/span><\/span>\n<\/span>\n        System.out.<\/span>print<\/span>(<\/span>"Enter the maximum number of objects: "<\/span>);<\/span><\/span>\n        numOfObj <\/span>=<\/span> scanner.<\/span>nextInt<\/span>();<\/span><\/span>\n<\/span>\n        weight <\/span>=<\/span> <\/span>new<\/span> <\/span>int<\/span>[numOfObj <\/span>+<\/span> <\/span>1<\/span>];<\/span><\/span>\n        profit <\/span>=<\/span> <\/span>new<\/span> <\/span>int<\/span>[numOfObj <\/span>+<\/span> <\/span>1<\/span>];<\/span><\/span>\n<\/span>\n        System.out.<\/span>println<\/span>(<\/span>"<\/span>\\n<\/span>Enter the weights:"<\/span>);<\/span><\/span>\n        <\/span>for<\/span> (<\/span>int<\/span> i <\/span>=<\/span> <\/span>1<\/span>; i <\/span><=<\/span> numOfObj; i<\/span>++<\/span>) {<\/span><\/span>\n            System.out.<\/span>print<\/span>(<\/span>"Weight "<\/span> <\/span>+<\/span> i <\/span>+<\/span> <\/span>": "<\/span>);<\/span><\/span>\n            weight[i] <\/span>=<\/span> scanner.<\/span>nextInt<\/span>();<\/span><\/span>\n        }<\/span><\/span>\n<\/span>\n        System.out.<\/span>println<\/span>(<\/span>"<\/span>\\n<\/span>Enter the profits:"<\/span>);<\/span><\/span>\n        <\/span>for<\/span> (<\/span>int<\/span> i <\/span>=<\/span> <\/span>1<\/span>; i <\/span><=<\/span> numOfObj; i<\/span>++<\/span>) {<\/span><\/span>\n            System.out.<\/span>print<\/span>(<\/span>"Profit "<\/span> <\/span>+<\/span> i <\/span>+<\/span> <\/span>": "<\/span>);<\/span><\/span>\n            profit[i] <\/span>=<\/span> scanner.<\/span>nextInt<\/span>();<\/span><\/span>\n        }<\/span><\/span>\n<\/span>\n        System.out.<\/span>print<\/span>(<\/span>"<\/span>\\n<\/span>Enter the maximum capacity: "<\/span>);<\/span><\/span>\n        capacity <\/span>=<\/span> scanner.<\/span>nextInt<\/span>();<\/span><\/span>\n<\/span>\n        subset <\/span>=<\/span> <\/span>new<\/span> <\/span>int<\/span>[numOfObj <\/span>+<\/span> <\/span>1<\/span>];<\/span><\/span>\n        table <\/span>=<\/span> <\/span>new<\/span> <\/span>int<\/span>[numOfObj <\/span>+<\/span> <\/span>1<\/span>][capacity <\/span>+<\/span> <\/span>1<\/span>];<\/span><\/span>\n    }<\/span><\/span>\n<\/span>\n    <\/span>private<\/span> <\/span>int<\/span> <\/span>max<\/span>(<\/span>int<\/span> <\/span>x<\/span>, <\/span>int<\/span> <\/span>y<\/span>) {<\/span><\/span>\n        <\/span>return<\/span> (x <\/span>><\/span> y) <\/span>?<\/span> x <\/span>:<\/span> y;<\/span><\/span>\n    }<\/span><\/span>\n<\/span>\n    <\/span>public<\/span> <\/span>void<\/span> <\/span>fnCalcProfit<\/span>() {<\/span><\/span>\n        <\/span>for<\/span> (<\/span>int<\/span> j <\/span>=<\/span> <\/span>0<\/span>; j <\/span><=<\/span> capacity; j<\/span>++<\/span>)<\/span><\/span>\n            table[<\/span>0<\/span>][j] <\/span>=<\/span> <\/span>0<\/span>;<\/span><\/span>\n<\/span>\n        <\/span>for<\/span> (<\/span>int<\/span> i <\/span>=<\/span> <\/span>0<\/span>; i <\/span><=<\/span> numOfObj; i<\/span>++<\/span>)<\/span><\/span>\n            table[i][<\/span>0<\/span>] <\/span>=<\/span> <\/span>0<\/span>;<\/span><\/span>\n<\/span>\n        <\/span>for<\/span> (<\/span>int<\/span> i <\/span>=<\/span> <\/span>1<\/span>; i <\/span><=<\/span> numOfObj; i<\/span>++<\/span>) {<\/span><\/span>\n            <\/span>for<\/span> (<\/span>int<\/span> j <\/span>=<\/span> <\/span>1<\/span>; j <\/span><=<\/span> capacity; j<\/span>++<\/span>) {<\/span><\/span>\n                <\/span>if<\/span> (j <\/span>-<\/span> weight[i] <\/span><<\/span> <\/span>0<\/span>)<\/span><\/span>\n                    table[i][j] <\/span>=<\/span> table[i <\/span>-<\/span> <\/span>1<\/span>][j];<\/span><\/span>\n                <\/span>else<\/span><\/span>\n                    table[i][j] <\/span>=<\/span> <\/span>max<\/span>(table[i <\/span>-<\/span> <\/span>1<\/span>][j], profit[i] <\/span>+<\/span> table[i <\/span>-<\/span> <\/span>1<\/span>][j <\/span>-<\/span> weight[i]]);<\/span><\/span>\n            }<\/span><\/span>\n        }<\/span><\/span>\n<\/span>\n        totalProfit <\/span>=<\/span> table[numOfObj][capacity];<\/span><\/span>\n    }<\/span><\/span>\n<\/span>\n    <\/span>public<\/span> <\/span>void<\/span> <\/span>fnFindSubSet<\/span>() {<\/span><\/span>\n        <\/span>int<\/span> i <\/span>=<\/span> numOfObj;<\/span><\/span>\n        <\/span>int<\/span> j <\/span>=<\/span> capacity;<\/span><\/span>\n<\/span>\n        <\/span>while<\/span> (i <\/span>>=<\/span> <\/span>1<\/span> <\/span>&&<\/span> j <\/span>>=<\/span> <\/span>1<\/span>) {<\/span><\/span>\n            <\/span>if<\/span> (table[i][j] <\/span>!=<\/span> table[i <\/span>-<\/span> <\/span>1<\/span>][j]) {<\/span><\/span>\n                subset[i] <\/span>=<\/span> <\/span>1<\/span>;<\/span><\/span>\n                j <\/span>=<\/span> j <\/span>-<\/span> weight[i];<\/span><\/span>\n            }<\/span><\/span>\n            i<\/span>--<\/span>;<\/span><\/span>\n        }<\/span><\/span>\n<\/span>\n        System.out.<\/span>print<\/span>(<\/span>"Items selected for the Knapsack are: "<\/span>);<\/span><\/span>\n        <\/span>for<\/span> (i <\/span>=<\/span> <\/span>1<\/span>; i <\/span><=<\/span> numOfObj; i<\/span>++<\/span>) {<\/span><\/span>\n            <\/span>if<\/span> (subset[i] <\/span>==<\/span> <\/span>1<\/span>)<\/span><\/span>\n                System.out.<\/span>print<\/span>(i <\/span>+<\/span> <\/span>" "<\/span>);<\/span><\/span>\n        }<\/span><\/span>\n        System.out.<\/span>println<\/span>();<\/span><\/span>\n        System.out.<\/span>println<\/span>(<\/span>"Total Profit earned is "<\/span> <\/span>+<\/span> totalProfit);<\/span><\/span>\n    }<\/span><\/span>\n<\/span>\n    <\/span>public<\/span> <\/span>static<\/span> <\/span>void<\/span> <\/span>main<\/span>(<\/span>String<\/span>[] <\/span>args<\/span>) {<\/span><\/span>\n        Knapsack knapsackObj <\/span>=<\/span> <\/span>new<\/span> <\/span>Knapsack<\/span>();<\/span><\/span>\n<\/span>\n        knapsackObj.<\/span>fnReadKnapDetails<\/span>();<\/span><\/span>\n        knapsackObj.<\/span>fnCalcProfit<\/span>();<\/span><\/span>\n        knapsackObj.<\/span>fnFindSubSet<\/span>();<\/span><\/span>\n    }<\/span><\/span>\n}<\/span><\/span>\n<\/span><\/code><\/pre><\/div>\n\n\n\n
              Input Sample<\/h4>\n\n\n\n
              Lets consider this sample input for the 0\/1 Knapsack Problem.<\/p>\n\n\n\n
              Knapsack Capacity : 5<\/strong><\/p>\n\n\n\n
              Item<\/strong><\/td>Weight<\/strong><\/td>Profit<\/strong><\/td><\/tr>
              1<\/td>2<\/td>12<\/td><\/tr>
              2<\/td>1<\/td>10<\/td><\/tr>
              3<\/td>3<\/td>20<\/td><\/tr>
              4<\/td>2<\/td>15<\/td><\/tr><\/tbody><\/table><\/figure>\n\n\n\n
              Output<\/h4>\n\n\n\n
              <\/circle><\/circle><\/circle><\/g><\/svg><\/span><\/path><\/path><\/svg><\/span>
              Enter the maxium number <\/span>of<\/span> <\/span>objects<\/span> : <\/span>4<\/span><\/span>\nEnter the <\/span>weights<\/span> : <\/span><\/span>\n<\/span>\nWeight <\/span>1<\/span>: <\/span>2<\/span><\/span>\n<\/span>\nWeight <\/span>2<\/span>: <\/span>1<\/span><\/span>\n<\/span>\nWeight <\/span>3<\/span>: <\/span>3<\/span><\/span>\n<\/span>\nWeight <\/span>4<\/span>: <\/span>2<\/span><\/span>\n<\/span>\nEnter the <\/span>profits<\/span> : <\/span><\/span>\n<\/span>\nProfit <\/span>1<\/span>: <\/span>12<\/span><\/span>\n<\/span>\nProfit <\/span>2<\/span>: <\/span>10<\/span><\/span>\n<\/span>\nProfit <\/span>3<\/span>: <\/span>20<\/span><\/span>\n<\/span>\nProfit <\/span>4<\/span>: <\/span>15<\/span><\/span>\n<\/span>\nEnter the maximum <\/span>capacity<\/span> : <\/span>5<\/span><\/span>\nItems selected for the Knapsack <\/span>are<\/span> : <\/span>1<\/span> <\/span>2<\/span> <\/span>4<\/span> <\/span><\/span>\nTotal Profit earned is <\/span>37<\/span><\/span>\n<\/span><\/code><\/pre><\/div>\n\n\n\n
              Module 5<\/h2>\n\n\n\n
              Subset Sum Problem<\/h3>\n\n\n\n
              Design and implement C++\/Java Program to find a subset of a given set S = {S1<\/sub>, S2<\/sub>,\u2026, Sn<\/sub>} of n positive integers whose SUM is equal to a given positive integer d. For example, if S = {1, 2, 5, 6, 8} and d= 9, there are two solutions {1, 2, 6} and {1, 8}. Display a suitable message, if the given problem instance doesn’t have a solution.<\/p>\n\n\n\n
              C++ Code<\/h4>\n\n\n\n
              <\/circle><\/circle><\/circle><\/g><\/svg><\/span><\/path><\/path><\/svg><\/span>
              \/******************************************************<\/span><\/span>\n*File\t\t: 11SubsetSum.cpp<\/span><\/span>\n*Description: Program to solve Subset sum problem.<\/span><\/span>\n*Author\t\t: Prabodh C P<\/span><\/span>\n*Compiler\t: g++ compiler 7.5.0, Ubuntu 18.04<\/span><\/span>\n*Date\t\t: 31 Mar 2020<\/span><\/span>\n******************************************************\/<\/span><\/span>\n#include <\/span><<\/span>iostream<\/span>><\/span><\/span>\nusing<\/span> <\/span>namespace<\/span> std;<\/span><\/span>\n\/\/ Constant definitions<\/span><\/span>\nconst<\/span> <\/span>int<\/span> MAX <\/span>=<\/span> <\/span>100<\/span>;<\/span><\/span>\n\/\/ class definitions<\/span><\/span>\nclass<\/span> <\/span>SubSet<\/span><\/span>\n{<\/span><\/span>\n\tint stk[<\/span>MAX<\/span>], <\/span>set<\/span>[<\/span>MAX<\/span>];<\/span><\/span>\n\tint <\/span>size<\/span>, <\/span>top<\/span>, <\/span>count<\/span>;<\/span><\/span>\n\t<\/span>public<\/span>:<\/span><\/span>\n\t<\/span>SubSet<\/span>()<\/span><\/span>\n\t{<\/span><\/span>\n\t\t<\/span>top<\/span> <\/span>=<\/span> <\/span>-<\/span>1<\/span>;<\/span><\/span>\n\t\t<\/span>count<\/span> <\/span>=<\/span> <\/span>0<\/span>;<\/span><\/span>\n\t}<\/span><\/span>\n\t<\/span>void<\/span> <\/span>getInfo<\/span>(<\/span>void<\/span>);<\/span><\/span>\n\t<\/span>void<\/span> <\/span>push<\/span>(<\/span>int<\/span> <\/span>data<\/span>);<\/span><\/span>\n\t<\/span>void<\/span> <\/span>pop<\/span>(<\/span>void<\/span>);<\/span><\/span>\n\t<\/span>void<\/span> <\/span>display<\/span>(<\/span>void<\/span>);<\/span><\/span>\n\tint <\/span>fnFindSubset<\/span>(<\/span>int<\/span> <\/span>pos<\/span>, <\/span>int<\/span> <\/span>sum<\/span>);<\/span><\/span>\n};<\/span><\/span>\n\/******************************************************<\/span><\/span>\n*Function\t: getInfo<\/span><\/span>\n*Description: Function to read input<\/span><\/span>\n*Input parameters: no parameters<\/span><\/span>\n*RETURNS\t: no value<\/span><\/span>\n******************************************************\/<\/span><\/span>\nvoid<\/span> <\/span>SubSet<\/span> :: <\/span>getInfo<\/span>(<\/span>void<\/span>)<\/span><\/span>\n{<\/span><\/span>\n\tint i;<\/span><\/span>\n\tcout <\/span><<<\/span> <\/span>"Enter the maximum number of elements : "<\/span>;<\/span><\/span>\n\tcin <\/span>>><\/span> size;<\/span><\/span>\n\tcout <\/span><<<\/span> <\/span>"Enter the values of the elements : <\/span>\\n<\/span>"<\/span>;<\/span><\/span>\n\t<\/span>for<\/span> (i<\/span>=<\/span>1<\/span>; i<\/span><=<\/span>size; i<\/span>++<\/span>)<\/span><\/span>\n\tcin <\/span>>><\/span> set[i];<\/span><\/span>\n}<\/span><\/span>\n\/******************************************************<\/span><\/span>\n*Function\t: push<\/span><\/span>\n*Description: Function to push an element on to the stack<\/span><\/span>\n*Input parameters:<\/span><\/span>\n*int data\t- value to be pushed on to the stack<\/span><\/span>\n*RETURNS\t: no value<\/span><\/span>\n******************************************************\/<\/span><\/span>\nvoid<\/span> <\/span>SubSet<\/span> :: <\/span>push<\/span>(int data)<\/span><\/span>\n{<\/span><\/span>\n\tstk[<\/span>++<\/span>top] <\/span>=<\/span> data;<\/span><\/span>\n}<\/span><\/span>\n\/******************************************************<\/span><\/span>\n*Function\t: pop<\/span><\/span>\n*Description: Function to pop an element from the stack<\/span><\/span>\n*Input parameters: no parameters<\/span><\/span>\n*RETURNS\t: no value<\/span><\/span>\n******************************************************\/<\/span><\/span>\nvoid<\/span> <\/span>SubSet<\/span> :: <\/span>pop<\/span>(<\/span>void<\/span>)<\/span><\/span>\n{<\/span><\/span>\n\ttop<\/span>--<\/span>;<\/span><\/span>\n}<\/span><\/span>\n\/******************************************************<\/span><\/span>\n*Function\t: display<\/span><\/span>\n*Description: Function to display solution to sub set sum problem<\/span><\/span>\n*Input parameters: no parameters<\/span><\/span>\n*RETURNS\t: no value<\/span><\/span>\n******************************************************\/<\/span><\/span>\nvoid<\/span> <\/span>SubSet<\/span> :: <\/span>display<\/span>()<\/span><\/span>\n{<\/span><\/span>\n\tint i;<\/span><\/span>\n\tcout <\/span><<<\/span> <\/span>"<\/span>\\n<\/span>SOLUTION #"<\/span><<<\/span> <\/span>++<\/span>count <\/span><<<\/span>" IS<\/span>\\n<\/span>{ "<\/span>;<\/span><\/span>\n\t<\/span>for<\/span> (i<\/span>=<\/span>0<\/span>; i<\/span><=<\/span>top; i<\/span>++<\/span>)<\/span><\/span>\n\t\tcout <\/span><<<\/span> stk[i] <\/span><<<\/span> <\/span>" "<\/span>;<\/span><\/span>\n\tcout <\/span><<<\/span> <\/span>"}"<\/span> <\/span><<<\/span> endl;<\/span><\/span>\n}<\/span><\/span>\n\/******************************************************<\/span><\/span>\n*Function\t: fnFindSubset<\/span><\/span>\n*Description\t: Function to solve Subset sum problem.<\/span><\/span>\n*Input parameters:<\/span><\/span>\n*\tint pos\t- position<\/span><\/span>\n*\tint sum\t- sum of elements<\/span><\/span>\n*RETURNS\t: returns 1 if solution exists or zero otherwise<\/span><\/span>\n******************************************************\/<\/span><\/span>\nint <\/span>SubSet<\/span> :: <\/span>fnFindSubset<\/span>(int pos, int sum)<\/span><\/span>\n{<\/span><\/span>\n\tint i;<\/span><\/span>\n\tstatic int foundSoln <\/span>=<\/span> <\/span>0<\/span>;<\/span><\/span>\n\t<\/span>if<\/span> (sum<\/span>><\/span>0<\/span>)<\/span><\/span>\n\t{<\/span><\/span>\n\t\t<\/span>for<\/span> (i<\/span>=<\/span>pos; i<\/span><=<\/span>size; i<\/span>++<\/span>)<\/span><\/span>\n\t\t{<\/span><\/span>\n\t\t\t<\/span>push<\/span>(set[i]);<\/span><\/span>\n\t\t\t<\/span>fnFindSubset<\/span>(i<\/span>+<\/span>1<\/span>, sum <\/span>-<\/span> set[i]);<\/span><\/span>\n\t\t\t<\/span>pop<\/span>();<\/span><\/span>\n\t\t}<\/span><\/span>\n\t}<\/span><\/span>\n\t<\/span>if<\/span> (sum <\/span>==<\/span> <\/span>0<\/span>)<\/span><\/span>\n\t{<\/span><\/span>\n\t\t<\/span>display<\/span>();<\/span><\/span>\n\t\tfoundSoln <\/span>=<\/span> <\/span>1<\/span>;<\/span><\/span>\n\t}<\/span><\/span>\n\t<\/span>return<\/span> foundSoln;<\/span><\/span>\n}<\/span><\/span>\n\/******************************************************<\/span><\/span>\n*Function\t: main<\/span><\/span>\n*Input parameters: no parameters<\/span><\/span>\n*RETURNS\t:\t0 on success<\/span><\/span>\n******************************************************\/<\/span><\/span>\nint <\/span>main<\/span>(<\/span>void<\/span>)<\/span><\/span>\n{<\/span><\/span>\n\tint sum;<\/span><\/span>\n\tSubSet set1;<\/span><\/span>\n\tset1.<\/span>getInfo<\/span>();<\/span><\/span>\n\tcout <\/span><<<\/span> <\/span>"Enter the sum value : "<\/span>;<\/span><\/span>\n\tcin <\/span>>><\/span> sum;<\/span><\/span>\n\tcout <\/span><<<\/span> endl;<\/span><\/span>\n\t<\/span>if<\/span> (<\/span>!<\/span>set1.<\/span>fnFindSubset<\/span>(<\/span>1<\/span>, sum))<\/span><\/span>\n\t\tcout <\/span><<<\/span> <\/span>"<\/span>\\n<\/span>The problem instance doesnt have any solution."<\/span> <\/span><<<\/span> endl;<\/span><\/span>\n\t<\/span>else<\/span><\/span>\n\t\tcout <\/span><<<\/span> <\/span>"<\/span>\\n<\/span>The above-mentioned sets are the required solution to "<\/span> <\/span><<<\/span><\/span>\n\t\t<\/span>"the given instance."<\/span> <\/span><<<\/span> endl;<\/span><\/span>\n\t<\/span>return<\/span> <\/span>0<\/span>;<\/span><\/span>\n}<\/span><\/span><\/code><\/pre><\/div>\n\n\n\n
              Java Code<\/h4>\n\n\n\n
              <\/circle><\/circle><\/circle><\/g><\/svg><\/span><\/path><\/path><\/svg><\/span>
              import<\/span> java.util.Scanner;<\/span><\/span>\n<\/span>\nclass<\/span> <\/span>SubSet<\/span> {<\/span><\/span>\n    <\/span>private<\/span> <\/span>static<\/span> <\/span>final<\/span> <\/span>int<\/span> MAX <\/span>=<\/span> <\/span>100<\/span>;<\/span><\/span>\n    <\/span>private<\/span> <\/span>int<\/span>[] stk <\/span>=<\/span> <\/span>new<\/span> <\/span>int<\/span>[MAX];<\/span><\/span>\n    <\/span>private<\/span> <\/span>int<\/span>[] set <\/span>=<\/span> <\/span>new<\/span> <\/span>int<\/span>[MAX];<\/span><\/span>\n    <\/span>private<\/span> <\/span>int<\/span> size;<\/span><\/span>\n    <\/span>private<\/span> <\/span>int<\/span> top;<\/span><\/span>\n    <\/span>private<\/span> <\/span>int<\/span> count;<\/span><\/span>\n    <\/span>private<\/span> <\/span>static<\/span> <\/span>int<\/span> foundSoln <\/span>=<\/span> <\/span>0<\/span>;<\/span><\/span>\n<\/span>\n    <\/span>public<\/span> <\/span>SubSet<\/span>() {<\/span><\/span>\n        top <\/span>=<\/span> <\/span>-<\/span>1<\/span>;<\/span><\/span>\n        count <\/span>=<\/span> <\/span>0<\/span>;<\/span><\/span>\n    }<\/span><\/span>\n<\/span>\n    <\/span>public<\/span> <\/span>void<\/span> <\/span>getInfo<\/span>() {<\/span><\/span>\n        Scanner scanner <\/span>=<\/span> <\/span>new<\/span> <\/span>Scanner<\/span>(System.in);<\/span><\/span>\n        System.out.<\/span>print<\/span>(<\/span>"Enter the maximum number of elements: "<\/span>);<\/span><\/span>\n        size <\/span>=<\/span> scanner.<\/span>nextInt<\/span>();<\/span><\/span>\n        System.out.<\/span>println<\/span>(<\/span>"Enter the values of the elements: "<\/span>);<\/span><\/span>\n        <\/span>for<\/span> (<\/span>int<\/span> i <\/span>=<\/span> <\/span>1<\/span>; i <\/span><=<\/span> size; i<\/span>++<\/span>) {<\/span><\/span>\n            set[i] <\/span>=<\/span> scanner.<\/span>nextInt<\/span>();<\/span><\/span>\n        }<\/span><\/span>\n    }<\/span><\/span>\n<\/span>\n    <\/span>public<\/span> <\/span>void<\/span> <\/span>push<\/span>(<\/span>int<\/span> <\/span>data<\/span>) {<\/span><\/span>\n        stk[<\/span>++<\/span>top] <\/span>=<\/span> data;<\/span><\/span>\n    }<\/span><\/span>\n<\/span>\n    <\/span>public<\/span> <\/span>void<\/span> <\/span>pop<\/span>() {<\/span><\/span>\n        top<\/span>--<\/span>;<\/span><\/span>\n    }<\/span><\/span>\n<\/span>\n    <\/span>public<\/span> <\/span>void<\/span> <\/span>display<\/span>() {<\/span><\/span>\n        System.out.<\/span>print<\/span>(<\/span>"<\/span>\\n<\/span>SOLUTION #"<\/span> <\/span>+<\/span> (<\/span>++<\/span>count) <\/span>+<\/span> <\/span>" IS<\/span>\\n<\/span>{ "<\/span>);<\/span><\/span>\n        <\/span>for<\/span> (<\/span>int<\/span> i <\/span>=<\/span> <\/span>0<\/span>; i <\/span><=<\/span> top; i<\/span>++<\/span>) {<\/span><\/span>\n            System.out.<\/span>print<\/span>(stk[i] <\/span>+<\/span> <\/span>" "<\/span>);<\/span><\/span>\n        }<\/span><\/span>\n        System.out.<\/span>println<\/span>(<\/span>"}"<\/span>);<\/span><\/span>\n    }<\/span><\/span>\n<\/span>\n    <\/span>public<\/span> <\/span>int<\/span> <\/span>findSubset<\/span>(<\/span>int<\/span> <\/span>pos<\/span>, <\/span>int<\/span> <\/span>sum<\/span>) {<\/span><\/span>\n        <\/span>if<\/span> (sum <\/span>><\/span> <\/span>0<\/span>) {<\/span><\/span>\n            <\/span>for<\/span> (<\/span>int<\/span> i <\/span>=<\/span> pos; i <\/span><=<\/span> size; i<\/span>++<\/span>) {<\/span><\/span>\n                <\/span>push<\/span>(set[i]);<\/span><\/span>\n                foundSoln <\/span>=<\/span> <\/span>findSubset<\/span>(i <\/span>+<\/span> <\/span>1<\/span>, sum <\/span>-<\/span> set[i]);<\/span><\/span>\n                <\/span>pop<\/span>();<\/span><\/span>\n            }<\/span><\/span>\n        }<\/span><\/span>\n        <\/span>if<\/span> (sum <\/span>==<\/span> <\/span>0<\/span>) {<\/span><\/span>\n            <\/span>display<\/span>();<\/span><\/span>\n            foundSoln <\/span>=<\/span> <\/span>1<\/span>;<\/span><\/span>\n        }<\/span><\/span>\n        <\/span>return<\/span> foundSoln;<\/span><\/span>\n    }<\/span><\/span>\n<\/span>\n    <\/span>public<\/span> <\/span>static<\/span> <\/span>void<\/span> <\/span>main<\/span>(<\/span>String<\/span>[] <\/span>args<\/span>) {<\/span><\/span>\n        Scanner scanner <\/span>=<\/span> <\/span>new<\/span> <\/span>Scanner<\/span>(System.in);<\/span><\/span>\n        <\/span>int<\/span> sum;<\/span><\/span>\n        SubSet set1 <\/span>=<\/span> <\/span>new<\/span> <\/span>SubSet<\/span>();<\/span><\/span>\n        set1.<\/span>getInfo<\/span>();<\/span><\/span>\n        System.out.<\/span>print<\/span>(<\/span>"Enter the sum value: "<\/span>);<\/span><\/span>\n        sum <\/span>=<\/span> scanner.<\/span>nextInt<\/span>();<\/span><\/span>\n        System.out.<\/span>println<\/span>();<\/span><\/span>\n<\/span>\n        <\/span>if<\/span> (set1.<\/span>findSubset<\/span>(<\/span>1<\/span>, sum) <\/span>==<\/span> <\/span>0<\/span>) {<\/span><\/span>\n            System.out.<\/span>println<\/span>(<\/span>"The problem instance doesn't have any solution."<\/span>);<\/span><\/span>\n        } <\/span>else<\/span> {<\/span><\/span>\n            System.out.<\/span>println<\/span>(<\/span>"The above-mentioned sets are the required solution to the given instance."<\/span>);<\/span><\/span>\n        }<\/span><\/span>\n        scanner.<\/span>close<\/span>();<\/span><\/span>\n    }<\/span><\/span>\n}<\/span><\/span>\n<\/span><\/code><\/pre><\/div>\n\n\n\n
              Output<\/h4>\n\n\n\n
              <\/circle><\/circle><\/circle><\/g><\/svg><\/span><\/path><\/path><\/svg><\/span>
              Enter the maximum number <\/span>of<\/span> <\/span>elements<\/span> : <\/span>5<\/span><\/span>\nEnter the values <\/span>of<\/span> the <\/span>elements<\/span> : <\/span><\/span>\n1<\/span> <\/span>2<\/span> <\/span>5<\/span> <\/span>6<\/span> <\/span>8<\/span><\/span>\nEnter the sum <\/span>value<\/span> : <\/span>9<\/span><\/span>\n<\/span>\n<\/span>\nSOLUTION<\/span> #<\/span>1<\/span> <\/span>IS<\/span><\/span>\n{ <\/span>1<\/span> <\/span>2<\/span> <\/span>6<\/span> }<\/span><\/span>\n<\/span>\nSOLUTION<\/span> #<\/span>2<\/span> <\/span>IS<\/span><\/span>\n{ <\/span>1<\/span> <\/span>8<\/span> }<\/span><\/span>\n<\/span>\nThe above<\/span>-<\/span>mentioned sets are the required solution to the given instance.<\/span><\/span>\n<\/span>\n#######################################################################################<\/span><\/span>\n<\/span>\nEnter the maximum number <\/span>of<\/span> <\/span>elements<\/span> : <\/span>3<\/span><\/span>\nEnter the values <\/span>of<\/span> the <\/span>elements<\/span> : <\/span><\/span>\n3<\/span> <\/span>5<\/span> <\/span>9<\/span><\/span>\nEnter the sum <\/span>value<\/span> : <\/span>6<\/span><\/span>\n<\/span>\n<\/span>\nThe problem instance doesnt have any solution.<\/span><\/span>\n<\/span><\/code><\/pre><\/div>\n\n\n\n
              \n\n\n\n
              Hamiltonian Cycles<\/h3>\n\n\n\n
              Design and implement C++\/Java Program to find all Hamiltonian Cycles in a connected undirected Graph G of n vertices using backtracking principle.<\/p>\n\n\n\n
              C++ Code<\/h4>\n\n\n\n
              <\/circle><\/circle><\/circle><\/g><\/svg><\/span><\/path><\/path><\/svg><\/span>
              \/* C++ program for solution of Hamiltonian<\/span><\/span>\nCycle problem using backtracking *\/<\/span><\/span>\n#include<\/span> <\/span><bits\/stdc++.h><\/span><\/span>\nusing<\/span> <\/span>namespace<\/span> <\/span>std<\/span>;<\/span><\/span>\n<\/span>\n\/\/ Number of vertices in the graph<\/span><\/span>\n#define<\/span> <\/span>V<\/span> 5<\/span><\/span>\n<\/span>\nvoid<\/span> <\/span>printSolution<\/span>(<\/span>int<\/span> <\/span>path<\/span>[]);<\/span><\/span>\n<\/span>\n\/* A utility function to check if<\/span><\/span>\nthe vertex v can be added at index 'pos'<\/span><\/span>\nin the Hamiltonian Cycle constructed<\/span><\/span>\nso far (stored in 'path[]') *\/<\/span><\/span>\nbool<\/span> <\/span>isSafe<\/span>(<\/span>int<\/span> <\/span>v<\/span>, <\/span>bool<\/span> <\/span>graph<\/span>[V][V],<\/span><\/span>\n\t\t\t<\/span>int<\/span> <\/span>path<\/span>[], <\/span>int<\/span> <\/span>pos<\/span>)<\/span><\/span>\n{<\/span><\/span>\n\t\/* Check if this vertex is an adjacent<\/span><\/span>\n\tvertex of the previously added vertex. *\/<\/span><\/span>\n\t<\/span>if<\/span> (graph [path[pos <\/span>-<\/span> <\/span>1<\/span>]][ v ] <\/span>==<\/span> <\/span>0<\/span>)<\/span><\/span>\n\t\t<\/span>return<\/span> <\/span>false<\/span>;<\/span><\/span>\n<\/span>\n\t\/* Check if the vertex has already been included.<\/span><\/span>\n\tThis step can be optimized by creating<\/span><\/span>\n\tan array of size V *\/<\/span><\/span>\n\t<\/span>for<\/span> (<\/span>int<\/span> i <\/span>=<\/span> <\/span>0<\/span>; i <\/span><<\/span> pos; i<\/span>++<\/span>)<\/span><\/span>\n\t\t<\/span>if<\/span> (path[i] <\/span>==<\/span> v)<\/span><\/span>\n\t\t\t<\/span>return<\/span> <\/span>false<\/span>;<\/span><\/span>\n<\/span>\n\t<\/span>return<\/span> <\/span>true<\/span>;<\/span><\/span>\n}<\/span><\/span>\n<\/span>\n\/* A recursive utility function<\/span><\/span>\nto solve hamiltonian cycle problem *\/<\/span><\/span>\nbool<\/span> <\/span>hamCycleUtil<\/span>(<\/span>bool<\/span> <\/span>graph<\/span>[V][V],<\/span><\/span>\n\t\t\t\t<\/span>int<\/span> <\/span>path<\/span>[], <\/span>int<\/span> <\/span>pos<\/span>)<\/span><\/span>\n{<\/span><\/span>\n\t\/* base case: If all vertices are<\/span><\/span>\n\tincluded in Hamiltonian Cycle *\/<\/span><\/span>\n\t<\/span>if<\/span> (pos <\/span>==<\/span> V)<\/span><\/span>\n\t{<\/span><\/span>\n\t\t\/\/ And if there is an edge from the<\/span><\/span>\n\t\t\/\/ last included vertex to the first vertex<\/span><\/span>\n\t\t<\/span>if<\/span> (graph[path[pos <\/span>-<\/span> <\/span>1<\/span>]][path[<\/span>0<\/span>]] <\/span>==<\/span> <\/span>1<\/span>)<\/span><\/span>\n\t\t\t<\/span>return<\/span> <\/span>true<\/span>;<\/span><\/span>\n\t\t<\/span>else<\/span><\/span>\n\t\t\t<\/span>return<\/span> <\/span>false<\/span>;<\/span><\/span>\n\t}<\/span><\/span>\n<\/span>\n\t\/\/ Try different vertices as a next candidate<\/span><\/span>\n\t\/\/ in Hamiltonian Cycle. We don't try for 0 as<\/span><\/span>\n\t\/\/ we included 0 as starting point in findHamCycle()<\/span><\/span>\n\t<\/span>for<\/span> (<\/span>int<\/span> v <\/span>=<\/span> <\/span>1<\/span>; v <\/span><<\/span> V; v<\/span>++<\/span>)<\/span><\/span>\n\t{<\/span><\/span>\n\t\t\/* Check if this vertex can be added<\/span><\/span>\n\t\t\/\/ to Hamiltonian Cycle *\/<\/span><\/span>\n\t\t<\/span>if<\/span> (<\/span>isSafe<\/span>(v, graph, path, pos))<\/span><\/span>\n\t\t{<\/span><\/span>\n\t\t\tpath[pos] <\/span>=<\/span> v;<\/span><\/span>\n<\/span>\n\t\t\t\/* recur to construct rest of the path *\/<\/span><\/span>\n\t\t\t<\/span>if<\/span> (<\/span>hamCycleUtil<\/span> (graph, path, pos <\/span>+<\/span> <\/span>1<\/span>) <\/span>==<\/span> <\/span>true<\/span>)<\/span><\/span>\n\t\t\t\t<\/span>return<\/span> <\/span>true<\/span>;<\/span><\/span>\n<\/span>\n\t\t\t\/* If adding vertex v doesn't lead to a solution,<\/span><\/span>\n\t\t\tthen remove it *\/<\/span><\/span>\n\t\t\tpath[pos] <\/span>=<\/span> <\/span>-<\/span>1<\/span>;<\/span><\/span>\n\t\t}<\/span><\/span>\n\t}<\/span><\/span>\n<\/span>\n\t\/* If no vertex can be added to<\/span><\/span>\n\tHamiltonian Cycle constructed so far,<\/span><\/span>\n\tthen return false *\/<\/span><\/span>\n\t<\/span>return<\/span> <\/span>false<\/span>;<\/span><\/span>\n}<\/span><\/span>\n<\/span>\n\/* This function solves the Hamiltonian Cycle problem<\/span><\/span>\nusing Backtracking. It mainly uses hamCycleUtil() to<\/span><\/span>\nsolve the problem. It returns false if there is no<\/span><\/span>\nHamiltonian Cycle possible, otherwise return true<\/span><\/span>\nand prints the path. Please note that there may be<\/span><\/span>\nmore than one solutions, this function prints one<\/span><\/span>\nof the feasible solutions. *\/<\/span><\/span>\nbool<\/span> <\/span>findHamCycle<\/span>(<\/span>bool<\/span> <\/span>graph<\/span>[V][V])<\/span><\/span>\n{<\/span><\/span>\n\t<\/span>int<\/span> <\/span>*<\/span>path <\/span>=<\/span> <\/span>new<\/span> <\/span>int<\/span>[V];<\/span><\/span>\n\t<\/span>for<\/span> (<\/span>int<\/span> i <\/span>=<\/span> <\/span>0<\/span>; i <\/span><<\/span> V; i<\/span>++<\/span>)<\/span><\/span>\n\t\tpath[i] <\/span>=<\/span> <\/span>-<\/span>1<\/span>;<\/span><\/span>\n<\/span>\n\t\/* Let us put vertex 0 as the first vertex in the path.<\/span><\/span>\n\tIf there is a Hamiltonian Cycle, then the path can be<\/span><\/span>\n\tstarted from any point of the cycle as the graph is undirected *\/<\/span><\/span>\n\tpath[<\/span>0<\/span>] <\/span>=<\/span> <\/span>0<\/span>;<\/span><\/span>\n\t<\/span>if<\/span> (<\/span>hamCycleUtil<\/span>(graph, path, <\/span>1<\/span>) <\/span>==<\/span> <\/span>false<\/span> )<\/span><\/span>\n\t{<\/span><\/span>\n\t\tcout <\/span><<<\/span> <\/span>"<\/span>\\n<\/span>Solution does not exist for this graph"<\/span> <\/span><<<\/span> endl;<\/span><\/span>\n\t\t<\/span>return<\/span> <\/span>false<\/span>;<\/span><\/span>\n\t}<\/span><\/span>\n<\/span>\n\t<\/span>printSolution<\/span>(path);<\/span><\/span>\n\t<\/span>return<\/span> <\/span>true<\/span>;<\/span><\/span>\n}<\/span><\/span>\n<\/span>\n\/* A utility function to print solution *\/<\/span><\/span>\nvoid<\/span> <\/span>printSolution<\/span>(<\/span>int<\/span> <\/span>path<\/span>[])<\/span><\/span>\n{<\/span><\/span>\n\tcout <\/span><<<\/span> <\/span>"Solution Exists:"<\/span><\/span>\n\t\t\t<\/span>" Following is one Hamiltonian Cycle <\/span>\\n<\/span>"<\/span>;<\/span><\/span>\n\t<\/span>for<\/span> (<\/span>int<\/span> i <\/span>=<\/span> <\/span>0<\/span>; i <\/span><<\/span> V; i<\/span>++<\/span>)<\/span><\/span>\n\t\tcout <\/span><<<\/span> path[i] <\/span><<<\/span> <\/span>" "<\/span>;<\/span><\/span>\n<\/span>\n\t\/\/ Let us print the first vertex again<\/span><\/span>\n\t\/\/ to show the complete cycle<\/span><\/span>\n\tcout <\/span><<<\/span> path[<\/span>0<\/span>] <\/span><<<\/span> <\/span>" "<\/span>;<\/span><\/span>\n\tcout <\/span><<<\/span> endl;<\/span><\/span>\n}<\/span><\/span>\n<\/span>\n\/\/ Driver Code<\/span><\/span>\nint<\/span> <\/span>main<\/span>()<\/span><\/span>\n{<\/span><\/span>\n\t<\/span>int<\/span> iNum;<\/span><\/span>\n\t<\/span>bool<\/span> g1[V][V], g2[V][V];<\/span><\/span>\n\t<\/span><\/span>\n\tcout <\/span><<<\/span> <\/span>"<\/span>\\n<\/span>Enter the number of nodes in the first graph : "<\/span>;<\/span><\/span>\n\tcin <\/span>>><\/span> iNum;<\/span><\/span>\n\tcout <\/span><<<\/span> <\/span>"<\/span>\\n<\/span>Enter the adjacency matrix of the first graph"<\/span> <\/span><<<\/span> endl;\t\t\t\t\t\t<\/span><\/span>\n\t<\/span>for<\/span>(<\/span>int<\/span> i<\/span>=<\/span>0<\/span>; i<\/span><<\/span>iNum; i<\/span>++<\/span>)<\/span><\/span>\n\t{<\/span><\/span>\n\t\t<\/span>for<\/span>(<\/span>int<\/span> j<\/span>=<\/span>0<\/span>; j<\/span><<\/span>iNum; j<\/span>++<\/span>)<\/span><\/span>\n\t\t{<\/span><\/span>\n\t\t\tcin <\/span>>><\/span> g1[i][j];<\/span><\/span>\n\t\t}<\/span><\/span>\n\t}<\/span><\/span>\n\t<\/span><\/span>\n\t\/\/ Print the solution<\/span><\/span>\n\t<\/span>findHamCycle<\/span>(g1);<\/span><\/span>\n\t<\/span><\/span>\n\tcout <\/span><<<\/span> <\/span>"<\/span>\\n<\/span>Enter the number of nodes in the second graph : "<\/span>;<\/span><\/span>\n\tcin <\/span>>><\/span> iNum;<\/span><\/span>\n\tcout <\/span><<<\/span> <\/span>"<\/span>\\n<\/span>Enter the adjacency matrix of the second graph"<\/span> <\/span><<<\/span> endl;\t\t\t\t\t\t<\/span><\/span>\n\t<\/span>for<\/span>(<\/span>int<\/span> i<\/span>=<\/span>0<\/span>; i<\/span><<\/span>iNum; i<\/span>++<\/span>)<\/span><\/span>\n\t{<\/span><\/span>\n\t\t<\/span>for<\/span>(<\/span>int<\/span> j<\/span>=<\/span>0<\/span>; j<\/span><<\/span>iNum; j<\/span>++<\/span>)<\/span><\/span>\n\t\t{<\/span><\/span>\n\t\t\tcin <\/span>>><\/span> g2[i][j];<\/span><\/span>\n\t\t}<\/span><\/span>\n\t}<\/span><\/span>\n<\/span>\n\t\/\/ Print the solution<\/span><\/span>\n\t<\/span>findHamCycle<\/span>(g2);<\/span><\/span>\n<\/span>\n\t<\/span>return<\/span> <\/span>0<\/span>;<\/span><\/span>\n}<\/span><\/span>\n<\/span>\n<\/span><\/code><\/pre><\/div>\n\n\n\n
              Java Code<\/h4>\n\n\n\n
              <\/circle><\/circle><\/circle><\/g><\/svg><\/span><\/path><\/path><\/svg><\/span>
              import<\/span> java.util.Scanner;<\/span><\/span>\n<\/span>\nclass<\/span> <\/span>HamiltonianCycle<\/span> {<\/span><\/span>\n    <\/span>private<\/span> <\/span>static<\/span> <\/span>final<\/span> <\/span>int<\/span> V <\/span>=<\/span> <\/span>5<\/span>;<\/span><\/span>\n<\/span>\n    <\/span><\/span>\n    <\/span>private<\/span> <\/span>static<\/span> <\/span>boolean<\/span> <\/span>isSafe<\/span>(<\/span>int<\/span> <\/span>v<\/span>, <\/span>int<\/span>[][] <\/span>graph<\/span>, <\/span>int<\/span>[] <\/span>path<\/span>, <\/span>int<\/span> <\/span>pos<\/span>) {<\/span><\/span>\n<\/span>\n        <\/span>if<\/span> (graph[path[pos <\/span>-<\/span> <\/span>1<\/span>]][v] <\/span>==<\/span> <\/span>0<\/span>)<\/span><\/span>\n            <\/span>return<\/span> <\/span>false<\/span>;<\/span><\/span>\n<\/span>\n        <\/span>for<\/span> (<\/span>int<\/span> i <\/span>=<\/span> <\/span>0<\/span>; i <\/span><<\/span> pos; i<\/span>++<\/span>) {<\/span><\/span>\n            <\/span>if<\/span> (path[i] <\/span>==<\/span> v)<\/span><\/span>\n                <\/span>return<\/span> <\/span>false<\/span>;<\/span><\/span>\n        }<\/span><\/span>\n<\/span>\n        <\/span>return<\/span> <\/span>true<\/span>;<\/span><\/span>\n    }<\/span><\/span>\n<\/span>\n<\/span>\n    <\/span>private<\/span> <\/span>static<\/span> <\/span>boolean<\/span> <\/span>hamCycleUtil<\/span>(<\/span>int<\/span>[][] <\/span>graph<\/span>, <\/span>int<\/span>[] <\/span>path<\/span>, <\/span>int<\/span> <\/span>pos<\/span>) {<\/span><\/span>\n<\/span>\n        <\/span>if<\/span> (pos <\/span>==<\/span> V) {<\/span><\/span>\n            <\/span>if<\/span> (graph[path[pos <\/span>-<\/span> <\/span>1<\/span>]][path[<\/span>0<\/span>]] <\/span>==<\/span> <\/span>1<\/span>)<\/span><\/span>\n                <\/span>return<\/span> <\/span>true<\/span>;<\/span><\/span>\n            <\/span>else<\/span><\/span>\n                <\/span>return<\/span> <\/span>false<\/span>;<\/span><\/span>\n        }<\/span><\/span>\n<\/span>\n        <\/span>for<\/span> (<\/span>int<\/span> v <\/span>=<\/span> <\/span>1<\/span>; v <\/span><<\/span> V; v<\/span>++<\/span>) {<\/span><\/span>\n            <\/span>if<\/span> (<\/span>isSafe<\/span>(v, graph, path, pos)) {<\/span><\/span>\n                path[pos] <\/span>=<\/span> v;<\/span><\/span>\n<\/span>\n                <\/span>if<\/span> (<\/span>hamCycleUtil<\/span>(graph, path, pos <\/span>+<\/span> <\/span>1<\/span>) <\/span>==<\/span> <\/span>true<\/span>)<\/span><\/span>\n                    <\/span>return<\/span> <\/span>true<\/span>;<\/span><\/span>\n<\/span>\n                path[pos] <\/span>=<\/span> <\/span>-<\/span>1<\/span>;<\/span><\/span>\n            }<\/span><\/span>\n        }<\/span><\/span>\n<\/span>\n        <\/span>return<\/span> <\/span>false<\/span>;<\/span><\/span>\n    }<\/span><\/span>\n<\/span>\n    <\/span>private<\/span> <\/span>static<\/span> <\/span>boolean<\/span> <\/span>findHamCycle<\/span>(<\/span>int<\/span>[][] <\/span>graph<\/span>) {<\/span><\/span>\n        <\/span>int<\/span>[] path <\/span>=<\/span> <\/span>new<\/span> <\/span>int<\/span>[V];<\/span><\/span>\n        <\/span>for<\/span> (<\/span>int<\/span> i <\/span>=<\/span> <\/span>0<\/span>; i <\/span><<\/span> V; i<\/span>++<\/span>)<\/span><\/span>\n            path[i] <\/span>=<\/span> <\/span>-<\/span>1<\/span>;<\/span><\/span>\n<\/span>\n        path[<\/span>0<\/span>] <\/span>=<\/span> <\/span>0<\/span>;<\/span><\/span>\n        <\/span>if<\/span> (<\/span>hamCycleUtil<\/span>(graph, path, <\/span>1<\/span>) <\/span>==<\/span> <\/span>false<\/span>) {<\/span><\/span>\n            System.out.<\/span>println<\/span>(<\/span>"<\/span>\\n<\/span>Solution does not exist for this graph"<\/span>);<\/span><\/span>\n            <\/span>return<\/span> <\/span>false<\/span>;<\/span><\/span>\n        }<\/span><\/span>\n<\/span>\n        <\/span>printSolution<\/span>(path);<\/span><\/span>\n        <\/span>return<\/span> <\/span>true<\/span>;<\/span><\/span>\n    }<\/span><\/span>\n<\/span>\n    <\/span>private<\/span> <\/span>static<\/span> <\/span>void<\/span> <\/span>printSolution<\/span>(<\/span>int<\/span>[] <\/span>path<\/span>) {<\/span><\/span>\n        System.out.<\/span>print<\/span>(<\/span>"Solution Exists: Following is one Hamiltonian Cycle <\/span>\\n<\/span>"<\/span>);<\/span><\/span>\n        <\/span>for<\/span> (<\/span>int<\/span> i <\/span>=<\/span> <\/span>0<\/span>; i <\/span><<\/span> V; i<\/span>++<\/span>)<\/span><\/span>\n            System.out.<\/span>print<\/span>(path[i] <\/span>+<\/span> <\/span>" "<\/span>);<\/span><\/span>\n<\/span>\n        System.out.<\/span>print<\/span>(path[<\/span>0<\/span>] <\/span>+<\/span> <\/span>" "<\/span>);<\/span><\/span>\n        System.out.<\/span>println<\/span>();<\/span><\/span>\n    }<\/span><\/span>\n<\/span>\n    <\/span>public<\/span> <\/span>static<\/span> <\/span>void<\/span> <\/span>main<\/span>(<\/span>String<\/span>[] <\/span>args<\/span>) {<\/span><\/span>\n        <\/span>int<\/span> iNum;<\/span><\/span>\n        <\/span>int<\/span>[][] g1 <\/span>=<\/span> <\/span>new<\/span> <\/span>int<\/span>[V][V];<\/span><\/span>\n        <\/span>int<\/span>[][] g2 <\/span>=<\/span> <\/span>new<\/span> <\/span>int<\/span>[V][V];<\/span><\/span>\n<\/span>\n        Scanner scanner <\/span>=<\/span> <\/span>new<\/span> <\/span>Scanner<\/span>(System.in);<\/span><\/span>\n<\/span>\n        System.out.<\/span>print<\/span>(<\/span>"Enter the number of nodes in the first graph: "<\/span>);<\/span><\/span>\n        iNum <\/span>=<\/span> scanner.<\/span>nextInt<\/span>();<\/span><\/span>\n        System.out.<\/span>println<\/span>(<\/span>"Enter the adjacency matrix of the first graph:"<\/span>);<\/span><\/span>\n        <\/span>for<\/span> (<\/span>int<\/span> i <\/span>=<\/span> <\/span>0<\/span>; i <\/span><<\/span> iNum; i<\/span>++<\/span>) {<\/span><\/span>\n            <\/span>for<\/span> (<\/span>int<\/span> j <\/span>=<\/span> <\/span>0<\/span>; j <\/span><<\/span> iNum; j<\/span>++<\/span>) {<\/span><\/span>\n                g1[i][j] <\/span>=<\/span> scanner.<\/span>nextInt<\/span>();<\/span><\/span>\n            }<\/span><\/span>\n        }<\/span><\/span>\n<\/span>\n        <\/span>findHamCycle<\/span>(g1);<\/span><\/span>\n<\/span>\n        System.out.<\/span>print<\/span>(<\/span>"Enter the number of nodes in the second graph: "<\/span>);<\/span><\/span>\n        iNum <\/span>=<\/span> scanner.<\/span>nextInt<\/span>();<\/span><\/span>\n        System.out.<\/span>println<\/span>(<\/span>"Enter the adjacency matrix of the second graph:"<\/span>);<\/span><\/span>\n        <\/span>for<\/span> (<\/span>int<\/span> i <\/span>=<\/span> <\/span>0<\/span>; i <\/span><<\/span> iNum; i<\/span>++<\/span>) {<\/span><\/span>\n            <\/span>for<\/span> (<\/span>int<\/span> j <\/span>=<\/span> <\/span>0<\/span>; j <\/span><<\/span> iNum; j<\/span>++<\/span>) {<\/span><\/span>\n                g2[i][j] <\/span>=<\/span> scanner.<\/span>nextInt<\/span>();<\/span><\/span>\n            }<\/span><\/span>\n        }<\/span><\/span>\n<\/span>\n        <\/span>findHamCycle<\/span>(g2);<\/span><\/span>\n    }<\/span><\/span>\n}<\/span><\/span>\n<\/span><\/code><\/pre><\/div>\n\n\n\n
              Input Graphs<\/h4>\n\n\n\n
              Let us consider the following graphs as input for this program<\/p>\n\n\n\n
              \n
              \n
              Graph 1<\/strong><\/h5>\n\n\n\n
              \"\"<\/a><\/figure>\n<\/div>\n\n\n\n
              \n
              Graph 2<\/strong><\/h5>\n\n\n\n
              \"\"<\/a><\/figure>\n<\/div>\n<\/div>\n\n\n\n
              Output<\/h4>\n\n\n\n
              <\/circle><\/circle><\/circle><\/g><\/svg><\/span><\/path><\/path><\/svg><\/span>
              <\/span>\nEnter the number <\/span>of<\/span> nodes <\/span>in<\/span> the first <\/span>graph<\/span> : <\/span>5<\/span><\/span>\n<\/span>\nEnter the adjacency matrix <\/span>of<\/span> the first graph<\/span><\/span>\n0<\/span> <\/span>1<\/span> <\/span>0<\/span> <\/span>1<\/span> <\/span>0<\/span><\/span>\n1<\/span> <\/span>0<\/span> <\/span>1<\/span> <\/span>1<\/span> <\/span>1<\/span><\/span>\n0<\/span> <\/span>1<\/span> <\/span>0<\/span> <\/span>0<\/span> <\/span>1<\/span><\/span>\n1<\/span> <\/span>1<\/span> <\/span>0<\/span> <\/span>0<\/span> <\/span>1<\/span><\/span>\n0<\/span> <\/span>1<\/span> <\/span>1<\/span> <\/span>1<\/span> <\/span>0<\/span><\/span>\nSolution <\/span>Exists<\/span>: Following is one Hamiltonian Cycle <\/span><\/span>\n0<\/span> <\/span>1<\/span> <\/span>2<\/span> <\/span>4<\/span> <\/span>3<\/span> <\/span>0<\/span> <\/span><\/span>\n<\/span>\nEnter the number <\/span>of<\/span> nodes <\/span>in<\/span> the second <\/span>graph<\/span> : <\/span>5<\/span><\/span>\n<\/span>\nEnter the adjacency matrix <\/span>of<\/span> the second graph<\/span><\/span>\n0<\/span> <\/span>1<\/span> <\/span>0<\/span> <\/span>1<\/span> <\/span>0<\/span><\/span>\n1<\/span> <\/span>0<\/span> <\/span>1<\/span> <\/span>1<\/span> <\/span>1<\/span><\/span>\n0<\/span> <\/span>1<\/span> <\/span>0<\/span> <\/span>0<\/span> <\/span>1<\/span><\/span>\n1<\/span> <\/span>1<\/span> <\/span>0<\/span> <\/span>0<\/span> <\/span>0<\/span><\/span>\n0<\/span> <\/span>1<\/span> <\/span>1<\/span> <\/span>0<\/span> <\/span>0<\/span><\/span>\n<\/span>\nSolution does not exist for <\/span>this<\/span> graph<\/span><\/span>\n<\/span><\/code><\/pre><\/div>\n\n\n\n
              \n","protected":false},"excerpt":{"rendered":"
              Demystifying Algorithms & Solving Problems In this blog post, you will find solutions for the lab component Design & Analysis of\u00a0Algorithms (21CS42) course work for the IV semester of VTU university. The solutions to the lab component are coded in C++. We recommend using the Code:Blocks as the integrated development environment (IDE). You can find […]<\/p>\n","protected":false},"author":1,"featured_media":672,"comment_status":"open","ping_status":"closed","sticky":false,"template":"","format":"standard","meta":{"_monsterinsights_skip_tracking":false,"_monsterinsights_sitenote_active":false,"_monsterinsights_sitenote_note":"","_monsterinsights_sitenote_category":0,"site-container-style":"default","site-container-layout":"default","site-sidebar-layout":"default","disable-article-header":"default","disable-site-header":"default","disable-site-footer":"default","disable-content-area-spacing":"default","_jetpack_memberships_contains_paid_content":false,"footnotes":"","jetpack_publicize_message":"","jetpack_publicize_feature_enabled":true,"jetpack_social_post_already_shared":true,"jetpack_social_options":{"image_generator_settings":{"template":"highway","default_image_id":0,"font":"","enabled":false},"version":2}},"categories":[3],"tags":[91,93,89,90,94,78,26,34,35,43],"class_list":["post-643","post","type-post","status-publish","format-standard","has-post-thumbnail","hentry","category-programming","tag-21cs42","tag-4thsemester","tag-algorithms","tag-c-2","tag-complete-solutions","tag-cse","tag-foss","tag-java","tag-lab-manual","tag-vtu"],"aioseo_notices":[],"jetpack_publicize_connections":[],"jetpack_featured_media_url":"https:\/\/i0.wp.com\/moodle.sit.ac.in\/blog\/wp-content\/uploads\/2023\/06\/daa-tutorial-1.png?fit=250%2C247&ssl=1","jetpack-related-posts":[],"jetpack_sharing_enabled":true,"amp_enabled":true,"_links":{"self":[{"href":"https:\/\/moodle.sit.ac.in\/blog\/wp-json\/wp\/v2\/posts\/643","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/moodle.sit.ac.in\/blog\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/moodle.sit.ac.in\/blog\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/moodle.sit.ac.in\/blog\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/moodle.sit.ac.in\/blog\/wp-json\/wp\/v2\/comments?post=643"}],"version-history":[{"count":3,"href":"https:\/\/moodle.sit.ac.in\/blog\/wp-json\/wp\/v2\/posts\/643\/revisions"}],"predecessor-version":[{"id":1925,"href":"https:\/\/moodle.sit.ac.in\/blog\/wp-json\/wp\/v2\/posts\/643\/revisions\/1925"}],"wp:featuredmedia":[{"embeddable":true,"href":"https:\/\/moodle.sit.ac.in\/blog\/wp-json\/wp\/v2\/media\/672"}],"wp:attachment":[{"href":"https:\/\/moodle.sit.ac.in\/blog\/wp-json\/wp\/v2\/media?parent=643"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/moodle.sit.ac.in\/blog\/wp-json\/wp\/v2\/categories?post=643"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/moodle.sit.ac.in\/blog\/wp-json\/wp\/v2\/tags?post=643"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}