Graf (Graph) dan Pohon (Tree) pada C++
Graf adalah kumpulan noktah (simpul) di dalam bidang dua dimensi
yang dihubungkan dengan sekumpulan garis (sisi). Graph dapat digunakan untuk merepresentasikan objek-objek diskrit
dan hubungan antara objek-objek tersebut. Representasi visual dari graph adalah dengan menyatakan objek
sebagai noktah, bulatan atau titik (Vertex),
sedangkan hubungan antara objek dinyatakan dengan garis (Edge).
G = (V, E)
Dimana :
G = Graph
V = Simpul
atau Vertex, atau Node, atau Titik
E = Busur
atau Edge, atau arc
Graf merupakan suatu cabang ilmu yang memiliki banyak terapan.
Banyak sekali struktur yang bisa direpresentasikan dengan graf, dan banyak
masalah yang bisa diselesaikan dengan bantuan graf. Seringkali graf digunakan
untuk merepresentasikan suaru jaringan. Misalkan jaringan jalan raya dimodelkan
graf dengan kota sebagai simpul (vertex/node)
dan jalan yang menghubungkan setiap kotanya sebagai sisi (edge) yang bobotnya (weight)
adalah panjang dari jalan tersebut.
Ada beberapa cara untuk menyimpan graph di dalam sitem komputer. Struktur data bergantung pada
struktur graph dan algoritma yang
digunakan untuk memanipulasi graph.
Secara teori salah satu dari keduanya dapat dibedakan antara struktur list dan matriks, tetapi dalam
penggunaannya struktur terbaik yang sering digunakan adalah kombinasi keduanya.
a.
Graph tak berarah
(undirected graph atau non-directed graph) :
-
Urutan simpul
dalam sebuah busur tidak dipentingkan. Misal busur e1 dapat disebut busur AB
atau BA
b.
Graph berarah (directed graph) :
-
Urutan simpul
mempunyai arti. Misal busur AB adalah e1 sedangkan busur BA adalah e8.
c.
Graph Berbobot (Weighted Graph)
-
Jika setiap
busur mempunyai nilai yang menyatakan hubungan antara 2 buah simpul, maka busur
tersebut dinyatakan memiliki bobot.
-
Bobot sebuah
busur dapat menyatakan panjang sebuah jalan dari 2 buah titik, jumlah rata-rata
kendaraan perhari yang melalui sebuah jalan, dll.
2). Istilah – Istilah Dalam Graph
Terdapat
istilah – istilah yang berkaitan dengan graph, yaitu :
a.
Vertex
Vertex adalah
himpunan node/titik pada sebuah graph.
b.
Edge
Edge adalah garis
yang menghubungkan tiap node/vertex.
c.
Adjacent
Adjacent adalah dua
buah titik dikatakan berdekatan juka dua buah titik tersebut terhubung dengan
sebuah sisi.
d.
Weight
Sebuah
graph dikatakan berbobot apabila
terdapat sebuah fungsi bobot bernilai real pada himpunan Edge.
e.
Path
Path adalah walk dengan setiap vertex berbeda. Walk
didefinisikan sebagai ururtan vertex
dan edge. Diawali dengan origin vertex dan diakhiri dengan terminus vertex.
f.
Cycle
Cycle adalah
siklus atau sirkuit yang berawal dan berakhir pada simpul yang sama.
Dalam pemrograman, agar data yang ada dalam graph dapat diolah, maka graph
harus dinyatakan dalam suatu struktur data yang dapat mewakili graph tersebut. Dalam hal ini graph perlu direpresentasikan kedalam
bentuk array dan dimensi yang sering
disebut matrix atau direpresentasikan
dalam bentuk linked list. Bentuk mana yang dipilih biasanya
tergantung kepada efisiensi dan kemudahan dalam membuat program. Berikut ini
beberapa bentuk representasi graph :
3.1). Representasi dalam bentuk matrix
a.
Adjacency
Matrix Graph tak berarah
Matrik
yang digambarkan pada gambar 1b merupakan representasi dalam bentuk Adjacency Matrik dari graf yang
digambarkan pada gambar 1a. Beberapa hal yang dapat dilihat atau dapat
diterangkan pada Adjacency Matrik
tersebut adalah sebagai berikut :
1.
Matrik yang
terbentuk adalah matrik bujur sangkar n x n, dimana n = jumlah simpul yang ada
dalam graf tersebut. Matrik ini menyatakan hubungan antara simpul satu dengan
simpul lainnya.
2.
Matrik yang
terbentuk adalah matrik simetris dengan sumbu simetris adalah diagonal dari
titik kiri atas ke titik kanan bawah.
3.
Data yang
tedapat baik dalam baris maupun kolom, dapat menyatakan degree sebuah simpul. Contoh : baik pada baris D maupun kolom D
jumlah angka 1 nya adalah 3 buah, dimana jumlah ini menyatakan degree simpul D.
b.
Adjacency Matrix Graf
Berarah
Matrik
yang digambarkan pada gambar 2b merupakan representasi dalam bentuk Adjacency Matrik dari graf yang
digambarkan pada gambar 2a. Beberapa hal yang dapat dilihat atau dapat
diterangkan pada Adjacency Matrik
tersebut adalah sebagai berikut :
1.
Matrik yang
terbentuk adalah matrik bujur sangkar n x n, dimana n = jumlah simpul yang ada dalam
graf tersebut. Matrik ini menyatakan hubungan antara simpul satu dengan simpul
lainnya.
2.
Matrik yang
terbentuk mungkin simetris mungkin juga tidak simetris. Menjadi Simetris bila
hubungan antara dua buah simpul (v1 dan v2) terdapat busur dari v1 ke v2 dan
juga sebaliknya.
3.
Hal pokok
yang dinyatakan oleh matrik ini adalah : busur yang ’keluar’ dari suatu simpul.
Dengan demikian, data yang terdapat dalam suatu baris, dapat menyatakan
outdegree simpul yang bersangkutan.
Contoh
: Jumlah elemen yang nilainya = 1 pada baris B ada 3 elemen,ini menyatakan
jumlah outdegree simpul B adalah 3 buah.
4.
Data yang
terdapat dalam suatu kolom, dapat menyatakan indegree simpul bersangkutan.
Contoh
: Jumlah elemen yang nilainya 1 pada kolom B ada 2 elemen, ini menyatakan indegree
simpul B adalah 2 buah.
c.
Adjacency Matrix Graph berbobot tak Berarah
Nilai
yang ada dalam tiap elemen matrik, menyatakan bobot busur yang menghubungkan
dua buah simpul yang bersangkutan. Untuk dua buah simpul yang tidak berhubungan
langsung oleh sebuah busur, maka dianggap dihubungkan oleh sebuah busur yang
nilai bobotnya tidak terhingga. Dalam pemograman, karena keperluan algoritma,
maka dari total bobot seluruh busur yang ada atau yang mungkin ada.
Contoh:
pada gambar 3a simpul A dan C tidak berhubungan langsung melalui sebuah busur,
maka untuk elemen matrik yang bersangkutan diisi dengan nilai 999 karena nilai
999 dalam kasus ini cukup mewakili nilai tidak terhingga.
3.2). Representasi dalam bentuk Linked List
a.
Adjacency List
Bila
ingin direpresentasikan dalam bentuk linked
list, dapat diilustrasikan secara sederhana seperti gamabar 4b. Dari
ilustrasi sederhana tersebut terlihat ada 5 buah simpul A,B,C,D,dan E yang
dibariskan dari atas kebawah seperti pada gambar 4a. Kemudian dari masing-masing
simpul ’keluar’ pointer kearah kanan yang menunjuk simpul-simpul lain. Salah
satu contoh, yang dapat dilihat pada gambar 4b dimana A menunjuk simpul B dan
simpul D.
Dalam
Adjacency List, kita perlu membedakan
antara simpul-vertex dan simpul-edge. Simpul-vertex untuk menyatakan simpul atau vertex, dan simpul-edge
untuk menyatakan hubungan antar simpul yang biasa disebut busur. Struktur
keduanya bisa sama, bisa juga tidak sama, tergantung kebutuhan. Untuk
memudahkan pembuatan program, struktur kedua macam simpul dibuat sama seperti
yang digambarkan pada gambar 5c. Yang membedakan antara simpul-vertex dan simpul-edge, adalah anggapan terhadap simpul tersebut. Dalam contoh ini,
terlihat struktur simpul dibuat terdiri dari 3 elemen. Satu elemen untuk INFO,
dua elemen untuk pointer. Pointer kiri (left)
dan pointer kanan (right).
Struct tipes{
Struct tipes
*Left;
int INFO;
Struct tipes
*Right;
};
Struct tipes
*First,*Pvertex,*Pedge;
|
Bila
simpul dianggap sebagai simpul-vertex,
maka :
Pointer left digunakan untuk menunjuk simpul
berikutnya dalam untaian simpul-simpul yang ada,atau diisi NULL bila sudah
tidak ada simpul yang pelu ditunjuk. Sedangkan pointer Right digunakan
untuk menunjuk simpul edge yang
pertama.
Bila
Simpul dianggap sebagai simpul-edge,
maka :
Pointer left digunakan
untuk menunjuk simpul-vertex ‘tujuan’
yang berhubungan dengan simpul-vertex
‘asal’ dan pointer right digunakan
untuk menunjuk simpul-edge berikutnya
bila masih ada, atau diisi NULL bila tak ada lagi simpul-busur yang ditunjuk.
Berikut
ini merupakan contoh program graph
#include
<stdfix.h>
#include
<stdio.h>
#include
<iostream>
#include
<stdlib.h>
using
namespace std;
int
ordo[5][5];
void
masukkan(int a, int b, int c){
for (int i = 1; i <= 4; i++){
for (int j = 1; j <= 4; j++)
if (i == a && j == b){
ordo[a][b] = ordo[i][j];
ordo[a][b] = c;
}
}
}
void
tampilkan(int a, int b, int c){
for (int i = 1; i <= 4; i++){
for (int j = 1; j <= 4; j++)
cout << ordo[i][j] << "
";
cout << endl;
}
}
void
inisialisasi(){
for (int i = 1; i <= 4; i++){
for (int j = 1; j <= 4; j++)
ordo[i][j] = 0;
}
}
void
menu(){
cout <<
"-----------------MENU-----------------\n";
cout << "1. Masukkan
Data\n";
cout << "2. Tampilkan\n";
cout << "0. Keluar\n";
cout << "Masukkan Pilihan Anda:
";
}
int
main(){
inisialisasi();
int a, b, c;
int m;
do{
system("cls");
menu();
cin >> m;
switch (m){
case 1:
cout << "\nMasukkan Koordinat x
: ";
cin >> a;
cout << "Masukkan Koordinat y :
";
cin >> b;
cout << "Masukkan Isi : ";
cin >> c;
if (a <= 4 && b <= 4){
masukkan(a, b, c);
}
else{
cout << "\nIndeks harus kurang
dari 4\n";
}break;
system("pause");
case 2:system("cls");
tampilkan(a, b, c); break;
system("pause");
}system("pause");
} while (m != 0);
}
|
Output
:
1.
Memasukkan
data untuk koordinat (1,1)
2.
Memasukkan
data untuk koordinat (2,2)
3.
Memasukkan
data untuk koordinat (3,3)
4.
Memasukkan
data untuk koordinat (4,4)
5.
Menampilkan
hasil
Tree merupakan salah satu bentuk struktur data tidak linear yang menggambarkan hubungan yang
bersifat hirarkis (hubungan one to many)
antara elemen-elemen. Tree bisa
didefinisikan sebagai kumpulan simpul/node
dengan satu elemen khusus yang disebut Root
dan node lainnya. Tree juga adalah suatu graph yang acyclic, simple, connected yang tidak mengandung loop.
Sebuah
binary search tree (bst) adalah
sebuah pohon biner yang boleh kosong, dan setiap nodenya harus memiliki identifier/value. Value pada semua node
subpohon sebelah kiiri adalah selalu lebih kecil dari value dari root,
sedangkan value subpohon di sebelah
kanan adalah sama atau lebih besar dari value
pada root, masing-masing subpohon
tersebut (kiri dan kanan) itu sendiri adalah juga binary search tree.
Struktur
data bst sangat penting dalam struktur pencarian, misalkan dalam kasus
pencarian dalam sebuah list, jika list sudah dalam keadaan terurut maka proses
pencarian akan semakin cepat, jika kita menggunakan list
contigue dan melakukan pencarian biner, akan tetapi jika kita ingin melakukan perubahan isi list (insert atau delete),
menggunakan list contigue akan sangat
lambat, karena prose insert dan delete dalam list contigue butuh memindahkan linked-list,
yang untuk operasi insert atau delete tinggal mengatur- atur pointer, akan tetapi pada n-linked list, kita tidak bisa melakukan
pointer sembarangan setiap saat,
kecuali hanya satu kali dengan kata lain hanya secara squential.
Berikut
ini merupakan istilah yang berhubungan dengan tree.
1.
Predesesor
Node yang berada
diatas node tertentu. (contoh :
B predesesor dari E dan F)
2.
Succesor
Node yang berada
dibawah node tertentu. (contoh : E dan F merupakan succesor dari B)
3.
Ancestor
Seluruh
node yang terletak sebelum node tertentu dan terletak pada jalur
yang sama. (contoh : A dan B merupakan ancestor dari F)
4.
Descendant
Seluruh
node yang terletak sesudah node tertentu dan terletak pada jalur
yang sama. (contoh : F dan B merupakan ancestor dari A)
5.
Parent
Predesesor satu level
diatas satu node. (contoh : B
merupakan parent dari F)
6.
Child
Succesor satu level dibawah satu node.
(contoh : F merupakan child dari B)
7.
Sibling
Node yang
memiliki parent yang sama dengan satu
node (contoh : E dan F adalah sibling)
8.
Subtree
Bagian
dari tree yang berupa suatu node beserta descendant-nya (contoh : Subtree
B, E, F dan Subtree D, G, H)
9.
Size
Banyaknya
node dalam suatu tree (contoh : gambar tree
diatas memiliki size = 8)
10.
Height
Banyaknya
tingkat/level dalam suatu tree (contoh : gambar tree diatas memiliki height = 3)
11.
Root (Akar)
Node khusus dalam
tree yang tidak memiliki predesesor (Contoh : A)
12.
Leaf (Daun)
Node-node dalam tree yang tidak memiliki daun (contoh : Node E,F,C,G,H)
13.
Degree
(Derajat)
Banyaknya
child yang dimiliki oleh suatu node (contoh : Node A memiliki derajat 3, node
B memiliki derajat 2)
Binary Tree merupakan salah satu bentuk struktur data tidak linear yang menggambarkan hubungan yang
bersifat hirarkis (hubungan one to many)
antara elemen-elemen. Dalam tree
terdapat jenis-jenis tree yang
memiliki sifat khusus, diantaranya adalah binary
tree.
Binary tree adalah suatu tree
dengan syarat bahwa tiap node
(simpul) hanya boleh memiliki maksimal dua subtree dan kedua subtree tersebut
harus terpisah. Tiap node dalam binary tree boleh memiliki paling banyak
dua child (anak simpul), secara
khusus anaknya dinamakan kiri dan kanan.
Binary Tree merupakan himpunan vertex-vertex yang terdiri dari 2
subtree (dengan disjoint) yaitu
subtree kiri dan subtree kanan. Setiap vertex
dalam binary tree mempunyai
derajat keluar max = 2.
Sebuah pohon biner adalah grafik asiklis yang terhubung dimana setiap tingkatan dari susut tidak lebih dari 3. Ini dapat
ditunjukkan bahwa dalam pohon biner manapun, terdapat persis dua atau lebih
simpul dengan tingkat satu daripada yang terdapat dengan tingkat tiga, tetapi
bisa terdapat angka apa saja dari simpul dengan tingkat dua. Sebuah pohon biner
berakar merupakan sebuah grafik yang mempunyai satu dari sudutnya dengan
tingkat tidak lebih dari dua sebagai akar.
Dengan akar yang dipilih, setiap sudut akan memiliki ayah
khusus, dan diatas dua anak bagaimanapun
juga, sejauh ini terdapat keterbatasan informasi untuk membedakan antara anak
kiri atau kanan. Jika kita membuang keperluan yang tak terkoneksi, membolehkan bermacam koneksi dalam komponen di grafik, kita
memanggil struktur sebuah hutan.
Sebuah jalan lain untuk mendefinisikan pohon biner melalui
definisi rekursif pada grafik langsung. Sebuah pohon biner dapat berarti :
- Sebuah sudut tunggal.
- Sebuah graf yang dibentuk
dengan mengambil dua pohon biner, menambahkan sebuah sudut, dan menambahkan
sebuah panah langsung dari sudut yang baru ke akar dai setiap pohon biner.
Pohon biner dapat dikontruksi dari bahasa pemrogaraman primitif
dalam berbagai cara. Dalam bahasa yang
menggunakan records dan referensi. Pohon biner secara khas dikontruksi dengan
mengambil sebuah struktur simpul pohon yang memuat beberapa data dan referensi
ke anak kiri dan anak kanan.
Kadang-kadang itu juga memuat sebuah referensi ke ayahnya yang
khas. Jika sebuah simpul mempunyai kurang dari dua anak, beberapa penunjuk anak
diaatur kedalam nilai nol khusus atau kesebuah simpul sentinel.
Pohon biner dapat juga disimpan sebagai struktur data implisit
dalam array, dan jika pohon tersebut merupakan sebuah pohon biner lengkap,
metode ini tidak boros tempat. Dalam penyusunan yang rapat ini, jika sebuah
simpul memiliki indeks i, anaknya dapat ditemukan pada indeks ke-2i+1 dan 2i+2,
meskipun ayahnya (jika ada) ditemukan pada indeks lantai ((i-1)/2) (asumsikan
akarnya memiliki indeks kosong). Metode ini menguntungkan dari banyak
penyimpanan yang rapat dan memiliki referensi lokal yang lebih baik,
teristimewa selama sebuah preordeer traversal.
Berikut
ini merupakan istilah – istilah yang berhubungan dengan binary tree
a.
Full Binary Tree,
semua simpul (kecuali daun) memiliki dua anak dan tiap cabang memiliki panjang
ruas yang sama.
b.
Complete Binary Tree,
Hampir sama dengan Full Binary Tree,
semua simpul (kecuali daun) memiliki dua anak tetapi memiliki panjang ruas
berbeda.
c.
Similar Binary Tree,
dua pohon yang memiliki struktur yang sama tetapi informasinya berbeda.
d.
Equivalent binary tree,
dua pohon yang memiliki struktur informasi yang sama.
e.
Kewed tree, dua pohon
yang semua simpulnya mempunyai satu anak atau turunan kecuali daun.
Kunjungan
pada binary tree terbagi menjadi tiga
bentuk binary tree, yaitu :
9.1).
Kunjungan secara preorder (Depth First
Order), mempunyai ururtan :
a.
Cetak isi
simpul yang dikunjungi (simpul akar)
b.
Kunjungi
cabang kiri
c.
Kunjungi
cabang daun
Programnya
adalah sebagai berikut :
Void
preorder (node *root)
{
If
(root != NULL)
{
Printf(“%d”,root
-/.data);
Preorder
(root->kiri);
Preorder
(root->kanan);
}
}
|
9.2).
Kunjungan secara Inorder (symmetric order),
mempunyai urutan :
a.
Kunjungi
cabang kiri
b.
Cetak isi
simpul yang dikunjungi (simpul akar)
c.
Kunjungi
cabang kanan
Programnya
adalah sebagai berikut :
Void
inordr (node *root)
{
If
(root != NULL)
{
Inorder
(root->kiri);
Printf
(“%d”, root ->data);
Inorder
(root->kanan);
}
}
|
9.3).
Kunjungan secara postorder, mempunyai urutan :
a.
Kunjungi
cabang kiri
b.
Kunjungi
cabang kanan
c.
Cetak isi
simpul yang dikunjungi (simpul akar)
Programnya
adalah sebagai berikut :
Void
postorder (node *root)
{
If
(root!= NULL)
{
Postorder
(root -> kiri);
Postorder
(root ->kanan);
Printf
(“%d”, root ->data);
}
}
|
10). Contoh
Program Tree
Berikut
ini merupakan program tree
#include
<iostream>
#include
<stdio.h>
#include
<conio.h>
#include
<stdlib.h>
struct
Node{
int
data;
Node
*kiri;
Node
*kanan;
};
int
count;
void
tambah(Node **root, int databaru)
{
if((*root)
== NULL){
Node
*baru;
baru
= new Node;
baru->data
= databaru;
baru->kiri
= NULL;
baru->kanan
= NULL;
(*root)
= baru;
(*root)->kiri
= NULL;
(*root)->kanan
= NULL;
printf("Data
telah Dimasukkan");
}
else
if(databaru < (*root)->data)
tambah(&(*root)->kiri,databaru);
else
if(databaru > (*root)->data)
tambah(&(*root)->kanan,databaru);
else
if(databaru == (*root)->data)
printf("Data
sudah ada!!");
}
void
preOrder(Node *root){
if(root
!= NULL){
printf("%d
" ,root->data);
preOrder(root->kiri);
preOrder(root->kanan);
}
}
void
inOrder(Node *root){
if(root
!= NULL){
inOrder(root->kiri);
printf("%d
",root->data);
inOrder(root->kanan);
}
}
void
postOrder(Node *root){
if(root
!= NULL){
postOrder(root->kiri);
postOrder(root->kanan);
printf("%d
",root->data);
}
}
void
search(Node **root, int cari)
{
if((*root)
== NULL){
printf("Maaf,Data
tidak ditemukan!");
}
else
if(cari < (*root)->data)
search(&(*root)->kiri,cari);
else
if(cari > (*root)->data)
search(&(*root)->kanan,cari);
else
if(cari == (*root)->data)
printf("Data
ditemukan!!!");
}
void
hapus(Node **root, int del)
{
if((*root)
== NULL){
printf("Data
tidak ada!!");
}
else
if(del < (*root)->data)
hapus(&(*root)->kiri,del);
else
if(del > (*root)->data)
hapus(&(*root)->kanan,del);
else
if(del == (*root)->data)
{
(*root)=NULL;
printf("Data
telah Terhapus");
}
}
int
main(){
int
pil,cari,del;
Node
*pohon;
pohon
= NULL;
do{
int
data;
system("cls");
printf(" PROGRAM TREE LANJUTAN \n");
printf("================================\n");
printf(" 1. Masukkan Data \n");
printf(" 2. Transverse \n");
printf(" 3. Cari \n");
printf(" 4. Hapus \n");
printf(" 5. Clear Data \n");
printf(" 6. Keluar \n");
printf("================================\n");
printf("Masukkan
Pilihan Anda : ");
scanf("%d",&pil);
switch(pil){
case
1:
printf("Masukkan
data baru : ");
scanf("%d",
&data);
tambah(&pohon,data);
break;
case
2:
printf("\nPreOrder
: ");
if(pohon!=NULL)
preOrder(pohon);
else
printf("Data masih kosong");
printf("\ninOrder
: ");
if(pohon!=NULL)
inOrder(pohon);
else
printf("Data masih kosong");
printf("\npostOrder
: ");
if(pohon!=NULL)
postOrder(pohon);
else
printf("Data masih kosong");
break;
case
3:
printf("Cari
data : ");
scanf("%d",
&cari);
search(&pohon,cari);
break;
case
4:
printf("Hapus
data : ");
scanf("%d",
&del);
hapus(&pohon,del);
break;
case
5:
pohon
= NULL;
printf("Semua
data telah terhapus");
break;
case
6:
return
0;
default:
printf("Maaf,
pilihan Anda Salah");
}
getch();
}while(pil!=7);
}
|
Output
:
1.
Memasukkan
data
2.
Mencari data
3.
3.
Proses Transverse
4.
Menghapus
data yang diinginkan.
5.
Menghapus
seluruh data yang dimasukkan.
6.
Keluar dari
program.
11). Studi
Kasus Graph
Implementasi Algoritma Greedy
untuk Melakukan Graph Coloring: Studi Kasus Peta Propinsi Jawa
Timur.
Algoritma Greedy merupakan algoritma yang menghasilkan solusi optimum melalui penyelesaian langkah
per langkah (step by
step) dengan menerapkan 2 hal
berikut pada tiap langkahnya:
a.
Pilihan yang
diambil merupakan pilihan terbaik yang dapat
diperoleh pada saat
itu tanpa memperhatikan konsekuensinya ke
depan nanti, hal
ini bersesuaian dengan prinsip
Algoritma Greedy yaitu “take what you can get now”.
b.
Berharap dengan
memilih pilihan terbaik
saat itu (optimum lokal/local optimum) dapat mencapai solusi
terbaik dari permasalahan yang
dihadapi (optimum global/global
optimum). Dalam algoritma Greedy
diasumsikan bahwa optimum lokal merupakan bagian dari optimum global. Sedangkan untuk aplikasinya algoritma Greedy digunakan untuk
pemecahan yang memerlukan
solusi.
Pada permasalahan ini studi kasus yang diangkat adalah peta Jawa
Timur yaitu bagaimana membentuk suatu graf coloring dari sebuah peta, dengan
kota sebagai vertexnya dan jalan protokol sebgai edge-nya. Berikut ini adalah graph
untuk peta Provinsi Jawa Timur.
No
|
Kota
|
Jumlah Edge
|
1
|
Kediri
|
6
|
2
|
Probolinggo
|
5
|
3
|
Malang
|
5
|
4
|
Lumajang
|
3
|
5
|
Jember
|
4
|
6
|
Sidoarjo
|
4
|
7
|
Surabaya
|
4
|
8
|
Bangkalan
|
4
|
9
|
Bojonegoro
|
4
|
10
|
Nganjuk
|
4
|
11
|
Kertosono
|
4
|
12
|
Madiun
|
4
|
13
|
Ponorogo
|
4
|
14
|
Magetan
|
3
|
15
|
Ngawi
|
3
|
16
|
Tulungagung
|
3
|
17
|
Trenggalek
|
3
|
18
|
Blitar
|
3
|
19
|
Jombang
|
3
|
20
|
Mojokerto
|
3
|
21
|
Gresik
|
3
|
22
|
Pasuruan
|
3
|
23
|
Sampang
|
3
|
24
|
Pamekasan
|
3
|
25
|
Situbondo
|
3
|
26
|
Bondowoso
|
3
|
27
|
Banyuwangi
|
2
|
28
|
Sumenep
|
2
|
29
|
Lamongan
|
2
|
30
|
Tuban
|
2
|
31
|
Pacitan
|
2
|
Program untuk studi kasus :
Input
:
#include
<cstdlib>
#include
<iostream>
using
namespace std;
//
inisialisai
const
int MAX = 100;
int
n;
int
a[MAX][MAX];
int
color[MAX];
int
degree[MAX];
int
NN[MAX];
int
NNCount;
int
unprocessed;
void
Coloring();
void
GetInput();
void
Init();
int
MaxDegreeVertex();
void
scannedInit(int scanned[MAX]);
void
UpdateNN(int ColorNumber);
int
FindSuitableY(int ColorNumber, int& VerticesInCommon);
int
MaxDegreeInNN();
void
PrintOutput();
void
Coloring()
{
int x,y;
int ColorNumber = 0;
int VerticesInCommon = 0;
while (unprocessed>0)
{
x = MaxDegreeVertex();
ColorNumber ++;
color[x] = ColorNumber;
unprocessed --;
UpdateNN(ColorNumber);
while (NNCount>0)
{
y = FindSuitableY(ColorNumber,
VerticesInCommon);
if (VerticesInCommon == 0)
y = MaxDegreeInNN();
color[y] = ColorNumber;
unprocessed --;
UpdateNN(ColorNumber);
}
}
}
void
GetInput()
{
cout<<"Masukkan banyak data :
";
cin >> n;
cout<<"Masukkan hubungan graph
: \n";
for (int i=0; i < n; i++){
for (int j=0; j < n; j++){
cout<<"Simpul
"<<i+1<<" - "<<j+1<<" : ";
cin >> a[i][j];
}
}
}
void
Init()
{
for (int i=0; i < n; i++)
{
color[i] = 0;
degree[i] = 0;
for (int j = 0; j < n; j++)
if (a[i][j] == 1)
degree[i] ++;
}
NNCount = 0;
unprocessed = n;
}
int
MaxDegreeVertex()
{
int max = -1;
int max_i;
for (int i =0; i < n; i++)
if (color[i] == 0)
if (degree[i]>max)
{
max = degree[i];
max_i = i;
}
return max_i;
}
void
scannedInit(int scanned[MAX])
{
for (int i=0; i < n; i++)
scanned[i] = 0;
}
void
UpdateNN(int ColorNumber)
{
NNCount = 0;
for (int i=0; i < n; i++)
if (color[i] == 0)
{
NN[NNCount] = i;
NNCount ++;
}
for (int i=0; i < n; i++)
if (color[i] == ColorNumber)
for (int j=0; j < NNCount;
j++)
while (a[i][NN[j]] == 1)
{
NN[j] = NN[NNCount - 1];
NNCount --;
}
}
int
FindSuitableY(int ColorNumber, int& VerticesInCommon)
{
int temp,tmp_y,y;
int scanned[MAX];
VerticesInCommon = 0;
for (int i=0; i < NNCount; i++)
{
tmp_y = NN[i];
temp = 0;
scannedInit(scanned);
for (int x=0; x < n; x++)
if (color[x] == ColorNumber)
for (int k=0; k < n; k++)
if (color[k] == 0
&& scanned[k] == 0)
if (a[x][k] == 1
&& a[tmp_y][k] == 1)
{
temp ++;
scanned[k] = 1;
}
if (temp > VerticesInCommon)
{
VerticesInCommon = temp;
y = tmp_y;
}
}
return y;
}
int
MaxDegreeInNN()
{
int tmp_y;
int temp, max = 0;
for (int i=0; i < NNCount; i++)
{
temp = 0;
for (int j=0; j < n; j++)
if (color[j] == 0 &&
a[NN[i]][j] == 1)
temp ++;
if (temp>max)
{
max = temp;
tmp_y = NN[i];
}
}
if (max == 0)
return NN[0];
else
return tmp_y;
}
void
PrintOutput()
{
cout<<"\n\n";
for (int i=0; i < n; i++)
cout << "Vertex "
<< i+1
<< " warna "
<< color[i] << endl;
}
int
main(int argc, char *argv[])
{
system("color f2");
awal:
GetInput();
Init();
Coloring();
PrintOutput();
cout<<"\nIngin mengulang ?
(y/n) : ";
char p;
cin>>p;
if(p=='y') {
system("cls");
goto awal;
}
else return EXIT_SUCCESS;
}
|
Pada program ini hanya dilakukan
pewarnaan untuk 12 titik dengan jumlah edge terbanyak.
Output :
1.
Masukkan
jumlah simpul dan hubungan antar simpul, berdasarkan matriks ketetanggaan.
2.
Output yang
dihasilkan
Sumber :
Saputri, S. (2016). Graf dan Pohon. Modul Alpro 2-1, 129-162.
Sumber :
Saputri, S. (2016). Graf dan Pohon. Modul Alpro 2-1, 129-162.
Komentar
Posting Komentar