MinMaks dengan Divide and Conquer c++

 #include <cstdlib>
#include <iostream>

using namespace std;

void minmax2(int A[], int i, int j, int &min, int &max ){
    
     int min1, min2, max1, max2,k;
     if(i==j){
              min=A[i];
              max=A[i];
              }
     else if(i==j-1){
          if(A[i]<A[j]){
                        max=A[j];
                        min=A[i];
                        }
          else{
               max=A[i];
               min=A[j];
               }
          }
     else{
          k=(i+j)/2;
          minmax2(A,i,k,min1,max1);
          minmax2(A,(k+1),j,min2,max2);
          if(min1<min2)min=min1;
          else min=min2;
          if(max1<max2)max=max2;
          else max=max1;
          }
     }

int main(int argc, char *argv[])
{
  
    system("title MinMax dengan Divide and Conquer c++ - adibrenizaf.blogspot.com/");
   
    int A[100],n,i,j,min,max;
    cout<<"Mauskkan banyak data : ";
    cin>>n;
    for(int a=1;a<=n;a++){
            cout<<"Data ke-"<<a<<" : ";
            cin>>A[a];
            }
    i=1;
    j=n;
   
    minmax2(A,i,j,min,max);
   
    cout<<"\nNilai max = "<<max<<endl;
    cout<<"Nilai min = "<<min<<endl<<endl;
   
    system("PAUSE");
    return EXIT_SUCCESS;
}

Read More

Graf lintasan terpendek v 2.0 Algoritma Greedy

#include <cstdlib>
#include <iostream>
#define max 20
#define infinity 9999

using namespace std;
class dijkstra{
      private:
              int n,graph[max][max],colour[max],start,distance[max],predecessor[max];
              enum {green,yellow,red};
      public:
             void read_graph();
             void initialize();
             int select_min_distance_lable();
             void update(int);
             void output();
             void function();

      };
void dijkstra::read_graph(){
     cout<<"masukkan jumlah node = ";
     cin>>n;
     cout<<"masukkan nilai matrik untuk graf ::\n";
     int i,j;
     for(i=1;i<=n;i++){
                       for(j=1;j<=n;j++){
                                         cout<<"["<<i<<"],["<<j<<"]=";
                                         cin>>graph[i][j];}}
     for(i=1;i<=n;i++){
                       colour[i]=green;}
     cout<<"masukkan vertex mulai :: ";
     cin>>start;
     }
void dijkstra::initialize(){
     for(int i=1;i<=n;i++){
             if(i==start){
                          distance[i]=0;}
             else{distance[i]=infinity;}
     }
     for(int j=1;j<=n;j++){
             if(graph[start][j]!=0){
                                    predecessor[j]=start;}
             else{predecessor[j]=0;}
     }
}
int dijkstra::select_min_distance_lable(){
    int min=infinity;
    int p=0;
    for(int i=1;i<=n;i++){
            if(colour[i]==green){
                                 if(min>=distance[i]){
                                                   min=distance[i];
                                                   p=i;
                                                   }
                                 }
            }
    return p;
    }
void dijkstra::update(int p){
     cout<<"\nupdate jarak = \n";
     for(int i=1;i<=n;i++){
             if(colour[i]==green){
                                  if(graph[p][i]!=0){
                                                     if(distance[i]>graph[p][i]+distance[p]){
                                                                                             distance[i]=graph[p][i]+distance[p];
                                                                                             predecessor[i]=p;
                                                                                             }
                                                     }
                                  }
             cout<<distance[i]<<'\t';
             }
     }
void dijkstra::output()
{
 cout<<"****** Jalur akhir dan distacnes adalah ******\n\n";

 for(int i=1;i<=n;i++)
 {
  if(predecessor[i]==0 && i!=start)
  {
   cout<<"jalan tidak ada antara "<<i<<" dan awal titik "
    <<start<<endl;
   exit(1);
  }
  cout<<"jalan untuk node "<<i<<" is ::\n";
  int j=i;
  int array[max];
  int l=0;
  while(predecessor[j]!=0)
  {
   array[++l]=predecessor[j];
   j=predecessor[j];
  }
  for(int k=l;k>=1;k--)
   cout<<array[k]<<"->";

  cout<<i<<endl;
  cout<<"jarak adalah "<<distance[i]<<endl<<endl<<endl;
 }
}

