programer skripsi tesis tugas akhir
-

Contoh Program Source Code   /

Algoritma Prim Dengan Java

Posted on 09.22
Join with us

Algoritma Prim Dengan Java

Algoritma Prim adl sebuah algoritma dalam graph theory unt mencari pohon rentang minimum unt sebuah graf terhubung berbobot [wikipedia]. Mudahnya, Algoritma Prims adl salah satu aplikasi yang digunakan unt mencari rentang minimum. Untuk lebih jelas akan kita berikan contoh dg gambar :

Algoritma Prim Dengan Java
Algoritma Prim Dengan Java

Terdapat sebuah rangkaian spt pada gambar di atas. Setiap titik disebut dg vertex. Terdapat 6 vertex yaitu A, B, C, D, E, & F.Yang ingin dilakukan di sini adl menghubungkan semua vertex yang ada dg melalui jalur yang menghabiskan cost paling minimal. Dengan memakai algoritma prim kita dapat menentukan jalur tersebut.

Adapun langkah-langkah penyelesainnya adl sebagai berikut :

1. Tentukan titik start. Dalam kasus ini kita tentukan titik startnya adl vertex B.
2. Kemudian buatlah dua buah himpunan. Misalkan himpunan T & S. Dimana elemen dr T adl vertex-vertex yang sudah saling terhubung & elemen himpunan S adl vertex-vertex yang belum terhubung. Pada akhir proses, seluruh elemen F akan berpindah mjd elemen T & F mjd himpunan kosong.
3. Pada awal proses elemen T hanyalah vertex yang mjd titik start (vertex B) & himpunan F berisi vertex-vertex sisanya.
4. T={B} ; F={A,C,D,E,F}

Algoritma Prim Dengan Java
Algoritma Prim Dengan Java


B(- , -) : A(B,1) D(B,1) C(B,5) E(- , – ) F(- ,  -)
Tuliskan semua vertex yang memiliki kemungkinan terhubung dg vertex B secara langsung. Penulisan A(B,1) artinya titik A bisa dihubungkan secara langsung dg vertex B(titik start) dg cost 1. Pada langkah ini vertex E & F tidak dapat terhubung secara langsung sehingga kita menuliskannya dg E(- ,  – ) & F(- ,  -). Kemudian pilihlah jalur yang menghabiskan cost paling minimal. Pada langkah ini terdapat 2 jalur yang memiliki cost paling minimum, pilih saja yang lebih dulu yaitu A(B,1). Dan selanjutnya himpunan T & F mjd T={B,A} ; F={ C,D,E,F} .

5. T={B,A} ; F={C,D,E,F}

A(B , 1) : D(B,1) C(A,3) F(A , 3 ) E(- , -)
Saat ini vertex B & A telah terhubung. Kemudian tuliskan semua kemungkinan vertex yang bisa dihubungkan secara langsung dg vertex – vertex yang telah saling terhubung (bisa vertex A / B). Pada langkah ini vertex E tidak memiliki kemungkinan dihubungkan secara langsung maka dituliskan dg E(- , – ). Kemudian pilih jalur yang menghabiskan cost paling kecil.

Algoritma Prim Dengan Java
Algoritma Prim Dengan Java

6. T={B,A,D} ; F={C,E,F}
D(B,1): C(D,2) E(D , 4) F(A , 3)

Algoritma Prim Dengan Java
Algoritma Prim Dengan Java

7. T={B,A,D,C} ; F={E,F}
C(D,2) : E(C,1) F(A,3)



8. T={B,A,D,C} ; F={C,D,E,F}
E(C,1); F(A,3)



9. Selesai. Semua vertex telah terhubung dg cost 8 (cost optimal).
Begitulah cara kerja dr algoritma Prim. Cukup mudah dipahami bukan? Namun jika kita ingin membuat program dr algoritma prim, menurut kita sangatlah sulit membuat programnya jika kita berpatokan dg cara I yang telah dijelaskan di atas. Untuk membuat programnya lebih baik jika kita memakai cara II yang akan kita jelaskan setelah ini. Cara II lebih mudah jika diimplementasikan ke dalam bentuk program.
Cara II:

