Home » » Makalah Graph

Makalah Graph

Written By Olan on Sunday, 29 December 2013 | 05:36

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).





Share this article :

0 komentar:

Post a Comment

 

Copyright © 2014. Olan Arsyad