void dijkstra::function()
{
 cout<<"\n**********************************************************************\n";
 cout<<"*Program ini adalah untuk menerapkan algoritma dijkstra dengan menggunakan kode warna* \n";
 cout<<"**********************************************************************\n\n";
 read_graph();
 initialize();  //repeate until all nodes become red
 int flag=0;
 int i;

 cout<<"\n\n******** Kerja dari algoritma ini adalah **********\n\n";

 for(i=1;i<=n;i++)
  if(colour[i]!=red)
   flag=1;

 cout<<"Jarak awal adalah ::\n";
 for(i=1;i<=n;i++)
  cout<<distance[i]<<'\t';
 cout<<endl;

 while(flag)
 {
  int p=select_min_distance_lable();
  cout<<"\nJarak min label yang berwarna kuning adalah "<<p;
  colour[p]=yellow;

  update(p);
  cout<<"\nnode ="<<p<<" berwarna merah "<<endl;
  colour[p]=red;

  flag=0;
  for(i=1;i<=n;i++)
   if(colour[i]!=red)
    flag=1;

  cout<<endl<<endl<<endl;
 }
 output();
}

int main(int argc, char *argv[])
{
    dijkstra d;
 d.function();
    system("PAUSE");
    return EXIT_SUCCESS;
    }

Read More

Graf lintasan terpendek Algoritma Greedy

#include<iostream>
#include<stdlib.h>
#define MAX 20
#define INFINITY 9999
using namespace std;
class dijkstra
{
private:
int n;
int graph[MAX][MAX];
int colour[MAX];
int start;
int distance[MAX];
int predecessor[MAX];
enum {green,yellow,red};
public:
void read_graph();
void initialize();
int select_min_distance_lable();
void update(int);
void output();
void function();
};
void dijkstra::read_graph()
{
cout<<"Enter the no. of nodes in the graph ::";
cin>>n;
cout<<"Enter the adjacency matrix for the graph ::\n";
int i,j;
for(i=1;i<=n;i++)
for(j=1;j<=n;j++)
cin>>graph[i][j];
for(i=1;i<=n;i++)
colour[i]=green;
cout<<"Enter the start vertex ::";
cin>>start;
}
void dijkstra::initialize()
{
for(int i=1;i<=n;i++)
{
if(i==start)
distance[i]=0;
else
distance[i]=INFINITY;
}
for(int j=1;j<=n;j++)
{
if(graph[start][j]!=0)
predecessor[j]=start;
else
predecessor[j]=0;
}
}
int dijkstra::select_min_distance_lable()
{
int min=INFINITY;
int p=0;
for(int i=1;i<=n;i++)
{
if(colour[i]==green)
{
if(min>=distance[i])
{
min=distance[i];
p=i;
}
}
}
return p;
}
void dijkstra::update(int p) // p is a yellow colour node
{
cout<<"\nupdated distances are ::\n";
for(int i=1;i<=n;i++)
{
if(colour[i]==green)
{
if(graph[p][i]!=0)
{
if(distance[i]>graph[p][i]+distance[p])
{
distance[i]=graph[p][i]+distance[p];
predecessor[i]=p;
}
}
}
cout<<distance[i]<<'\t';
}
}
void dijkstra::output()
{
cout<<"****** The final paths and the distacnes are ******\n\n";
for(int i=1;i<=n;i++)
{
if(predecessor[i]==0 && i!=start)
{
cout<<"path does not exists between "<<i<<" and the start vertex "<<start<<endl;
exit(1);
}
cout<<"path for node “<<i<<” is ::\n";
int j=i;
int array[MAX];
int l=0;
while(predecessor[j]!=0)
{
array[++l]=predecessor[j];
j=predecessor[j];
}
for(int k=l;k>=1;k=-k)
cout<<array[k]<<"->";
cout<<i<<endl;
cout<<"distance is "<<distance[i]<<endl<<endl<<endl;
}
}
void dijkstra::function()
{
cout<<"\n**********************************************************************\n";
cout<<"This program is to implement dijkstra’s algorithm using colour codes \n";
cout<<"**********************************************************************\n\n";
read_graph();
initialize();
//repeate until all nodes become red
int flag=0;
int i;
cout<<"\n\n******** The working of the algorithm is **********\n\n";
for(i=1;i<=n;i++)
if(colour[i]!=red)
flag=1;
cout<<"The initial distances are ::\n";
for(i=1;i<=n;i++)
cout<<distance[i]<<'\t';
cout<<endl;
while(flag)
{
int p=select_min_distance_lable();
cout<<"\nThe min distance lable that is coloured yellow is "<<p;
colour[p]=yellow;
update(p);
cout<<"\nnode "<<p<<" is coloured red "<<endl;
colour[p]=red;
flag=0;
for(i=1;i<=n;i++)
if(colour[i]!=red)
flag=1;
cout<<endl<<endl<<endl;
}
output();
}
int main()
{
dijkstra d;
d.function();

system("PAUSE");
return EXIT_SUCCESS;
}

Read More

strategi algoritma prim dan kruskal

#include <cstdlib>
#include <iostream>
#include <conio.h>

using namespace std;
class prims
{
   private:
        int n; //no of nodes
        int graph_edge[250][4]; //edges in the graph
        int g; //no of edges in the graph
        int tree_edge[250][4]; //edges in the tree
        int t; //no of edges in the tree
        int s; //source node
//Partition the graph in to two sets
            int T1[50],t1; // Set 1
            int T2[50],t2; // Set 2
   public:
       void input();
       int findset(int);
       void algorithm();
       void output();
       };
   void prims::input()
   {
  cout<<"*************************************************\n"
  <<"This program implements the prims algorithm\n"
  <<"*************************************************\n";
  cout<<"Enter the no. of nodes in the undirected weighted graph ::";
  cin>>n;
  g=0;
  cout<<"Enter the weights for the following edges ::\n";
  for(int i=1;i<=n;i++)
     {
      for(int j=i+1;j<=n;j++)
              {
              cout<<" < "<<i<<" , "<<j<<" > ::";
  int w;
  cin>>w;
  if(w!=0)
  {
   g++;
   graph_edge[g][1]=i;
   graph_edge[g][2]=j;
   graph_edge[g][3]=w;
   }
                      }
}
// print the graph edges
   cout<<"\n\nThe edges in the given graph are::\n";
   for(int i=1;i<=g;i++)
   cout<<" < "<<graph_edge[i][1]
   <<" , "<<graph_edge[i][2]
   <<" > ::"<<graph_edge[i][3]<<endl;
       }
       int prims::findset(int x)
       {
       for(int i=1;i<=t1;i++)
       if(x==T1[i])
       return 1;
       for(int i=1;i<=t2;i++)
       if(x==T2[i])
       return 2;
       return -1;
       }
  void prims::algorithm()
  {
   t=0;
   t1=1;
   T1[1]=1; //The source node
   t2=n-1;
   int i;
   for(i=1;i<=n-1;i++)
   T2[i]=i+1; //The reamining nodes
   cout<<"\n*****The algorithm starts*****\n\n";
   while(g!=0 && t!=n-1)
   {
// Find the least cost edge
   int min=9999;
   int p;
   int u,v,w;
   for(i=1;i<=g;i++)
   {
   bool flag1=false,flag2=false;
//if u and v are in different sets
     if(findset(graph_edge[i][1])!=findset(graph_edge[i][2]))
      {
       if(min>graph_edge[i][3])
        {
         min=graph_edge[i][3];
         u=graph_edge[i][1];
         v=graph_edge[i][2];
         w=graph_edge[i][3];
         p=i;
         }
        }
       }
//break if there is no such edge
        cout<<"The edge included in the tree is ::";
        cout<<" < "<<u<<" , "<<v<<" > "<<endl;
//delete the edge from graph edges
         for(int l=p;l<g;l++)
          {
          graph_edge[l][1]=graph_edge[l+1][1];
          graph_edge[l][2]=graph_edge[l+1][2];
          graph_edge[l][3]=graph_edge[l+1][3];
          }
          g--;
//add the edge to the tree
      t++;
      tree_edge[t][1]=u;
      tree_edge[t][2]=v;
      tree_edge[t][3]=w;
//Alter the set partitions
        t1++;
        int m;
        if(findset(v)==2)
        {
         T1[t1]=v;
         m=v;
         }
         else if(findset(u)==2)
         {
         T1[t1]=u;
         m=u;
         }
         int x;
         for(x=1;T2[x]!=m;x++);
         for(;x<t2;x++)
         T2[x]=T2[x+1];
         t2--;
// Print the sets
   int k;
   cout<<"NOW\nT1 :: ";
   for(k=1;k<=t1;k++)
    cout<<T1[k]<<' ';
    cout<<endl;
    cout<<"T2 :: ";
    for(k=1;k<=t2;k++)
    cout<<T2[k]<<' ';
    cout<<endl;
    cout<<"The graph edges are ::\n";
    for(i=1;i<=g;i++)
    cout<<" < "<<graph_edge[i][1]
    <<" , "<<graph_edge[i][2]
    <<" > ::"<<graph_edge[i][3]<<endl;
    cout<<endl<<endl;
                     }
                     }
                     void prims::output()
                     {
                     cout<<"\nThe selected edges are ::\n";
                     for(int i=1;i<=t;i++)
                     cout<<" < "<<tree_edge[i][1]
                     <<" , "<<tree_edge[i][2]
                     <<"> ::"<<tree_edge[i][3]<<endl;
}
int main(int argc, char *argv[])
{
    prims obj;
    obj.input();
    obj.algorithm();
    obj.output();

    system("PAUSE");
    return EXIT_SUCCESS;
}

Read More