1. langkah awal pada Cara II sama dg langkah 1 sampai 3 pada Cara I.
2. kemudian buatlah sebuah tabel(array) yang menyimpan cost – cost antar vertex dr persoalan yang diberikan (persoalan yang akan diselesaikan di sini sama dg persoalan yang diberikan pada Cara I). Jika terdapat dua vertex yang tidak bisa terhubung secara langsung berikanlah nilai.

Contoh Penerapan Kode Program Dengan java

Source code

import java.util.InputMismatchException;
import java.util.Scanner;
public class Prims
{
private boolean unsettled[];
private boolean settled[];
private int numberofvertices;
private int adjacencyMatrix[][];
private int key[];
public static final int INFINITE = 999;
private int parent[];
public Prims(int numberofvertices)
{
this.numberofvertices = numberofvertices;
unsettled = new boolean[numberofvertices + 1];
settled = new boolean[numberofvertices + 1];
adjacencyMatrix = new int[numberofvertices + 1][numberofvertices + 1];
key = new int[numberofvertices + 1];
parent = new int[numberofvertices + 1];
}
public int getUnsettledCount(boolean unsettled[])
{
int count = 0;
for (int index = 0; index < unsettled.length; index++)
{
if (unsettled[index])
{
count++;
}
}
return count;
}
public void primsAlgorithm(int adjacencyMatrix[][])
{
int evaluationVertex;
for (int source = 1; source <= numberofvertices; source++)
{
for (int destination = 1; destination <= numberofvertices; destination++)
{
this.adjacencyMatrix[source][destination] = adjacencyMatrix[source][destination];
}
}
for (int index = 1; index <= numberofvertices; index++)
{
key[index] = INFINITE;
}
key[1] = 0;
unsettled[1] = true;
parent[1] = 1;
while (getUnsettledCount(unsettled) != 0)
{
evaluationVertex = getMimumKeyVertexFromUnsettled(unsettled);
unsettled[evaluationVertex] = false;
settled[evaluationVertex] = true;
evaluateNeighbours(evaluationVertex);
}
}
private int getMimumKeyVertexFromUnsettled(boolean[] unsettled2)
{
int min = Integer.MAX_VALUE;
int node = 0;
for (int vertex = 1; vertex <= numberofvertices; vertex++)
{
if (unsettled[vertex] == true && key[vertex] < min)
{
node = vertex;
min = key[vertex];
}
}
return node;
}
public void evaluateNeighbours(int evaluationVertex)
{
for (int destinationvertex = 1; destinationvertex <= numberofvertices; destinationvertex++)
{
if (settled[destinationvertex] == false)
{
if (adjacencyMatrix[evaluationVertex][destinationvertex] != INFINITE)
{
if (adjacencyMatrix[evaluationVertex][destinationvertex] < key[destinationvertex])
{
key[destinationvertex] = adjacencyMatrix[evaluationVertex][destinationvertex];
parent[destinationvertex] = evaluationVertex;
}
unsettled[destinationvertex] = true;
}
}
}
}
public void printMST()
{
System.out.println("SUMBER: TUJUAN = BERAT");
for (int vertex = 2; vertex <= numberofvertices; vertex++)
{
System.out.println(parent[vertex] + "\t:\t" + vertex +"\t=\t"+ adjacencyMatrix[parent[vertex]][vertex]);
}
}
public static void main(String... arg)
{
int adjacency_matrix[][];
int number_of_vertices;
Scanner scan = new Scanner(System.in);
try
{
System.out.println("Masukkan jumlah simpul");
number_of_vertices = scan.nextInt();
adjacency_matrix = new int[number_of_vertices + 1][number_of_vertices + 1];
System.out.println("Masukkan Matrix tertimbang unt grafik");
for (int i = 1; i <= number_of_vertices; i++)
{
for (int j = 1; j <= number_of_vertices; j++)
{
adjacency_matrix[i][j] = scan.nextInt();
if (i == j)
{
adjacency_matrix[i][j] = 0;
continue;
}
if (adjacency_matrix[i][j] == 0)
{
adjacency_matrix[i][j] = INFINITE;
}
}
}
Prims prims = new Prims(number_of_vertices);
prims.primsAlgorithm(adjacency_matrix);
prims.printMST();
} catch (InputMismatchException inputMismatch)
{
System.out.println("Format masukan salah");
}
scan.close();
}
}


