Tampilkan postingan dengan label Diskrit. Tampilkan semua postingan
Tampilkan postingan dengan label Diskrit. Tampilkan semua postingan

Kamis, 19 Juni 2014

Minimum Spanning Tree Metode Kruskal pada Matematika Diskrit


Algoritma Program Pascal untuk Minimum Spanning Tree Metode Kruskal pada Matematika Diskrit

program minimum_spanning_tree;
uses wincrt;
var
   i, j, k, n, y, z, cek, jarak: integer;
   v, vb                       : array [1..20,1..20] of integer;
   urutan, lewat               : array [1..20] of integer;
label 1, 2, 3;

Begin
1:
  {Input}
  writeln('Program Minimum Spanning Tree');
  write('Masukkan besar matriks adjacency (n x n): ');readln(n);
  for i:= 1 to n do
  begin
       for j:= i to n do
       begin
            if j <> i then
            begin
                 write('V',i,'V',j,' = ');readln(v[i,j]);
                 v[j,i]:= v[i,j];
                 vb[i,j]:= v[i,j];
                 vb[j,i]:= v[j,i];
            end;
       end;
  end;


2:
  {Cetak Matriks Adjacency}
  write('    ');
  for i:= 1 to n do
  begin
       write('  V',i);
  end;
  writeln;
  for i:= 1 to n do
  begin
       write('V',i,'|');
       for j:= 1 to n do
       begin
            if v[i,j-1] < 10 then write('   ',v[i,j]);
            if v[i,j-1] >= 10 then write('  ',v[i,j]);
       end;
       writeln('   |');
  end;

  if cek = 0 then
  begin
       writeln;
       writeln('Benarkan ini matriks adjacency yang anda inginkan?');
       writeln('1. Ya   2. Tidak');readln(k);
  end;

  if cek = 0 then
  begin
       {Jik dipilih ya, maka proses cetak matriks diulangi}
       if k = 1 then
       begin
            cek:= 1;
            clrscr;
            goto 2;
       end;

       {Jika dipilih tidak, maka proses input akan diulangi}
       if k = 2 then
       begin
            for i:= 1 to n do
            begin
                 for j:= 1 to n do
                 begin
                      v[i,j]:= 0;
                 end;
            end;
            clrscr;
            goto 1;
       end;
  end;

  {Pencarian urutan}
  cek:= 1;
  repeat
        k:= 10000;

        for i:= 1 to n do
        begin
             for j:= i to n do
             begin
                  if j <> i then
                  begin
                       if  vb[i,j] <> 0 then
                       begin
                            if v[i,j] < k then
                            begin
                                 k:=  vb[i,j];
                                 y:= i;
                                 z:= j;
                            end;
                       end;
                  end;
             end;
        end;

        vb[y,z]:= 0;
        urutan[cek]:= k;
        cek:= cek + 1;
  until cek > 2*n;

  {Cetak urutan}
  writeln;
  writeln('Ukuran dari terkecil adalah');
  for i:= 1 to 20 do
  begin
       if urutan[i] <> 0 then write(' ',urutan[i]);
  end;
  writeln;

  {Cetak minimum spanning tree}
  writeln;
  writeln('Jadi minimum spanning tree dari graf tersebut adalah ');
  z:= 1;
  cek:= 1;
  repeat
        write('V',z);
        k:= 10000;

        for i:= 1 to n do
        begin
             if lewat[i] <> 1 then
             begin
                  if z <> i then
                  begin
                       if v[z,i] <> 0 then
                       begin
                            if v[z,i] < k then
                            begin
                                 k:= v[z,i];
                                 j:= i;
                            end;
                       end;
                  end;
             end;
        end;

        lewat[z]:= 1;
        cek:= cek + 1;
        jarak:= jarak + k;
        z:= j;
  until cek = n;
  write('V',z,' = ',jarak);
End.



Preview Program:

Metode Djikstra pada Matematika Diskrit

Algoritma program Pascal untuk Metode Djikstra pada Matematika Diskrit


program djikstra;

uses wincrt;

var

   i, j, k, n, x, y, cek: integer;

   v                    : array [1..10,1..10] of integer;

   nilai, hasil         : array [1..10] of integer;

label 1, 2, 3;



Begin

1:

  {Input}

  writeln('Program Pencarian Lintasan Terpendek');

  write('Masukkan besar matriks adjacency (n x n): ');readln(n);

  for i:= 1 to n do

  begin

       for j:= 1 to n do

       begin

            if j <> i then

            begin

                 writeln('Masukkan 0 jika tidak hubungan antar vertex.');

                 write('V',i,'V',j,' = ');readln(v[i,j]);

                 clrscr;

            end;

       end;

  end;




