1.
Jelaskan
pengertian dari graph!
Graph adalah
kumpulan dari simpul dan busur yang secara matematis dinyatakan sebagai :G = (V, E)
2.
Sebutkan
dan jelaskan istilah istilah pada graph!
·
Incident
·
Degree (derajat), indegree dan
outdegree
·
Indegree sebuah simpul pada graph
berarah
·
Outdegree sebuah simpul pada graph
berarah
3.
apa
yang dimaksud dengan graph berarah,tidak berarah,dan berbobot!
·
Graf
berarah adalah graf yang setiap sisinya diberikan orientasi arah disebut
sebagai graf berarah.
·
Graf tidak berarah yaitu graf yang setiap sisinya tidak
mempunyai arah anak panah tetapi memiliki bobot pada setiap sisinya.
·
graf
berbobot merupakan suatu graf tanpa busur parallel dimana setiap busurnya
berhubungan dengan suatu bilangan riil tak negatif yang menyatakan bobot busur
(w(a)) tersebuT.
4.
buatlah
satu contoh program dari graph berarah!
/**
*
class Graph
*
@author Jim
*
@version 1.0
*/
public
class Graph
{
protected
HashMap adjacencyMap;
/**
*
insialisasi Graf, membuat adjacency map
*/
public
Graph()
{
adjacencyMap
= new HashMap()
}
/**
*
Memeriksa apakah Graf mengandung simpul
*
*@return
true – jika tidak mengandung simpul kosong.
*/
public
boolean isEmpty()
{
return
adjacencyMap.isEmpty();
}
/**
*
Mengembalikan jumlah simpul induk dalam graf
*/
public
int size()
{
return adjacencyMap.size();
}
/**
*
Mengembalikan jumlah sisi dalam graf
*/
public
int getEdgeCount()
{
int
count = 0;
for
(inti=0;i<adjacencyMap.CAPACITY;i++){
if
(adjacencyMap.keys[i] != null){
LinkedList
edges = (LinkedList)
adjacencyMap.get(adjacencyMap.keys[i]);
count
+= edges.size();
}
}
return
count;
}
/**
*
Menambahkan sebuah objek sebagai simpul
*
@param vertex – the specified object
*
@return true – jika berhasil ditambahkan
*/
public
boolean addVertex (Object vertex)
{
if
(adjacencyMap.containsKey(vertex))
return
false;
adjacencyMap.put (vertex,
new
LinkedList());
return
true;
}
/**
*
Menambahkan sisi, dan simpul jika belum ada dalam graf
*
@param v1 – simpul awal mula sisi
*
@param v2 – simpul akhir dari sisi
*
@return true – jika sisi berhasil ditambahkan ke dalam graf
*/
public
boolean addEdge (Object v1, Object v2)
{
addVertex
(v1); addVertex (v2);
LinkedList
l = (LinkedList)
adjacencyMap.get(v1);
l.add(v2);
return
true;
}
}
Untuk
memberikan gambaran singkat tentang struktur data graf ini, akan ditunjukan
bagaimana membentuk draf seperti gambar 2 dengan menggunakan fungsi dalam
struktur data graf di atas.
/*
*Contoh
implementasi ADT graf
*
new instance, bentuk objek graph1 sebagai graph
*/
Graph
graph1 = new Graph();
/*
*
gunakan fungsi addEdge untuk menambah simpul-simpul ke dalam graf sesuai
dengan hubungan ketetanggaan antar simpul
*/
graph1.addEdge(“Achorage”,”Billings”);
graph1.addEdge(“Achorage”,”Corvalis”);
graph1.addEdge(“Achorage”,”Edmonton”);
graph1.addEdge(“Billings”,”Denver”);
graph1.addEdge(“Billings”,”Edmonton”);
graph1.addEdge(“Corvalis”,”Denver”);
graph1.addEdge(“Denver”,”Edmonton”);
graph1.addEdge(“Denver”,”Flagstaff”);
graph1.addEdge(“Flagstaff”,”Denver”);
graph1.addEdge(“Flagstaff”,”Houston”);
graph1.addEdge(“Grand
Rapids”,”Houston”);
5.
buatlah
satu contoh kasus graph!