Hasilnya :



$javac Prims.java $java Prims Masukkan jumlah simpul 5 Masukkan Matrix tertimbang unt grafik 0 4 0 0 5 4 0 3 6 1 0 3 0 6 2 0 6 6 0 7 5 1 2 7 0 SUMBER: TUJUAN = BERAT 1 : 2 = 4 5 : 3 = 2 2 : 4 = 6 2 : 5 = 1



Algoritma Prim Dengan Java

Algoritma Prim adl sebuah algoritma dalam graph theory unt mencari pohon rentang minimum unt sebuah graf terhubung berbobot [wikipedia]. Mudahnya, Algoritma Prims adl salah satu aplikasi yang digunakan unt mencari rentang minimum. Untuk lebih jelas akan kita berikan contoh dg gambar :

Algoritma Prim Dengan Java
Algoritma Prim Dengan Java

Terdapat sebuah rangkaian spt pada gambar di atas. Setiap titik disebut dg vertex. Terdapat 6 vertex yaitu A, B, C, D, E, & F.Yang ingin dilakukan di sini adl menghubungkan semua vertex yang ada dg melalui jalur yang menghabiskan cost paling minimal. Dengan memakai algoritma prim kita dapat menentukan jalur tersebut.

Adapun langkah-langkah penyelesainnya adl sebagai berikut :

1. Tentukan titik start. Dalam kasus ini kita tentukan titik startnya adl vertex B.
2. Kemudian buatlah dua buah himpunan. Misalkan himpunan T & S. Dimana elemen dr T adl vertex-vertex yang sudah saling terhubung & elemen himpunan S adl vertex-vertex yang belum terhubung. Pada akhir proses, seluruh elemen F akan berpindah mjd elemen T & F mjd himpunan kosong.
3. Pada awal proses elemen T hanyalah vertex yang mjd titik start (vertex B) & himpunan F berisi vertex-vertex sisanya.
4. T={B} ; F={A,C,D,E,F}

Algoritma Prim Dengan Java
Algoritma Prim Dengan Java


B(- , -) : A(B,1) D(B,1) C(B,5) E(- , – ) F(- ,  -)
Tuliskan semua vertex yang memiliki kemungkinan terhubung dg vertex B secara langsung. Penulisan A(B,1) artinya titik A bisa dihubungkan secara langsung dg vertex B(titik start) dg cost 1. Pada langkah ini vertex E & F tidak dapat terhubung secara langsung sehingga kita menuliskannya dg E(- ,  – ) & F(- ,  -). Kemudian pilihlah jalur yang menghabiskan cost paling minimal. Pada langkah ini terdapat 2 jalur yang memiliki cost paling minimum, pilih saja yang lebih dulu yaitu A(B,1). Dan selanjutnya himpunan T & F mjd T={B,A} ; F={ C,D,E,F} .

5. T={B,A} ; F={C,D,E,F}

A(B , 1) : D(B,1) C(A,3) F(A , 3 ) E(- , -)
Saat ini vertex B & A telah terhubung. Kemudian tuliskan semua kemungkinan vertex yang bisa dihubungkan secara langsung dg vertex – vertex yang telah saling terhubung (bisa vertex A / B). Pada langkah ini vertex E tidak memiliki kemungkinan dihubungkan secara langsung maka dituliskan dg E(- , – ). Kemudian pilih jalur yang menghabiskan cost paling kecil.

