Algoritma, Struktur Data, dan Pemrograman: Bab 12. Java Struktur Data dan Pemrograman GUI

Tuesday, December 20, 2016

Bab 12. Java Struktur Data dan Pemrograman GUI

Bab.12 Graf Dan Aplikasinya

Tujuan Instruksional
· Memodelkan permasalahan-permasalahan di dunia nyata menggunakan graf. · Mendeskripsikan peristilahan graf: verteks, tepi, graf sederhana, graf terbobot/tak-berbobot, dan graf terarah/tak-terarah. · Memodelkan graf menggunakan antarmuka Graph, kelas AbstractGraph, dan kelas UnweightedGraph. · Menampilkan graf secara visual.	· Merepresentasikan penjelajahan suatu graf menggunakan kelas AbstractGraph.Tree. · Mendesain dan mengimplementasikan pencarian depth-first. · Mendesain dan mengimplementasikan pencarian breadth-first.

12.1 Introduksi

Graf memainkan peranan penting di dalam pemodelan permasalahan-permasalahan di dunia nyata. Sebagai contoh, permasalahan dalam menemukan jarak terpendek dari dua kota dapat dimodelkan menggunakan suatu graf, dimana verteks merepresentasikan kota dan tepi merepresentasikan jalan dan jarak antar dua kota yang bertetangga, seperti tertampil pada Gambar 12.1. Permasalahan dalam mencari jarak terpendek antara dua kota direduksi menjadi permasalahan pencarian jalur terpendek antara dua verteks di dalam suatu graf.

Gambar 12.1 Suatu graf dapat digunakan untuk memodelkan jarak antara kota

Graf biasanya diselesaikan menggunakan algoritma. Algoritma graf memiliki banyak terapan di berbagai bidang, seperti ilmu komputer, matematika, biologi, teknik, ekonomi, genetika, dan ilmu sosial. Bab ini akan menyajikan beberapa algoritma untuk melakukan pencarian depth-first dan pencarian breadth-first beserta aplikasinya.

12.2 Terminologi Graf

Bab ini tidak mengasumsikan bahwa pembaca memiliki pengetahuan dasar tentang teori graf atau matematika diskrit. Jadi, akan digunakan peristilahan sederhana dalam mendefinisikan graf.

Apa itu graf? Graf merupakan struktur matematik yang merepresentasikan relasi antar entitas di dunia nyata. Sebagai contoh, graf pada Gambar 12.1 merepresentasikan jalan dan jaraknya di antara kota-kota di Sumatera Utara (hanya ilustrasi saja, tidak sesuai dengan peta sebenarnya).

Graf memuat sehimpunan verteks (atau simpul atau titik) dan sehimpunan tepi yang menghubungkan antar verteks. Untuk lebih memudahkan, suatu graf didefinisikan sebagai G = (V, E), dimana V merepresentasikan sehimpunan verteks dan E merepresentasikan sehimpunan tepi. Sebagai contoh, V dan E untuk graf pada Gambar 12.1 adalah sebagai berikut:

V = {"Balige", "Parapat", "Raya",

"Tebing", "Siantar", "Perdagangan", "Sipirok", "Tanjung",

"Binjai", "Medan", "Asahan", "Kisaran"};

E = {{"Balige", "Parapat"},{"Balige", "Tebing"},

{"Balige", "Siantar"}, {"Parapat", "Siantar"},

...

};

Suatu graf bisa terarah atau tak-terarah. Di dalam suatu graf terarah, setiap tepi memiliki arah, yang mengindikasikan bahwa Anda bergerak dari satu verteks ke verteks lain melalui tepi. Anda bisa memodelkan relasi orangtua/anak menggunakan suatu graf terarah, dimana tepi dari verteks A ke B mengindikasikan bahwa A adalah orangtua dari B.

Gambar 12.2 Graf dalam beebrapa rupa atau bentuk

Gambar 12.2a menampilkan suatu graf terarah. Di dalam suatu graf tak-terarah, Anda dapat bergerak dalam dua arah antar verteks. Graf pada Gambar 12.1 merupakan graf tak-terarah.

Tepi bisa terbobot atau tak-terbobot. Sebagai contoh, setiap tepi pada Gambar 12.1 memiliki suatu bobot yang merepresentasikan jarak antar dua kota.

Dua verteks di dalam suatu graf dikatakan bertetangga bila keduanya dihubungkan oleh tepi yang sama. Sama halnya, dua tepi dikatakan bertetangga bila keduanya terhubung ke verteks yang sama. Suatu tepi di dalam suatu graf yang menghubungkan dua verteks dikatakan sebagai insiden terhadap dua verteks tersebut. Derajat suatu verteks adalah jumlah tepi yang berinsiden terhadapnya.

Loop adalah suatu tepi yang menghubungkan verteks ke dirinya sendiri. Jika dua verteks dihubungkan oleh dua atau lebih tepi, maka tepi-tepi tersebut dikatakan tepi paralel. Graf sederhana adalah graf yang tidak memiliki loop dan tepi paralel. Graf sempurna adalah graf dimana setiap pasangan verteks (dua verteks) saling terhubung, seperti ditunjukkan pada Gambar 12.2b.

12.3 Merepresentasikan Graf

Untuk menulis suatu program yang memproses dan memanipulasi graf, Anda harus menyimpan atau merepresentasikan graf di dalam komputer.

12.3.1 Merepresentasikan Verteks

Verteks dapat disimpan di dalam suatu array. Sebagai contoh, Anda bisa menyimpan semua nama kota di dalam Gambar 12.1 menggunakan array berikut:

String[] verteks = {"Balige", "Parapat", "Raya", "Tebing", "Siantar",

"Perdagangan", "Sipirok", "Tanjung", "Binjai", "Medan", "Asahan",

"Kisaran"};

Verteks bisa pula merupakan objek sembarang tipe. Sebagai contoh, Anda bisa memandang kota sebagai objek yang memuat informasi seperti nama, populasi, dan walikota. Jadi, Anda mendefinisikan verteks sebagai berikut:

Kota kota0 = new Kota("Siantar", 563374, "Mangasi Siahaan");

...

Kota kota11 = new Kota("Medan", 1000203, "Timbul Pujianto");

Object[] verteks = { kota 0, kota 1, ..., kota 11};