2:

  {Cetak Matriks Adjacency}

  write('    ');

  for i:= 1 to n do

  begin

       write('  V',i);

  end;

  writeln;

  for i:= 1 to n do

  begin

       write('V',i,'|');

       for j:= 1 to n do

       begin

            if v[i,j-1] < 10 then write('   ',v[i,j]);

            if v[i,j-1] >= 10 then write('  ',v[i,j]);

       end;

       writeln('   |');

  end;



  if cek = 0 then

  begin

       writeln;

       writeln('Benarkan ini matriks adjacency yang anda inginkan?');

       writeln('1. Ya   2. Tidak');readln(k);

  end;



  if cek = 0 then

  begin

       {Jika dipilih ya, maka proses cetak matriks diulangi}

       if k = 1 then

       begin

            cek:= 1;

            clrscr;

            goto 2;

       end;



       {Jika dipilih tidak, maka proses input akan diulangi}

       if k = 2 then

       begin

            for i:= 1 to n do

            begin

                 for j:= 1 to n do

                 begin                                               

                      v[i,j]:= 0;

                 end;

            end;

            clrscr;

            goto 1;

       end;

  end;



  {Input vertex awal dan akhir}

  writeln;

  write('Masukkan vertex awal : V');readln(x);

  write('Masukkan vertex akhir: V');readln(y);



  writeln;

  write('    V1');

  for i:= 2 to n do

  begin

       write('      V',i);

  end;

  writeln;

  for i:= 1 to n do

  begin

       if i <> x then write('| -,0,0 ');

       if i = x then write('| 0,1,1 ');

  end;

  writeln('|');

  hasil[x]:= 1;

  nilai[x]:= 0;



  repeat

        {Pencarian pivot baru}

        k:= nilai[x];

        for i:= 1 to n do

        begin

             if hasil[i] <> 1 then

             begin

                  if v[x,i] <> 0 then

                  begin

                       if nilai[i] = 0 then nilai[i]:= v[x,i] + k;

                       if nilai[i] <> 0 then

                       begin

                            if v[x,i] + k < nilai[i] then nilai[i]:= v[x,i] + k;

                       end;

                  end;

             end;

        end;



        {Cetak nilai pivot}

        for i:= 1 to n do

        begin

             if hasil[i] <> 1 then

             begin

                  if nilai[i] <> 0 then

                  begin

                       if nilai[i] < 10 then write('| ',nilai[i],',0,0 ');

                       if nilai[i] >= 10 then write('|',nilai[i],',0,0 ');

                  end;

                  if nilai[i] = 0 then write('| -,0,0 ');

             end;



             if hasil[i] = 1 then

             begin

                  if nilai[i] <> 0 then

                  begin

                       if nilai[i] < 10 then write('| ',nilai[i],',1,0 ');

                       if nilai[i] >= 10 then write('|',nilai[i],',1,0 ');

                  end;

                  if nilai[i] = 0 then write('| ',nilai[i],',1,0 ');

             end;

        end;

        writeln('|');



        cek:= 10000;

        for i:= 1 to n do

        begin

             if hasil[i] <> 1 then

             begin

                  if nilai[i] <> 0 then

                  begin

                       if nilai[i] < cek then

                       begin

                            cek:= nilai[i];

                            x:= i;

                       end;

                  end;

             end;

        end;

        hasil[x]:= 1;

        nilai[x]:= cek;



        {Cetak pivot baru}

        for i:= 1 to n do

        begin

             if i = x then write('| ',nilai[i],',1,1 ');

             if i <> x then

             begin

                  if hasil[i] <> 1 then

                  begin

                       if nilai[i] <> 0 then

                       begin

                            if nilai[i] < 10 then write('| ',nilai[i],',0,0 ');

                            if nilai[i] >= 10 then write('|',nilai[i],',0,0 ');

                       end;

                       if nilai[i] = 0 then write('| -,0,0 ');

                  end;

                  if hasil[i] = 1 then

                  begin

                       if nilai[i] <> 0 then

                       begin

                            if nilai[i] < 10 then write('| ',nilai[i],',1,0 ');

                            if nilai[i] >= 10 then write('|',nilai[i],',1,0 ');

                       end;

                       if nilai[i] = 0 then write('| ',nilai[i],',1,0 ');

                  end;

             end;

        end;

        writeln('|');

  until x = y;

End.



Preview Program:

Related Posts Plugin for WordPress, Blogger...