Algoritma Prim Dengan Java
Algoritma Prim Dengan Java

6. T={B,A,D} ; F={C,E,F}
D(B,1): C(D,2) E(D , 4) F(A , 3)

Algoritma Prim Dengan Java
Algoritma Prim Dengan Java

7. T={B,A,D,C} ; F={E,F}
C(D,2) : E(C,1) F(A,3)



8. T={B,A,D,C} ; F={C,D,E,F}
E(C,1); F(A,3)



9. Selesai. Semua vertex telah terhubung dg cost 8 (cost optimal).
Begitulah cara kerja dr algoritma Prim. Cukup mudah dipahami bukan? Namun jika kita ingin membuat program dr algoritma prim, menurut kita sangatlah sulit membuat programnya jika kita berpatokan dg cara I yang telah dijelaskan di atas. Untuk membuat programnya lebih baik jika kita memakai cara II yang akan kita jelaskan setelah ini. Cara II lebih mudah jika diimplementasikan ke dalam bentuk program.
Cara II:

1. langkah awal pada Cara II sama dg langkah 1 sampai 3 pada Cara I.
2. kemudian buatlah sebuah tabel(array) yang menyimpan cost – cost antar vertex dr persoalan yang diberikan (persoalan yang akan diselesaikan di sini sama dg persoalan yang diberikan pada Cara I). Jika terdapat dua vertex yang tidak bisa terhubung secara langsung berikanlah nilai.

Contoh Penerapan Kode Program Dengan java

Source code

import java.util.InputMismatchException;
import java.util.Scanner;
public class Prims
{
private boolean unsettled[];
private boolean settled[];
private int numberofvertices;
private int adjacencyMatrix[][];
private int key[];
public static final int INFINITE = 999;
private int parent[];
public Prims(int numberofvertices)
{
this.numberofvertices = numberofvertices;
unsettled = new boolean[numberofvertices + 1];
settled = new boolean[numberofvertices + 1];
adjacencyMatrix = new int[numberofvertices + 1][numberofvertices + 1];
key = new int[numberofvertices + 1];
parent = new int[numberofvertices + 1];
}
public int getUnsettledCount(boolean unsettled[])
{
int count = 0;
for (int index = 0; index < unsettled.length; index++)
{
if (unsettled[index])
{
count++;
}
}
return count;
}
public void primsAlgorithm(int adjacencyMatrix[][])
{
int evaluationVertex;
for (int source = 1; source <= numberofvertices; source++)
{
for (int destination = 1; destination <= numberofvertices; destination++)
{
this.adjacencyMatrix[source][destination] = adjacencyMatrix[source][destination];
}
}
for (int index = 1; index <= numberofvertices; index++)
{
key[index] = INFINITE;
}
key[1] = 0;
unsettled[1] = true;
parent[1] = 1;
while (getUnsettledCount(unsettled) != 0)
{
evaluationVertex = getMimumKeyVertexFromUnsettled(unsettled);
unsettled[evaluationVertex] = false;
settled[evaluationVertex] = true;
evaluateNeighbours(evaluationVertex);
}
}
private int getMimumKeyVertexFromUnsettled(boolean[] unsettled2)
{
int min = Integer.MAX_VALUE;
int node = 0;
for (int vertex = 1; vertex <= numberofvertices; vertex++)
{
if (unsettled[vertex] == true && key[vertex] < min)
{
node = vertex;
min = key[vertex];
}
}
return node;
}
public void evaluateNeighbours(int evaluationVertex)
{
for (int destinationvertex = 1; destinationvertex <= numberofvertices; destinationvertex++)
{
if (settled[destinationvertex] == false)
{
if (adjacencyMatrix[evaluationVertex][destinationvertex] != INFINITE)
{
if (adjacencyMatrix[evaluationVertex][destinationvertex] < key[destinationvertex])
{
key[destinationvertex] = adjacencyMatrix[evaluationVertex][destinationvertex];
parent[destinationvertex] = evaluationVertex;
}
unsettled[destinationvertex] = true;
}
}
}
}
public void printMST()
{
System.out.println("SUMBER: TUJUAN = BERAT");
for (int vertex = 2; vertex <= numberofvertices; vertex++)
{
System.out.println(parent[vertex] + "\t:\t" + vertex +"\t=\t"+ adjacencyMatrix[parent[vertex]][vertex]);
}
}
public static void main(String... arg)
{
int adjacency_matrix[][];
int number_of_vertices;
Scanner scan = new Scanner(System.in);
try
{
System.out.println("Masukkan jumlah simpul");
number_of_vertices = scan.nextInt();
adjacency_matrix = new int[number_of_vertices + 1][number_of_vertices + 1];
System.out.println("Masukkan Matrix tertimbang unt grafik");
for (int i = 1; i <= number_of_vertices; i++)
{
for (int j = 1; j <= number_of_vertices; j++)
{
adjacency_matrix[i][j] = scan.nextInt();
if (i == j)
{
adjacency_matrix[i][j] = 0;
continue;
}
if (adjacency_matrix[i][j] == 0)
{
adjacency_matrix[i][j] = INFINITE;
}
}
}
Prims prims = new Prims(number_of_vertices);
prims.primsAlgorithm(adjacency_matrix);
prims.printMST();
} catch (InputMismatchException inputMismatch)
{
System.out.println("Format masukan salah");
}
scan.close();
}
}