public class Kota {

private String namaKota;

private int populasi;

private String walikota;

public City(String namaKota, int populasi, String walikota) {

this.namaKota = namaKota;

this.populasi = populasi;

this.walikota = walikota;

}

public String dapatNamaKota() {

return namaKota;

}

public int dapatPopulasi() {

return populasi;

}

public String dapatWalikota() {

return walikota;

}

public void tetapkanWalikota(String walikota) {

this.walikota = walikota;

}

public void tetapkanPopulasi(int populasi) {

this.populasi = populasi;

}

Verteks dapat dilabel menggunakan angka-angka biasa 0, 1, 2, 3, ..., n – 1, untuk suatu graf dengan n verteks. Jadi, verteks[0] merepresentasikan “Balige”, verteks[1] merepresentasikan “Parapat”, dan seterusnya, seperti tertampil pada Gambar 12.3.

Gambar 12.3 Suatu array menyimpan nama-nama verteks

12.3.2 Merepresentasikan Tepi: Array Tepi

Tepi-tepi dapat direpresentasikan menggunakan suatu array dua dimensi. Sebagai contoh, Anda dapat menyimpan semua tepi dalam graf pada Gambar 12.1 menggunakan array berikut:

int[][] tepi = {

{0, 1}, {0, 3}, {0, 4},

{1, 0}, {1, 2}, {1, 4},

{2, 1}, {2, 4}, {2, 5}, {2, 6},

{3, 0}, {3, 4}, {3, 5}, {3, 8}, {3, 9},

{4, 0}, {4, 1}, {4, 2}, {4, 3}, {4, 5},

{5, 2}, {5, 3}, {5, 4}, {5, 6}, {5, 9}, {5, 10},

{6, 2}, {6, 5}, {6, 7}, {6, 10},

{7, 6}, {7, 10}, {7, 11},

{8, 3}, {8, 9},

{9, 3}, {9, 5}, {9, 8}, {9, 10},

{10, 5}, {10, 6}, {10, 7}, {10, 9}, {10, 11},

{11, 7}, {11, 10}

};

Ini dikenal dengan representasi tepi menggunakan array.

12.3.3 Merepresentasikan Tepi: Objek Edge

Cara lain untuk merepresentasikan tepi adalah dengan mendefinisikan tepi-tepi sebagai objek dan menyimpannya di dalam java.util.ArrayList. Kelas Edge dapat didefinisikan sebagai berikut:

public class Edge {

int u;

int v;

public Edge(int u, int v) {

this.u = u;

this.v = v;

}

Sebagai contoh, Anda bisa menyimpan semua tepi di dalam graf pada Gambar 12.1 menggunakan list berikut:

java.util.ArrayList<Edge> list = new java.util.ArrayList<Edge>();

list.add(new Edge(0, 1));

list.add(new Edge(0, 3));

list.add(new Edge(0, 4));

...

Menyimpan objek-objek Edge di dalam suatu ArrayList sangat bermanfaat bila Anda tidak terlalu mengerti teori graf.

Representasi tepi menggunakan array atau objek Edge berguna sebagai pengetahuan saja, tetapi kurang efisien bila diimplementasikan. Pada dua bagian ke depan, akan disajikan representasi graf menggunakan matriks kebertetanggaan (adjacency) dan list kebertetanggaan. Kedua struktur data ini efisien untuk memproses graf.

12.3.4 Merepresentasikan Tepi: Matriks Kebertetanggaan

Diasumsikan bahwa graf memiliki n buah verteks. Anda bisa menggunakan suatu matriks dua dimensi n x n, katakanlah matriksKebertetanggaan, untuk merepresentasikan tepi-tepi. Setiap elemen di dalam array adalah 0 atau 1. matriksKebertetanggaan[i][j] bernilai 1 jika terdapat tepi dari verteksi i ke verteks j. Sebaliknya, matriksKebertetanggaan[i][j] bernilai 0. Jika graf tidak terarah, maka matriksKebertetanggaan akan berupa matriks simmetrik, karena matriksKebertetanggaan[i][j] akan sama dengan matriksKebertetanggaan[j][i]. Sebagai contoh, tepi-tepi dalam graf pada Gambar 12.1 dapat direpresentasikan menggunakan matriks kebertetangaan sebagai berikut:

int[][] matriksKebertetanggaan = {

{0, 1, 0, 1, 1, 0, 0, 0, 0, 0, 0, 0}, // Balige

{1, 0, 1, 0, 1, 0, 0, 0, 0, 0, 0, 0}, // Parapat

{0, 1, 0, 0, 1, 1, 1, 0, 0, 0, 0, 0}, // Raya

{1, 0, 0, 0, 1, 1, 0, 0, 1, 1, 0, 0}, // Tebing

{1, 1, 1, 1, 0, 1, 0, 0, 0, 0, 0, 0}, // Siantar

{0, 0, 1, 1, 1, 0, 1, 0, 0, 1, 1, 0}, // Perdagangan

{0, 0, 1, 0, 0, 1, 0, 1, 0, 0, 1, 0}, // Sipirok

{0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 1, 1}, // Tanjung

{0, 0, 0, 1, 0, 0, 0, 0, 0, 1, 0, 0}, // Binjai

{0, 0, 0, 1, 0, 1, 0, 0, 1, 0, 1, 0}, // Medan

{0, 0, 0, 0, 0, 1, 1, 1, 0, 1, 0, 1}, // Asahan

{0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 1, 0} // Kisaran

};

Matriks kebertetanggaan untuk graf terarah pada Gambar 12.2a dapat direpresentasikan sebagai berikut:

int[][] a = {{0, 0, 1, 0, 0}, // Palma

{0, 0, 1, 0, 0}, // Juita

{0, 0, 0, 0, 1}, // Maria

{0, 0, 0, 0, 1}, // Cinthia

{0, 0, 0, 0, 0} // Widy

};

12.3.5 Merepresentasikan Tepi: List Kebertetanggaan

Untuk merepresentasikan tepi menggunakan list kebertetangaan, diperlukan untuk mendefinisikan array list. Array memiliki n buah entri. Setiap entri merupakan suatu list berantai. List berantai untuk verteks i memuat semua verteks j sehingga terdapat suatu tepi dari verteks i ke verteks j. Sebagai contoh, untuk merepresentasikan tepi-tepi di dalam graf pada Gambar 12.1, Anda perlu menciptakan suatu array yang memuat list berantai sebagai berikut:

java.util.LinkedList[] tetangga = new java.util.LinkedList[12];

tetangga[0] memuat semua verteks yang bertetangga dengan verteks 0 (Balige), tetangga[1] memuat semua verteks yang bertetangga dengan verteks 1 (Parapat), dan seterusnya, seperti ditampilkan pada Gambar 12.4.

Untuk merepresentasikan tepi-tepi di dalam graf pada Gambar 12.2a, Anda bisa menciptakan suatu array yang memuat list berantai sebagai berikut:

java.util.LinkedList[] tetangga = new java.util.LinkedList[5];

tetangga[0] memuat semua verteks yang diarahkan dari verteks 0 melalui tepi-tepi terarah, tetangga[1] memuat semua verteks yang diarahkan dari verteks 1 melalui tepi-tepi terarah, dan seterusnya, seperti tertampil pada Gambar 12.5.

Gambar 12.4 Tepi-tepi di dalam graf pada Gambar 12.1 direpresentasikan menggunakan list berantai

Gambar 12.5 Tepi-tepi di dalam graf pada Gambar 12.2a direpresentasikan menggunakan list berantai

Untuk fleksibilitas dan kemudahan, akan digunakan list array untuk merepresentasikan array. Juga, akan digunakan list array menggantikan list berantai, karena algoritma ini hanya memerlukan pencarian untuk verteks-verteks tetangga di dalam list. Penggunaan list array lebih efisien untuk kasus ini. Pada penggunaan list array, list kebertetangaan pada Gambar 12.4 dapat dibangun sebagai berikut:

List<ArrayList<Integer>> tetangga

= new ArrayList<List<Integer>>();

tetangga.add(new ArrayList<Integer>());

tetangga.get(0).add(1); tetangga.get(0).add(3);

tetangga.get(0).add(5);

tetangga.add(new ArrayList<Integer>());

tetangga.get(1).add(0); tetangga.get(1).add(2);

tetangga.get(1).add(3);

...

12.4 Memodelkan Graf

JCF (JAVA Collections Framework) berperan sebagai suatu contoh baik dalam mendesain struktur data kompleks. Fitur-fitur umum struktur data didefinisikan di dalam antarmuka Collections, Set, dan List. Kelas-kelas abstrak (AbstractCollection, AbstractSet, dan AbstractList) secara parsial mengimplementasikan ketiga antarmuka tersebut. Kelas-kelas konkrit (HashSet, LinkedHashSet, TreeSet, ArrayList, LinkedList, dan PriorityQueue) menyediakan implementasi-implementasi konkrit. Selanjutnya akan didefinisikan suatu antarmuka yang dinamai Graph yang memuat semua operasi umum dan suatu kelas abstrak yang dinamai AbstractGraph yang secara parsial mengimplementasikan antarmuka Graph. Beberapa graf konkrit akan ditambahkan ke dalam perancangan. Misalnya, akan didefinisikan dua graf yang dinamai UnweightedGraph dan WeightedGraph. Relasi antarmuka dan kelas diilustrasikan pada Gambar 12.6.

Gambar 12.6 Graf dapat dimodelkan menggunakan antarmuka, kelas abstrak, dan kelas konkrit

Apakah itu operasi-operasi umum untuk suatu graf? Pada umumnya, Anda perlu mendapatkan jumlah verteks di dalam suatu graf, mendapatkan semua verteks di dalam suatu graf, mendapatkan objek verteks dengan indeks tertentu, mendapatkan indeks verteks dengan nama tertentu, mendapatkan tetangga-tetangga suatu verteks, mendapatkan matriks kebertetanggaan, mendapatkan derajat suatu verteks, melakukan pencarian depth-first, dan melakukan pencarian breadth-first. Pencarian depth-first dan pencarian breadt-first akan dikenalkan pada bagian selanjutnya. Gambar 12.7 mengilustrasikan semua metode ini di dalam diagram UML.

AbstractGraph tidak mengenalkan metode baru. List verteks dan list kebertetanggaan didefinisikan di dalam kelas AbstractGraph. Dengan bidang-bidang data ini, sudah cukup untuk mengimplementasikan semua metode yang didefinisikan di dalam antarmuka Graph. UnweightedGraph sebenarnya hanya mewarisi AbstractGraph dengan empat konstruktor untuk menciptakan instans-instans Graph konkrit. UnweightedGraph mewarisi semua metode dari AbstractGraph dan tidak memberikan metode baru.

Gambar 12.7 Antarmuka Graph mendefinisikan operasi-operasi umum untuk semua tipe graf

Diasumsikan bahwa semua antarmuka dan kelas tersedia. Kode12.1 menyajikan suatu program uji yang menciptakan suatu graf pada Gambar 12.1 dan graf lain pada Gambar 12.2a.

Kode12.1 UjiGraf.java

public class UjiGraf {

public static void main(String[] args) {

String[] verteks = {"Balige", "Parapat", "Raya", "Tebing", "Siantar",

"Perdagangan", "Sipirok", "Tanjung", "Binjai", "Medan", "Asahan",

"Kisaran"};

// Array tepi untuk graf pada Gambar 12.1

int[][] tepi = {

{0, 1}, {0, 3}, {0, 4},

{1, 0}, {1, 2}, {1, 4},

{2, 1}, {2, 4}, {2, 5}, {2, 6},

{3, 0}, {3, 4}, {3, 5}, {3, 8}, {3, 9},

{4, 0}, {4, 1}, {4, 2}, {4, 3}, {4, 5},

{5, 2}, {5, 3}, {5, 4}, {5, 6}, {5, 9}, {5, 10},

{6, 2}, {6, 5}, {6, 7}, {6, 10},

{7, 6}, {7, 10}, {7, 11},

{8, 3}, {8, 9},

{9, 3}, {9, 5}, {9, 8}, {9, 10},

{10, 5}, {10, 6}, {10, 7}, {10, 9}, {10, 11},

{11, 7}, {11, 10}

};

Graph<String> graf1 =

new UnweightedGraph<String>(tepi, verteks);

System.out.println("Jumlah verteks di dalam graf1: "

+ graf1.getSize());

System.out.println("Verteks dengan indeks 1 adalah "

+ graf1.getVertex(1));

System.out.println("Indeks untuk Siantar adalah " +

graf1.getIndex("Siantar"));

System.out.println("Tepi untuk graf1:");

graf1.printEdges();

System.out.println("Matriks kebertetanggaan untuk graf1:");

graf1.printAdjacencyMatrix();

// List yang memuat objek-objek tepi untuk graf pada Gambar 12.2a

String[] nama = {"Palma", "Juita", "Maria", "Cinthia", "Widy"};

java.util.ArrayList<AbstractGraph.Edge> tepiList

= new java.util.ArrayList<AbstractGraph.Edge>();

tepiList.add(new AbstractGraph.Edge(0, 2));

tepiList.add(new AbstractGraph.Edge(1, 2));

tepiList.add(new AbstractGraph.Edge(2, 4));

tepiList.add(new AbstractGraph.Edge(3, 4));

// Menciptakan suatu graf dengan 5 verteks

Graph<String> graf2 = new UnweightedGraph<String>

(tepiList, java.util.Arrays.asList(nama));

System.out.println("Jumlah verteks di dalam graf2: "

+ graf2.getSize());

System.out.println("Tepi untuk graf2:");

graf2.printEdges();

System.out.println("\nMatriks kebertetanggaan untuk graf2:");

graf2.printAdjacencyMatrix();

for (int i = 0; i < 5; i++)

System.out.println("verteks " + i + ": " + graf2.getVertex(i));

}

Keluaran

Jumlah verteks di dalam graf1: 12

Verteks dengan indeks 1 adalah Parapat

Indeks untuk Siantar adalah 4

Tepi untuk graf1:

Verteks 0: (0, 1) (0, 3) (0, 4)

Verteks 1: (1, 0) (1, 2) (1, 4)

Verteks 2: (2, 1) (2, 4) (2, 5) (2, 6)

Verteks 3: (3, 0) (3, 4) (3, 5) (3, 8) (3, 9)

Verteks 4: (4, 0) (4, 1) (4, 2) (4, 3) (4, 5)

Verteks 5: (5, 2) (5, 3) (5, 4) (5, 6) (5, 9) (5, 10)

Verteks 6: (6, 2) (6, 5) (6, 7) (6, 10)

Verteks 7: (7, 6) (7, 10) (7, 11)

Verteks 8: (8, 3) (8, 9)

Verteks 9: (9, 3) (9, 5) (9, 8) (9, 10)

Verteks 10: (10, 5) (10, 6) (10, 7) (10, 9) (10, 11)

Verteks 11: (11, 7) (11, 10)

Matriks kebertetanggaan untuk graf1:

0 1 0 1 1 0 0 0 0 0 0 0

1 0 1 0 1 0 0 0 0 0 0 0

0 1 0 0 1 1 1 0 0 0 0 0

1 0 0 0 1 1 0 0 1 1 0 0

1 1 1 1 0 1 0 0 0 0 0 0

0 0 1 1 1 0 1 0 0 1 1 0

0 0 1 0 0 1 0 1 0 0 1 0

0 0 0 0 0 0 1 0 0 0 1 1

0 0 0 1 0 0 0 0 0 1 0 0

0 0 0 1 0 1 0 0 1 0 1 0

0 0 0 0 0 1 1 1 0 1 0 1

0 0 0 0 0 0 0 1 0 0 1 0

Jumlah verteks di dalam graf2: 5

Tepu untuk graf2:

Verteks 0: (0, 2)

Verteks 1: (1, 2)

Verteks 2: (2, 4)

Verteks 3: (3, 4)

Verteks 4:

Matriks kebertetanggaan untuk graf2:

0 0 1 0 0

0 0 0 0 1

0 0 0 0 0

verteks 0: Palma

verteks 1: Juita

verteks 2: Maria

verteks 3: Cinthia

verteks 4: Widy

Program menciptakan graf1 untuk graf pada Gambar 12.1 pada baris 3-24. Verteks-verteks untuk graf1 didefinisikan pada baris 3-5. Tepi-tepi untuk graf1 didefinisikan pada baris 8-21. Tepi-tepi tersebut direpresentasikan menggunakan suatu array dua dimensi. Untuk setiap baris i di dalam array, tepi[i][0] dan tepi[i][1] mengindikasikan bahwa terdapat suatu tepi dari verteks tepi[i][0] ke verteks tepi[i][1]. Sebagai contoh, baris pertama {0, 1} merepresentasikan tepi dari verteks 0 (tepi[0][0]) ke verteks 1 (tepi[0][1]). Baris {0, 4} merepresentasikan tepi dari verteks 0 (tepi[2][0]) ke verteks 4 (tepi[2][1]). Graf diciptakan pada baris 24. Baris 32 memanggil metode printEdges() pada graf1 untuk menampilkan semua tepi pada graf1. Baris 34 memanggil metode printAdjacencyMatrix() pada graf1 untuk menampilkan matriks kebertetanggaan pada graf1.

Program menciptakan graf2 untuk graf pada Gambar 12.2a pada baris 37-46. Semua tepi untuk graf2 didefinisikan pada baris 40-43. graf2 diciptakan menggunakan suatu list yang memuat objek-objek Edge pada baris 46. Baris 50 memanggil metode printEdges() pada graf2 untuk menampilkan semua tepi di dalam graf2. Baris 52 memanggil printAdjacencyMatrix() pada graf2 untuk menampilkan matriks kebertetanggaan.

Perhatikan bahwa kedua graf memuat verteks string. Verteks-verteks tersebut diasosiasikan dengan indeks 0, 1,...,n-1. Indeks merupakan lokasi verteks di dalam verteks. Sebagai contoh, indeks dari verteks Siantar adalah 4.

Sekarang perhatian akan dialihkan untuk mengimplementasikan antarmuka dan kelas. Kode12.2, kode12.3, dan kode12.4 memberikan antarmuka Graph, kelas AbstractGraph, dan kelas UnweightedGraph.

Kode12.2 Graph.java

public interface Graph<V> {

/** Mengembalikan jumlah verteks di dalam graf */

public int getSize();

/** Mengembalikan verteks-verteks di dalam graf */

public java.util.List<V> getVertices();

/** Mengembalikan objek untuk indeks verteks tertentu */

public V getVertex(int index);

/** Mengembalikan indeks untuk objek verteks tertentu */

public int getIndex(V v);

/** Mengembalikan tetangga-tetangga verteks dengan indeks tertentu */

public java.util.List<Integer> getNeighbors(int index);

/** Mengembalikan derajat suatu verteks tertentu */

public int getDegree(int v);

/** Mengembalikan matriks kebertetanggaan */

public int[][] getAdjacencyMatrix();

/** Menampilkan matriks kebertetanggaan */

public void printAdjacencyMatrix();

/** Menampilkan tepi-tepi */

public void printEdges();

/** Mendapatkan pohon pencarian depth-first */

public AbstractGraph<V>.Tree dfs(int v);

/** Mendapatkan pohon pencarian breadth-first */

public AbstractGraph<V>.Tree bfs(int v);

}

Kode12.3 AbstractGraph.java

100

101

102

103

104

105

106

107

108

109

110

111

112

113

114

115

116

117

118

119

120

121

122

123

124

125

126

127

128

129

130

131

132

133

134

135

136

137

138

139

140

141

142

143

144

145

146

147

148

149

150

151

152

153

154

155

156

157

158

159

160

161

162

163

164

165

166

167

168

169

170

171

172

173

174

175

176

177

178

179

180

181

182

183

184

185

186

187

188

189

190

191

192

193

194

195

196

197

198

199

200

201

202

203

204

205

206

207

208

209

210

211

212

213

214

215

216

217

218

219

220

221

222

223

224

225

226

227

228

229

230

231

232

233

234

235

236

237

238

239

240

241

242

243

244

245

246

247

248

249

250

251

252

253

254

255

256

257

258

259

260

261

262

263

264

265

266

267

268

269

270

271

272

273

274

275

276

277

278

279

280

281

282

283

284

285

286

287

288

289

import java.util.*;

public abstract class AbstractGraph<V> implements Graph<V> {

protected List<V> verteks; // Menyimpan verteks-verteks

protected List<List<Integer>> tetangga; // List kebertetanggaan

/** Menciptakan suatu graf dari semua tepi dan verteks disimpan di dalam array */

protected AbstractGraph(int[][] tepi, V[] verteks) {

this.verteks = new ArrayList<V>();

for (int i = 0; i < verteks.length; i++)

this.verteks.add(verteks[i]);

createAdjacencyLists(tepi, verteks.length);

}

/** Menciptakan suatu graf dari semua tepi dan verteks, disimpan di dalam List */

protected AbstractGraph(List<Edge> tepi, List<V> verteks) {

this.verteks = verteks;

createAdjacencyLists(tepi, verteks.size());

}

/** Menciptakan suatu graf untuk verteks-verteks integer 0, 1, 2 dan list tepi */

protected AbstractGraph(List<Edge> tepi, int jumlahVerteks) {

verteks = new ArrayList<V>(); // Menciptakan verteks

for (int i = 0; i < jumlahVerteks; i++) {

verteks.add((V)(new Integer(i))); // verteks adalah {0, 1, ...}

}

createAdjacencyLists(tepi, jumlahVerteks);

}

/** Menciptakan suatu graf dari verteks-verteks integer 0, 1, dan array tepi */

protected AbstractGraph(int[][] tepi, int jumlahVerteks) {

verteks = new ArrayList<V>(); // Menciptakan verteks

for (int i = 0; i < jumlahVerteks; i++) {

verteks.add((V)(new Integer(i))); // verteks adalah {0, 1, ...}

}

createAdjacencyLists(tepi, jumlahVerteks);

}

/** Menciptakan list kebertetanggaan untuk setiap verteks */

private void createAdjacencyLists(

int[][] tepi, int jumlahVerteks) {

// Menciptakan suatu list berantai

tetangga = new ArrayList<List<Integer>>();

for (int i = 0; i < jumlahVerteks; i++) {

tetangga.add(new ArrayList<Integer>());

}

for (int i = 0; i < tepi.length; i++) {

int u = tepi[i][0];

int v = tepi[i][1];

tetangga.get(u).add(v);

}

/** Menciptakan list kebertetanggaaan untuk setiap verteks */

private void createAdjacencyLists(

List<Edge> tepi, int jumlahVerteks) {

// Menciptakan suatu list berantai

tetangga = new ArrayList<List<Integer>>();

for (int i = 0; i < jumlahVerteks; i++) {

tetangga.add(new ArrayList<Integer>());

}

for (Edge tepi1: tepi) {

tetangga.get(tepi1.u).add(tepi1.v);

}

/** Mengembalikan jumlah verteks di dalam graf */

public int getSize() {

return verteks.size();

}

/** Mengembalikan verteeks-verteks di dalam graf */

public List<V> getVertices() {

return verteks;

}

/** Mengembalikan objek untuk verteks tertentu */

public V getVertex(int indeks) {

return verteks.get(indeks);

}

/** Mengembalikan indeks untuk objek verteks tertentu */

public int getIndex(V v) {

return verteks.indexOf(v);

}

/** Mengembalikan tetangga-tetangga verteks dengan indeks tertentu */

public List<Integer> getNeighbors(int indeks) {

return tetangga.get(indeks);

}

/** Mengembalikan derajat untuk verteks tertentu */

public int getDegree(int v) {

return tetangga.get(v).size();

}

/** Mengembalikan matriks kebertetanggaan */

public int[][] getAdjacencyMatrix() {

int[][] matriksKebertetanggaan = new int[getSize()][getSize()];

for (int i = 0; i < tetangga.size(); i++) {

for (int j = 0; j < tetangga.get(i).size(); j++) {

int v = tetangga.get(i).get(j);

matriksKebertetanggaan[i][v] = 1;

}

return matriksKebertetanggaan;

}

/** Menampilkan matriks kebertetanggaan */

public void printAdjacencyMatrix() {

int[][] matriksKebertetanggaan = getAdjacencyMatrix();

for (int i = 0; i < matriksKebertetanggaan.length; i++) {

for (int j = 0; j < matriksKebertetanggaan[0].length; j++) {

System.out.print(matriksKebertetanggaan[i][j] + " ");

}

System.out.println();

}

/** Menampilkan semua tepi */

public void printEdges() {

for (int u = 0; u < tetangga.size(); u++) {

System.out.print("Verteks " + u + ": ");

for (int j = 0; j < tetangga.get(u).size(); j++) {

System.out.print("(" + u + ", " +

tetangga.get(u).get(j) + ") ");

}

System.out.println();

}

/** Edge sebagai kelas inner di dalam kelas AbstractGraph */

public static class Edge {

public int u; // Verteks awal dari tepi

public int v; // Verteks akhir dari tepi

/** Menciptakan suatu tepi untuk (u, v) */

public Edge(int u, int v) {

this.u = u;

this.v = v;

}

/** Mendapatkan suatu pohon DFS mulai dari vertkes v */

/** Akan didiskusikan pada bagian 12.6 */

public Tree dfs(int v) {

List<Integer> urutanPencarian = new ArrayList<Integer>();

int[] orangtua = new int[verteks.size()];

for (int i = 0; i < orangtua.length; i++)

orangtua[i] = -1; // Menginisialisasi orangtua[i] dengan -1

// Menandai verteks yang dikunjungi

boolean[] isVisited = new boolean[verteks.size()];

// Mencari secara rekursif

dfs(v, orangtua, urutanPencarian, isVisited);

// Menghasilkan suatu pohon pencarian

return new Tree(v, orangtua, urutanPencarian);

}

/** Metode rekursif untuk pencarian DFS */

private void dfs(int v, int[] orangtua, List<Integer> urutanPencarian,

boolean[] isVisited) {

// Menyimpan verteks yang dikunjungi

urutanPencarian.add(v);

isVisited[v] = true; // Verteks v dikunjungi

for (int i : tetangga.get(v)) {

if (!isVisited[i]) {

orangtua[i] = v; // Orangtua dari verteks i adalah v

dfs(i, orangtua, urutanPencarian, isVisited); // Pencarian rekursif

}

/** Memulai pencarian bfs dari verteks v */

/** Akan didiskusikan dalam bagian 12.7 */

public Tree bfs(int v) {

List<Integer> urutanPencarian = new ArrayList<Integer>();

int[] orangtua = new int[verteks.size()];

for (int i = 0; i < orangtua.length; i++)

orangtua[i] = -1; // Menginisialisasi orangtua[i] dengan -1

java.util.LinkedList<Integer> antrian =

new java.util.LinkedList<Integer>(); // list digunakan sebagai suatu antrian

boolean[] isVisited = new boolean[verteks.size()];

antrian.offer(v); // Membuat v sebagai antrian

isVisited[v] = true; // Menandainya karena dikunjungi

while (!antrian.isEmpty()) {

int u = antrian.poll(); // Membongkar antrian ke u

urutanPencarian.add(u); // Mencari u

for (int w : tetangga.get(u)) {

if (!isVisited[w]) {

antrian.offer(w); // // Membuat w sebagai antrian

orangtua[w] = u; // Orangtua dari w adalah u

isVisited[w] = true; // Menandainya karena dikunjungi

}

return new Tree(v, orangtua, urutanPencarian);

}

/** Tree sebagai kelas inner di dalam kelas AbstractGraph */

/** Akan didiskusikan pada bagian 12.5 */

public class Tree {

private int akar; // Akar pohon

private int[] orangtua; // Menyimpan orangtua untuk setiap verteks

private List<Integer> urutanPencarian; // Menyimpan urutan pencarian

/** Menciptakan suatu pohon dengan akar, orangtua, dan urutanPencarian */

public Tree(int akar, int[] orangtua, List<Integer> urutanPencarian) {

this.akar = akar;

this.orangtua = orangtua;

this.urutanPencarian = urutanPencarian;

}

/** Menciptakan suatu pohon dengan akar dan orangtua

* tanpa urutan yang ditentukan */

public Tree(int akar, int[] orangtua) {

this.akar = akar;

this.orangtua = orangtua;

}

/** Mengembalikan akar dari pohon */

public int getRoot() {

return akar;

}

/** Memuat orangtua dari verteks v */

public int getParent(int v) {

return orangtua[v];

}

/** Mengembalikan suatu array yang memuat urutan pencarian */

public List<Integer> getSearchOrders() {

return urutanPencarian;

}

/** Mengembalikan jumlah verteks yang ditemukan */

public int getNumberOfVerticesFound() {

return urutanPencarian.size();

}

/** Mengembalikan jalur verteks dari suatu indeks verteks ke akar */

public List<V> getPath(int indeks) {

ArrayList<V> jalur = new ArrayList<V>();

do {

jalur.add(verteks.get(indeks));

indeks = orangtua[indeks];

}

while (indeks != -1);

return jalur;

}

/** Menampilkan suatu jalur dari akar ke verteks v */

public void printPath(int indeks) {

List<V> jalur = getPath(indeks);

System.out.print("Suatu jalur dari " + verteks.get(akar) + " ke " +

verteks.get(indeks) + ": ");

for (int i = jalur.size() - 1; i >= 0; i--)

System.out.print(jalur.get(i) + " ");

}

/** Menampilkan keseluruhan pohon */

public void printTree() {

System.out.println("Akar adalah: " + verteks.get(akar));

System.out.print("Tepi-tepi: ");

for (int i = 0; i < orangtua.length; i++) {

if (orangtua[i] != -1) {

// Menampilkan suatu tepi

System.out.print("(" + verteks.get(orangtua[i]) + ", " +

verteks.get(i) + ") ");

}

System.out.println();

}

Kode12.4 UnweightedGraph.java

import java.util.*;

public class UnweightedGraph<V> extends AbstractGraph<V> {

/** Menciptakan suatu graf dari tepi dan verteks yang disimpan di dalam array */

public UnweightedGraph(int[][] tepi, V[] verteks) {

super(tepi, verteks);

}

/** Menciptakan suatu graf dari tepi dan verteks yang disimpan di dalam list */

public UnweightedGraph(List<Edge> tepi, List<V> verteks) {

super(tepi, verteks);

}

/** Menciptakan suatu graf untuk verteks integer 0, 1, 2 dan tepi list */

public UnweightedGraph(List<Edge> tepi, int jumlahVerteks) {

super(tepi, jumlahVerteks);

}

/** Menciptakan suatu graf untuk verteks integer 0, 1, 2 dan tepi array */

public UnweightedGraph(int[][] tepi, int jumlahVerteks) {

super(tepi, jumlahVerteks);

}

Kode di dalam antarmuka Graph di dalam kode12.2 dan kelas UnweightedGraph cukup sederhana. Berikut adalah sedikit penjelasan tentang kode di dalam kelas AbstractGraph pada kode12.3.

Kelas AbstractGraph mendefinisikan bidang data verteks (baris 4) untuk menyimpan verteks dan tetangga (baris 5) untuk menyimpan tepi di dalam list kebertetanggaan. tetangga.get(i) menyimpan semua verteks yang bertetangga dengan verteks i. Empat konstruktor teroverload didefinisikan pada baris 8-38 untuk menciptakan graf dari array atau list tepi dan verteks. Metode createAdjacencyLists(int[][] tepi,int jumlahVerteks) menciptakan list kebertetanggaan dari tepi-tepi di dalam array (baris 41-54). Metode createAdjacencyLists(List<Edge> tepi,int jumlahVerteks) menciptakan list kebertetanggaan dari tepi-tepi di dalam list (baris 57-68).

Metode getAdjacencyMatrix() (baris 101-112) mengembalikan suatu array dua dimensi untuk merepresentasikan matris kebertetanggaan dari tepi. Metode printAdjacencyMatrix() (115-124) menampilkan matriks kebertetanggaan. Metode printEdges() (baris 127-136) menampilkan semua verteks dan tepi yang bertetangga dengan setiap verteks.

Kode pada baris 150-288 memberikan metode-metode untuk menemukan suatu pohon pencarian depth-first dan suatu pohon pencarian breadth-first, yang akan didiskusikan pada bagian 12.7 dan 12.8.

12.5 Visualisasi Graf

Bagian terdahulu mengenalkan bagaimana untuk memodelkan suatu graf menggunakan antarmuka Graph, kelas AbstractGraph, dan kelas UnweightedGraph. Bagian ini akan mengenalkan bagaimana menampilkan graf secara visual. Untuk menampilkan suatu graf, Anda perlu mengetahui lokasi dimana setiap verteks ditampilkan dan nama setiap verteks. Untuk memastikan graf dapat ditampilkan, suatu antarmuka yang dinamai Displayable didefinisikan pada kode12.5.

Kode12.5 Displayable.java

public interface Displayable {

public int getX(); // Mendapatkan koordinat-x dari verteks

public int getY(); // Mendapatkan koordinat-y dari verteks

public String getName(); // Mendapatkan nama tertampil dari verteks

}

Suatu graf dengan verteks Displayable sekarang dapat ditampilkan pada suatu panel yang dinamai GraphView seperti ditunjukkan pada kode12.6.

Kode12.6 GraphView.java

public class GraphView extends javax.swing.JPanel {

private Graph<? extends Displayable> graf;

public GraphView(Graph<? extends Displayable> graf) {

this.graf = graf;

}

protected void paintComponent(java.awt.Graphics g) {

super.paintComponent(g);

// Menggambar verteks

java.util.List<? extends Displayable> verteks

= graf.getVertices();

for (int i = 0; i < graf.getSize(); i++) {

int x = verteks.get(i).getX();

int y = verteks.get(i).getY();

String nama = verteks.get(i).getName();

g.fillOval(x - 8, y - 8, 16, 16); // Menampilkan suatu verteks

g.drawString(nama, x - 12, y - 12); // Menampilkan nama

}

// Menggambar tepi untuk sepasang verteks

for (int i = 0; i < graf.getSize(); i++) {

java.util.List<Integer> tetangga = graf.getNeighbors(i);

for (int j = 0; j < tetangga.size(); j++) {

int v = tetangga.get(j);

int x1 = graf.getVertex(i).getX();

int y1 = graf.getVertex(i).getY();

int x2 = graf.getVertex(v).getX();

int y2 = graf.getVertex(v).getY();

g.drawLine(x1, y1, x2, y2); // Menggambar tepi untuk (i, v)

}

Untuk menggambarkan graf pada suatu panel, suatu instans GraphView diciptakan melalui pelewatan graf sebagai suatu argumen di dalam konstruktor (baris 4). Kelas untuk verteks pada graf harus mengimplementasikan antarmuka Displayable agar bisa menampilkan vertes (baris 12-21). Untuk setiap verteks indeks i, pemanggilan graf.getNeighbors(i) akan mengembalikan list kebertetanggaan (baris 25). Dari list ini, Anda bisa menemukan semua verteks yang bertetangga dengan i dan menggambar suatu garis untuk menghubungkan i dengan verteks tetangganya (baris 27-33).

Kode12.7 menyajikan suatu contoh dalam menampilkan graf pada Gambar 12.1.

Kode12.7 TampilGraf.java

import javax.swing.*;

public class TampilGraf extends JApplet {

private Kota[] verteks = {new Kota("Balige", 75, 50),

new Kota("Parapat", 50, 210),

new Kota("Raya", 75, 275), new Kota("Siantar", 275, 175),

new Kota("Perdagangan", 400, 245),

new Kota("Tebing", 450, 100), new Kota("Binjai", 700, 80),

new Kota("Medan", 675, 120), new Kota("Asahan", 575, 295),

new Kota("Kisaran", 600, 400), new Kota("Sipirok", 408, 325),

new Kota("Tanjung", 450, 360) };

// Array tepi untuk graf pada Gambar 12.1

private int[][] tepi = {

{0, 1}, {0, 3}, {0, 4},

{1, 0}, {1, 2}, {1, 4},

{2, 1}, {2, 4}, {2, 5}, {2, 6},

{3, 0}, {3, 4}, {3, 5}, {3, 8}, {3, 9},

{4, 0}, {4, 1}, {4, 2}, {4, 3}, {4, 5},

{5, 2}, {5, 3}, {5, 4}, {5, 6}, {5, 9}, {5, 10},

{6, 2}, {6, 5}, {6, 7}, {6, 10},

{7, 6}, {7, 10}, {7, 11},

{8, 3}, {8, 9},

{9, 3}, {9, 5}, {9, 8}, {9, 10},

{10, 5}, {10, 6}, {10, 7}, {10, 9}, {10, 11},

{11, 7}, {11, 10}

};

private Graph<Kota> graf

= new UnweightedGraph<Kota>(tepi, verteks);

public TampilGraf() {

add(new GraphView(graf));

}

static class Kota implements Displayable {

private int x, y;

private String nama;

Kota(String nama, int x, int y) {

this.nama = nama;

this.x = x;

this.y = y;

}

public int getX() {

return x;

}

public int getY() {

return y;

}

public String getName() {

return nama;

}

12.6 Penjelajahan Graf

Penjelajahan graf merupakan proses pengunjungan setiap verteks masing-masing hanya sekali di dalam graf. Ada dua cara populer untuk menjelajah suatu graf: penjelajahan depth-first (atau DFS, depth-first search) dan penjelajahan breadth-first (atau DFS, breadth -first search). Kedua penjelajahan akan menghasilkan pohon spanning, yang dapat dimodelkan menggunakan suatu kelas, seperti yang ditampilkan pada Gambar 12.8. Perhatikan bahwa Tree merupakan kelas inner yang didefinisikan di dalam kelas AbstractGraph. AbstractGraph<V>.Tree berbeda dari antarmuka Tree yang telah didefinisikan pada bagian 11.2.5. AbstractGraph.Tree merupakan suatu kelas khusus yang didesain untuk menjelaskan relasi orangtua-anak dari simpul, sedangkan antarmuka Tree didesain untuk mendefinisikan beberapa operasi umum seperti pencarian, penyisipan, penghapusan di dalam suatu pohon. Karena tidak ada kebutuhan untuk melakukan operasi-operasi tersebut di dalam pohon spanning, maka AbstractGraph<V>.Tree tidak didefinisikan sebagai subtipe dari Tree.

Kelas Tree didefinisikan sebagai kelas inner di dalam kelas AbstractGraph dalam baris 214-288 pada kode12.3.

Kelas Tree mempunyai dua konstruktor. Konstruktor pertama menciptakan suatu pohon dengan urutan pencarian dan konstruktor kedua menciptakan suatu pohon tanpa urutan pencarian.

Gambar 12.8 Kelas Tree menjelaskan simpul dengan relasi orangtua-anak

Kelas Tree mendefinisikan tujuh metode. Metode getRoot() mengembalikan akar pohon. Anda bisa mendapatkan urutan verteks yang dicari dengan memanggil metode getSearchOrders(). Anda dapat memanggil metode getParent(v) untuk menemukan orangtua dari verteks v di dalam pencarian. Pemanggilan metode getNumberVerticesFound() mengembalikan jumlah verteks yang ditemukan. Pemanggilan metode getPath(index) mengembalikan suatu list verteks dari indeks verteks tertentu ke akar. Pemanggilan metode printPath(v) menampilkan jalur dari akar ke verteks v. Anda dapat menampilkan semua tepi di dalam pohon menggunakan metode printTree().

12.7 DFS (Depth-First Search)

DFS atas suatu graf sama seperti penjelajahan depth-first yang telah dijelaskan pada bagian 11.2.4, “Penjelajahan Pohon”. Dalam kasus suatu pohon, pencarian dimulai dari akar. Dalam suatu graf, pencarian bisa dimulai dari sembarang verteks.

DFS atas suatu pohon pertama-tama menghampiri akar, kemudian secara rekursif mengunjungi sub-subpohon dari akar tersebut. Dengan logika yang sama, DFS atau suatu graf, pertama-tama mengunjungi suatu verteks, kemudian mengunjungi semua verteks yang bertetangga dengan verteks itu. Perbedaannya adalah bahwa graf mempunyai siklus, yang bisa mengarah pada siklus tak-berakhir. Untuk mengatasi masalah ini, Anda perlu menjejak verteks-verteks yang telah dikunjungi.

Pencarian ini dikatakan depth-first, karena algoritma ini mencari sedalam mungkin yang bisa dilakukan. Pencarian dimulai dari verteks v. Setelah mengunjungi v, maka dilakukan kunjungan terhadap tetangga dari verteks v yang belum pernah dikunjungi sebelumnya. Jika verteks v tidak memiliki tetangga yang belum pernah dikunjungi sebelumnya, maka kembali ke verteks sebelum mengunjungi verteks v.

12.7.1 Algoritma DFS

Algoritma DFS dideskripsikan pada kode12.8 sebagai berikut:

Kode12.8 Algoritma DFS

1 dfs(verteks v) {

2 kunjungi v;

3 for setiap tetangga w dari v

4 if (w belum pernah dikunjungi) {

5 dfs(w);

6 }

7 }

Anda bisa menggunakan suatu array yang dinamai isVisited untuk menandai apakah suatu verteks telah dikunjungi sebelumnya atau tidak. Awalnya, isVisited[i] bernilai false untuk setiap verteks i. Begitu suatu verteks v dikunjungi, isVisited[v] ditetapkan bernilai true.

Perhatikan graf pada Gambar 12.9a. Dimisalkan bahwa Anda memulai DFS dari verteks 0. Setelah verteks 0 dikunjungi, kemudian salah satu dari tetangganya dikunjungi, katakanlah verteks 1. Sekarang verteks 1 telah dikunjungi, seperti tertampil pada Gambar 12.9b. Verteks 1 memiliki tiga tetangga: verteks 0, 2, dan verteks 4. Karena verteks 0 telah dikunjungi sebelumnya, maka Anda akan mengunjungi salah satu dari verteks 2 atau verteks 4. Sekarang anggap saja verteks 2 yang dikunjungi. Sekarang verteks 2 telah dikunjungi, seperti tertampil pada Gambar 12.9c. Verteks 2 memiliki tiga tetangga: verteks 0, 1, dan verteks 3. Karena verteks 0 dan verteks 1 telah dikunjungi sebelumnya, maka verteks 3 yang dikunjungi. Sekarang verteks 3 telah dikunjungi, seperti ditunjukkan pada Gambar 12.9d. Pada titik ini, verteks-verteks dikunjungi dengan urutan seperti ini:

0, 1, 2, 3

Karena semua tetangga dari verteks 3 telah pernah dikunjungi, maka kembali ke verteks 2. Karena semua tetangga verteks 2 sudah pernah dikunjungi, maka kembali ke verteks 4, seperti ditunjukkan pada Gambar 12.9e. Karena semua tetangga dari verteks 4 telah pernah dikunjungi, maka kembali ke verteks 1. Karena semua tetangga dari verteks 1 telah pernah dikunjungi, maka kembali ke verteks 0. Karena semua tetangga dari verteks 0 telah pernah dikunjungi, maka pencarian berhenti.

Gambar 12.9 DFS mengunjungi suatu simpul dan para tetangganya secara rekursif

12.7.2 Implementasi DFS

Metode dfs(int v) diimplementasikan dalam baris 152-181 pada kode12.3. Metode ini mengembalikan suatu instans dari kelas Tree dengan verteks v sebagai akar. Metode ini menyimpan verteks-verteks yang dicari di dalam suatu list urutanPencarian (baris 153), orangtua dari tiap verteks di dalam array orangtua (baris 154), dan menggunakan array isVisited untuk mengindikasikan apakah suatu verteks sudah pernah dikunjungi atau belum (baris 159). Metode ini juga memanggil suatu metode helper dfs(v, orangtua, urutanPencarian, isVisited) untuk melakukan suatu pencarian depth-first (baris 162).

Di dalam metode helper rekursif, pencarian dimulai dari verteks v. v ditambahkan pada urutanPencarian (baris 172) dan ditandai bahwa telah dikunjungi (baris 173). Untuk setiap tetangga yang belum pernah dikunjungi dari v, metode secara rekursif dipanggil untuk melakukan pencarian DFS. Ketika suatu verteks i dikunjungi, orangtua dari verteks i disimpan di dalam array orangtua[i] (baris 177).

Kode12.9 menyajikan suatu program uji yang menampilkan suatu DFS untuk graf pada Gambar 12.1 dimulai dari Tebing. Ilustrasi grafikal atas DFS dimulai dari Tebing ditampilkan pada Gambar 12.10.

Kode12.9 UjiDFS.java

public class UjiDFS {

public static void main(String[] args) {

String[] verteks = {"Balige", "Parapat", "Raya", "Tebing", "Siantar",

"Perdagangan", "Sipirok", "Tanjung", "Binjai", "Medan", "Asahan",

"Kisaran"};

int[][] tepi = {

{0, 1}, {0, 3}, {0, 4},

{1, 0}, {1, 2}, {1, 4},

{2, 1}, {2, 4}, {2, 5}, {2, 6},

{3, 0}, {3, 4}, {3, 5}, {3, 8}, {3, 9},

{4, 0}, {4, 1}, {4, 2}, {4, 3}, {4, 5},

{5, 2}, {5, 3}, {5, 4}, {5, 6}, {5, 9}, {5, 10},

{6, 2}, {6, 5}, {6, 7}, {6, 10},

{7, 6}, {7, 10}, {7, 11},

{8, 3}, {8, 9},

{9, 3}, {9, 5}, {9, 8}, {9, 10},

{10, 5}, {10, 6}, {10, 7}, {10, 9}, {10, 11},

{11, 7}, {11, 10}

};

Graph<String> graf =

new UnweightedGraph<String>(tepi, verteks);

AbstractGraph<String>.Tree dfs = graf.dfs(3); // 3 adalah Tebing

java.util.List<Integer> urutanPencarian = dfs.getSearchOrders();

System.out.println(dfs.getNumberOfVerticesFound() +

" verteks dicari di dalam DFS dengan urutan:");

for (int i = 0; i < urutanPencarian.size(); i++)

System.out.print(graf.getVertex(urutanPencarian.get(i)) + " ");

System.out.println();

for (int i = 0; i < urutanPencarian.size(); i++)

if (dfs.getParent(i) != -1)

System.out.println("orangtua dari " + graf.getVertex(i) +

" adalah " + graf.getVertex(dfs.getParent(i)));

}

Keluaran

12 verteks dicari di dalam DFS dengan urutan:

Tebing Balige Parapat Raya Siantar Perdagangan Sipirok Tanjung Asahan Medan Binjai Kisaran

orangtua dari Balige adalah Tebing

orangtua dari Parapat adalah Balige

orangtua dari Raya adalah Parapat

orangtua dari Siantar adalah Raya

orangtua dari Perdagangan adalah Siantar

orangtua dari Sipirok adalah Perdagangan

orangtua dari Tanjung adalah Sipirok

orangtua dari Binjai adalah Medan

orangtua dari Medan adalah Asahan

orangtua dari Asahan adalah Tanjung

orangtua dari Kisaran adalah Asahan

Gambar 12.10 DFS mencari mulai dari Tebing

12.8 BFS (Breadth-First Search)

Penjelajahan breadth-first atas suatu graf sama dengan penjelajahan breadth-first atas suatu pohon yang telah didiskusikan pada bagian 11.2.4. Pada kasus penjelajahan breadth-first atas suatu pohon, simpul-simpul dikunjungi level demi level. Pertama-tama akar dikunjungi, selanjutnya semua anak dari akar tersebut dikunjungi, kemudian cucu dari akar dikunjungi, dan seterusnya. Dengan cara yang sama, penjelajahan breadth-first atas suatu graf pertama-tama mengunjungi suatu verteks, dan kemudian semua verteks tetangganya, dan kemudian semua verteks tetangga dari verteks-verteks tersebut, dan seterusnya. Untuk memastikan bahwa setiap verteks hanya dikunjungi sekali saja, verteks yang telah atau pernah dikunjungi akan dilompati.

12.8.1 Algoritma BFS (Breadth-First Search)

Algoritma pencarian BFS dimulai dari verteks v di dalam suatu graf dapat dijelaskan pada kode12.10.

Kode12.8 Algoritma DFS

1 bfs(verteks v) {

2 menciptakan suatu antrian kosong untuk menyimpan verteks-verteks yang akan dikunjungi;

3 menambah v ke dalam antrian;

4 tandai v karena sudah dikunjungi;

6 while antrian tidak kosong {

7 Ambil suatu vertex, katakanla u, dari antrian

8 menambah u ke dalam suatu list yang memuat verteks-verteks yang sudah dijelajah;

9 for setiap tetangga w dari verteks u

10 if w belum dikunjungi {

11 menambah w ke dalam antrian;

12 tandai w karena sudah dikunjungi;

13 }

14 }

15 }

Perhatikan graf pada Gambar 12.11a. Dimisalkan bahwa Anda memulai pencarian breadth-first dai verteks 0. Pertama-tama mengunjungi verteks 0, kemudian mengunjungi semua tetangganya yaitu verteks 1, 2, dan 3, seperti tertampil pada Gambar 12.11b. Verteks 1 memiliki tiga tetangga, yaitu verteks 0, 2, dan 4. Karena verteks 0 dan 2 sudah pernah dikunjungi, maka hanya verteks 4 yang akan dikunjungi, seperti ditunjukkan pada Gambar 12.11c. Verteks 2 memiliki tiga tetangga, yaitu verteks 0, 1, dan 3, yang ketiganya sudah pernah dikunjungi. Verteks 3 memiliki tiga tetangga, yaitu verteks 0, 2, dan 4, dimana ketiganya sudah pernah dikunjungi. Verteks 4 mempunyai dua tetangga, yaitu verteks 1 dan 3, dimana keduanya sudah pernah dikunjungi. Jadi, pencarian berhenti.

Gambar 12.11 Pencarian breadth-first mengunjungi suatu simpul, kemudian mengunjungi semua tetangga dari simpul tersebut, kemudian mengunjungi semua tetangga dari tetangga simpul tersebut, dan seterusnya

12.8.2 Implementasi BFS (Breadth-First Search)

Metode bfs(int v) didefinisikan di dalam antarmuka Graph dan diimplementasikan di dalam kelas AbstractGraph (baris 185-210). Metode ini mengembalikan suatu instans dari kelas Tree dengan verteks v sebagai akar. Metode menyimpan semua verteks yang dicari di dalam suatu list urutanPencarian (baris 186), orangtua dari setiap verteks di dalam suatu array orangtua (baris 187), menggunakan suatu list berantai untuk antrian (baris 191-192), dan menggunakan array isVisited untuk mengindikasikan apakah suatu verteks sudah dikunjungi atau belum (baris 193). Pencarian dimulai dari verteks v. v ditambahkan ke dalam antrian pada baris 194 dan ditandai bahwa telah dikunjungi pada baris 195. Metode selanjutnya memeriksa setiap verteks u di dalam antrian (baris 198) dan menambahkannya ke dalam array urutanPencarian (baris 199). Metode ini menambahkan setiap verteks tetangga yang belum pernah dikunjungi (semua verteks w yang merupakan tetangga dari verteks u) ke dalam antrian (baris 202), menetapkan orangtuanya menjadi u (baris 203), dan menandai bahwa telah dikunjungi (baris 204).

Baris 12.11 menyajikan suatu program uji yang menampilkan suatu BFS untuk graf pada Gambar 12.1 dimulai dari Tebing. Ilustrasi grafikal atas BFS dimulai dari Tebing ditampilkan pada Gambar 12.12.

Kode12.11 UjiBFS.java

public class UjiBFS {

public static void main(String[] args) {

String[] verteks = {"Balige", "Parapat", "Raya", "Tebing", "Siantar",

"Perdagangan", "Sipirok", "Tanjung", "Binjai", "Medan", "Asahan",

"Kisaran"};

int[][] tepi = {

{0, 1}, {0, 3}, {0, 4},

{1, 0}, {1, 2}, {1, 4},

{2, 1}, {2, 4}, {2, 5}, {2, 6},

{3, 0}, {3, 4}, {3, 5}, {3, 8}, {3, 9},

{4, 0}, {4, 1}, {4, 2}, {4, 3}, {4, 5},

{5, 2}, {5, 3}, {5, 4}, {5, 6}, {5, 9}, {5, 10},

{6, 2}, {6, 5}, {6, 7}, {6, 10},

{7, 6}, {7, 10}, {7, 11},

{8, 3}, {8, 9},

{9, 3}, {9, 5}, {9, 8}, {9, 10},

{10, 5}, {10, 6}, {10, 7}, {10, 9}, {10, 11},

{11, 7}, {11, 10}

};

Graph<String> graf =

new UnweightedGraph<String>(tepi, verteks);

AbstractGraph<String>.Tree bfs = graf.bfs(3); // 3 adalah Tebing

java.util.List<Integer> urutanPencarian = bfs.getSearchOrders();

System.out.println(bfs.getNumberOfVerticesFound() +

" verteks-verteks dicari dalam urutan ini:");

for (int i = 0; i < urutanPencarian.size(); i++)

System.out.println(graf.getVertex(urutanPencarian.get(i)));

for (int i = 0; i < urutanPencarian.size(); i++)

if (bfs.getParent(i) != -1)

System.out.println("orangtua dari " + graf.getVertex(i) +

" adalah " + graf.getVertex(bfs.getParent(i)));

}

Keluaran

12 verteks-verteks dicari dalam urutan ini:

Tebing

Balige

Siantar

Perdagangan

Binjai

Medan

Parapat

Raya

Sipirok

Asahan

Tanjung

Kisaran

orangtua dari Balige adalah Tebing

orangtua dari Parapat adalah Balige

orangtua dari Raya adalah Siantar

orangtua dari Siantar adalah Tebing

orangtua dari Perdagangan adalah Tebing

orangtua dari Sipirok adalah Perdagangan

orangtua dari Tanjung adalah Sipirok

orangtua dari Binjai adalah Tebing

orangtua dari Medan adalah Tebing

orangtua dari Asahan adalah Perdagangan

orangtua dari Kisaran adalah Asahan

Gambar 12.12 Pencarian BFS dimulai dari Tebing

2 comments:

Imam LutfiMay 3, 2019 at 10:41 AM
Contoh untuk weighted graf nya gaada ya pak?
ReplyDelete
Replies
Bimbingan Belajar MIPATIKA'88May 7, 2020 at 3:02 AM
saya orang Tebing Tinggi (sumut) bang....wah bagus contoh soalnya ...mantul
ReplyDelete
Replies

Add comment

Menu

Tuesday, December 20, 2016

Bab 12. Java Struktur Data dan Pemrograman GUI

2 comments: