Makalah Graph

BAB I

Pengertian Struktur Data Graph

A. Dassar Teori

Graf adalah sebuah representasi abstrak dari himpunan objek yang saling terhubung. Objek atau simpul-simpul dalam graf disebut sebagai vertex, sedangkan garis yang menghubungkan simpul-simpul yang ada di dalam graf disebut sebagai edge.

Menurut arahnya, graf dibedakan menjadi dua, yaitu directed graph dan undirected graph. Directed graph atau graf berarah adalah graf dimana semua edge yang ada di dalamnya mempunyai arah atau menunjuk kepada vertex yang lain, sedangkan undirected graph adalah graf dimana semua edge yang ada di dalamnya tidak mempunyai arah. Kedua jenis graf ini bisa muncul dalam satu graf sekaligus, yang kemudian disebut sebagai 'mixed graph'.

B.  Representasi graph

Untuk menggunakan graf ke dalam bahasa yang dimengerti oleh komputer, kita perlu mencari representasi yang paling tepat dari graf. Berikut salah satu cara untuk merepresentasikan graf di komputer:

a. Graf tidak berarah (undirected graph)

Untuk graf tidak berarah, apabila ada hubungan dari sebuah node ke node lain, maka ada hubungan juga dari node lain ke node tersebut. Misalkan terdapat edge tidak berarah dari A ke B, maka edge tersebut direpresentasikan sebagai edge berarah dari A ke B sekaligus edge berarah dari B ke A. Berikut contoh representasi hubungan antara Dahlan dan teman-temannya.

b. Graf berarah (directed graph)

Untuk graf yang berarah, representasinya tidak dibuat seperti graf yang tidak berarah. Untuk jenis yang berarah ini, edge hanya dibuat satu arah saja. Berikut contoh representasi dari jalur perjalanan dari Piyungan ke UII:

 

C.  Penggunaan Graph dalam Kehidupan Sehari-hari

Graf digunakan dalam beberapa hal, misalnya:

-        memodelkan hubungan sosial antara satu orang dengan orang yang lain. Misalkan Dahlan kenal dengan Heri, Mukhtarizal, dan Fadlon. Heri kenal dengan Fadlon dan Dahlan, tapi tidak kenal dengan Mukhtarizal.

BAB II

Contoh Struktur Data Graph

A.     Kasus 1

Dengan menggunakan Java Tree Graph Library (JTGL), buatlah program di Java untuk merepresentasikan hubungan antara Arwan dan Teman-temannya.

Jawaban Kasus 1

import graph.*;

public class HubunganSosial {

            public static void main(String[] args) {

                        Graph graf = new Graph(GraphType.UNDIRECTED_GRAPH);

                        // menambahkan vertex ke dalam graph

                        graf.addVertex(”Dahlan”);

                        graf.addVertex(”Mukhtarizal”);

                        graf.addVertex(”Heri”);

                        graf.addVertex(”Fadlon”);

                        // menambahkan edge

                        graf.addEdge(”Dahlan”,” Mukhtarizal”,1);

                        graf.addEdge(”Dahlan”,” Heri”,1);

                        graf.addEdge(”Dahlan”,” Fadlon”,1);

                        graf.addEdge(”Heri”,” Fadlon”,1);

                        // menampilkan hubungan

                  VertexIterator vi = graf.vertexIterator();

                        while (vi.hasNextVertex()) {

                                    Vertex vertex = vi.nextVertex();

                                    EdgeIterator ei = vertex.edgeIterator();

                                    while (ei.hasNextEdge()) {

                                                Edge edge = ei.nextEdge();

                                    System.out.println(vertex.info + ” kenal dengan” + ei.pointedVertex.info);

                                    }

                        }}}

B.     Kasus 2

Dengan menggunakan Java Tree Graph Library (JTGL), buatlah program Java untuk merepresentasikan jalur dari Piyungan ke UII.

Jawaban Kasus 2

import graph.*;

public class Jalur {

            public static void main(String[] arg) {

                        Graph graf = new Graph(GraphType.DIRECTED_GRAPH);

                        // menambahkan vertex

                        graf.addVertex(”Piyungan”);

                        graf.addVertex(”Berbah”);

                        graf.addVertex(”Jangkang”);

                        graf.addVertex(”Besi”);

                        graf.addVertex(”UII”);

                        // menambahkan edge

                        graf.addEdge(”Piyungan”,”Berbah”,4);

                        graf.addEdge(”Berbah”,”Jangkang”,8);

                        graf.addEdge(”Jangkang”,”Besi”,7);

                        graf.addEdge(”Besi”,”UII”,3);

// menampilkan jalurnya

                        VertexIterator vi = graf.vertexIterator();

                        while (vi.hasNextVertex()) {

                                    Vertex vertex = vi.nextVertex();

                                    EdgeIterator ei = vertex.edgeIterator();

                                    while (ei.hasNextEdge()) {

                                                Edge edge = ei.nextEdge();

                                                System.out.println(”Dari ” + vertex.info + ” ke ” + edge.pointedVertex.info + ” dengan jarak: ” + edge.getWeight());

                                    }

                        }}}

BAB III

KESIMPULAN

Struktur data Graph merupakan salah satu bahan dasar pembuatan program. Pemakaian struktur data yang tepat di dalam proses pemrograman, akan menghasilkan algoritma yang jelas dan tepat sehingga menjadikan program secara keseluruhan lebih sederhana. Array merupakan bagian dari struktur data yaitu termasuk kedalam struktur data sederhana yang dapat di definisikan sebagai pemesanan alokasi memory sementara pada komputer. Apabila kita membuat program dengan data yang sudah kita ketahui batasnyamaka kita menggunakan Array (type data statis), namun apabila datanya belum kita ketahui batasnya maka gunakan pointer (type data dinamis).