Hasilnya :



$javac Prims.java $java Prims Masukkan jumlah simpul 5 Masukkan Matrix tertimbang unt grafik 0 4 0 0 5 4 0 3 6 1 0 3 0 6 2 0 6 6 0 7 5 1 2 7 0 SUMBER: TUJUAN = BERAT 1 : 2 = 4 5 : 3 = 2 2 : 4 = 6 2 : 5 = 1


Contoh Program Algoritma Prim Dengan Java

Source Code Algoritma Prim Dengan Java

Source Code Tutorial belajar Gratis download Flow Chart PDF ZIP RAR DOC Java C# Visual Basic VB PHP Matlab C++ Penerapan implementasi metode algoritma pemrograman

Tutorial belajar Algoritma Prim Dengan Java

VB PHP Matlab C++ Penerapan implementasi metode algoritma pemrograman Source Code Tutorial belajar Gratis download Flow Chart PDF ZIP RAR DOC Java C# Visual Basic

Gratis download Algoritma Prim Dengan Java

Chart PDF ZIP RAR DOC Java C# Visual Basic VB PHP Matlab C++ Penerapan implementasi metode algoritma pemrograman Source Code Tutorial belajar Gratis download Flow

Penerapan implementasi Algoritma Prim Dengan Java Algoritma Prim Dengan Java

Posted by: Project-G Contoh Program Algoritma Prim Dengan Java Updated at : 09.22
Jika Anda perlu source code terkait dengan artikel di atas atau ada yang ingin di tanyakan anda bisa melakukan konsultasi gratis kepada kami, melalui form di bawah. Hasil konsultasi akan di kirimkan ke email Anda. Kami mohon supportnya dengan mengklik beberapa tombol berikut :


Contoh Program Algoritma Prim Dengan Java

perhatian

Informasi Penting Untuk Mahasiswa !

Kami menawarkan layanan jasa konsultan bimbingan pembuatan program untuk Tesis Skripsi dan Tugas Akhir Informatika, Komputer, Elektro dan Teknik lainnya yang bidang minatnya mengarah ke teknologi informasi. BASED PROJECT :Mobile Development (Java, Adobe, AS3, Android, BB, iOS, WPhone dll), Web & Desktop Development (.Net, C#, MATLAB, PHP, Delphi, Visual Basic dll). BONUS : Di bimbing untuk penguasaan materi dan coding dan revisi.
detail
Label: , ,
Konsultasi gratis