tugas

 

1.    TIPE DATA (v)

Tipe data adalah jenis data yang mampu ditangani oleh suatu bahasa pemrograman pada komputer.

Contoh Tipe Data : 

a.      Tipe data Char dan String
Ini merupakan tipe data dasar, tipe data ini didefinisikan pada deklarsi var dibagian algoritma/program.
Example : Var Nama : String
Nilai : Char

b.      Tipe data Boolean
Tipe data ini digunakan untuk pengambilan keputusan dalam operasi logika. Terdiri dari true disimbolkan ‘T’ dan False yang disimbolkan ‘F’. Ketika kita ingin mendapatklan hasil yang valid/pasti, kita menggunakan tipe data boolean untuk memperoleh keputusan dalam suatu penyelesaian yang pasti.

c.       Tipe Data Integer
Merupakan tipe data bilangan bulat.

Tipe Data
Rentang nilai
Memori
Byte
0…255
1 byte
Word
0…65.555
1 byte
Integer
-32.768 s.d 32.767
2 byte
Long Integer
-2.147.483.648
4 byte 

d.      Tipe Data Real
Merupakan tipe data bilangan pecahan seperti real, single, double, comp, extend. 

e.       Tipe Data Subrange
Merupakan tipe data bilangan yang punya jangkauan nilai tertentu sesuai dengan definisi pada pemrogram.
Example:
Type Variabel=Nilai_awal…Nilai_akhir 

f.       Tipe Data Enumerasi
Merupakan tipe data yang memiliki elemen-elemen tertentu yang disebut satu/satu dari bernilai konstanta integer sesuai dengan urutannya. Pada tipe data ini elemen masukan diwakili oleh suatu nama variable yang ditlis di dalam kurung.
Example :
Indeks_Hari = (Nol, Minggu, Senin, Selasa, Rabu, Kamis, Jumat, Sabtu) 

g.      Tipe Data Array (Larik)
Tipe data ini sudah terstruktur dengan baik, walaupun masih sederhana. Tipe data ini menampung sejumlah data dengan tipe data sama (homogen) dalam sebuah variabel.
Cara mendefinisikan tipe data array :
Berdimensi satu
Var
Nama_Variabel_Array[1...N]of tipe_data
1 Nomor Indeks
Berdimensi dua
Var
Nama_Variabel_Array=Array[1...N,1...M]of tipe_data
2 buah Nomor Indeks 

h.      Tipe Data Record
Tipe data komposit yang sudah terstruktur denagn baik. Tipe data ini digunakan untuk menampung data suatu obyek. Datanya berupa campuran dari tipe data seperti string, numerik, char, boolean, atau tipe data lainnya. Tipe data ini merupakan struktur dasar dari suatu sistem database. 

i.        Tipe Data Array Record
Tipe data array yang dibangun dari tipe data record. 

j.        Tipe Data Citra
Berisi grafik/gambar yang banyak digunakan pada aplikasi video. 

2.    PROCEDURE & FUNCTION

A.  PROCEDURE

Merupakan blok program yg terpisah dr program lain ( modul / sub program ), dan dapat dipanggil dari program lain dengan menyebutkan nama dari procedure yg bersangkutan.
Contoh :
    program pemakaian_procedure;
    uses crt;
    procedure input_data;
    begin
        write ( “ NIM = “ ); readln ( nim ) ;
        write ( “ Nama = “ ); readln ( nama ) ;
    end;
    var     nim : string [ 14 ] ;
        nama : string [ 20 ] ;
    begin
        clrscr ;
        input_data;
        writeln ( “ Selesai … “ ) ;
    end

B.  FUNCTION

Blok fungsi hampir sama dengan procedure, hanya saja fungsi harus di deklarasikan dengan tipe nya. Buat program untuk menghitung jumlah 2 bilangan yg dilakukan dg fungsi & nilai dari kedua bilangan tsb, dikirimkan dr luar fungsi, yg mana nilai dari kedua bilangan harus diinputkan.
Program penjumlahan;
    Uses crt :
    Var bil1, bil2: byte;
    function hasil (var A,B: byte) : integer;
    Begin
        hasil:=A+B;
    end;
    begin
        clrscr;
        write (‘Bilangan 1=‘);readln(bil1);
        write (‘Bilangan 2=‘);readln(bil2);
        write (‘Bilangan1+Bilangan2=“, hasil(bil1,bil2));
    end

3.    ARRAY & RECORD (v)

A.   ARRAY

Pengertian Array adalah Array (larik) merupakan tipe data tersetruktur dimana didalamnya terdiri dari komponen-komponen yang mempunyai tipe data yang sama. Didalam suatu array jumlah komponen banyaknya adalah tetap. Didalam suatu larik atau array setiap kompoenen ditunjukan oleh suatu index yang unik. Index dari setiap komponen array menunjukan urutan data atau identitas yang mewakili data yang ada didalamnya.Logika sederhananya array itu bisa disamakan dengan dua orang dengan nama yang sama didalam suatu komunitas, untuk membedakan antara nama yang satu atau dengan nama yang lain maka diberikan initial tambahan untuk setiap nama.

a.      Deklarasi Array
Didalam penulisan bahasa pemograman setiap penggunaan array harus dideklarsikan terlebih dahulu. Pendeklarasian array diawali dengan nama variabel array diikuti dengan indeks array yang dituliskan didalam tanda “[]” , diikuti dengan kata cadangan of dan tipe data yang dibutuhkan.
Bentuk Umum Penulisan
Tanda_pengenal : array [..tipe index ..] of tipe data;
Contoh :
Var
A : array[1..4] of integer;
B : array[1..5] of string;
C: array[1..10] of real;

Keterangan :

a.      A,B,C merupakan tanda pengenal/ nama variabel dari array;

b.      1..4 : merupakan tipe indek dari array, yang menunjukan banyaknya data yang mampu disimpan.

c.       Integer : menunjukan bahwa data yang diinput berupa bilangan bulat.

b.      Contoh Program Array 1 dimensi

program INT_ARRAY;

uses wincrt;

const N=10;

type int_array = ARRAY [1..N] of integer;

var bil : int_array;

indeks : integer;

BEGIN

Writeln('masukkan sepuluh bilangan integer.');

for indeks := 1 to 10 do

begin

readln(bil[indeks]); { loop untuk memasukkan elemen array }

end;

writeln('Isi dari array ini adalah'); { tampilkan setiap elemen }

for indeks := 1 to 10 do

begin

writeln('bil[', indeks:2,'] adalah ',bil[indeks] );

end

END.

B.  RECORD

Pengertian Sebuah record rekaman disusun oleh beberapa field. Tiap field berisi data dari tipe dasar / bentukan tertentu. Record mempunyai kelebihan untuk menyimpan suatu sekumpulan elemen data yang berbeda-beda tipenya (di banding array).

Contoh Program record :

program RECORD_INTRO;

type tanggal = record

bulan, hari, tahun : integer;

end;

var waktu : tanggal;

begin

waktu.hari :=25;

waktu.bulan:=09;

waktu.tahun:= 1983;

writeln('hari ini adalah

',waktu.hari,':',waktu.bulan,':', waktu.tahun)

End.

4.    REKURSIF

Rekursif berarti bahwa suatu proses bisa memanggil dirinya sendiri. Menurut definisi dalam Microsoft Bookshelf, Rekursif adalah kemampuan suatu rutin untuk memanggil dirinya sendiri. Dalam Rekursif sebenarnya terkandung pengertian prosedur dan fungsi. Perbedaannya adalah bahwa rekursif bisa memanggil ke dirinya sendiri, tetapi prosedur dan fungsi harus dipanggil lewat pemanggil prosedur dan fungsi. Rekursif merupakan teknik pemrograman yang penting dan beberapa bahasa pemrograman mendukung keberadaan proses rekursif ini. Dalam prosedur dan fungsi, pemanggilan ke dirinya sendiri bisa berarti proses berulang yang tidak bisa diketahui kapan akan berakhir.
Kelebihan Perulangan Rekursif:

a.      Sangat mudah untuk melakukan perulangan dengan batasan yang luas dalam artian melakukan perulangan dalam skala yang besar.

b.      Dapat melakukan perulangan dengan batasan fungsi.
Kekurangan Perulangan Rekursif:

c.       Tidak bisa melakukan nested loop atau looping bersarang.

d.      Biasanya membuat fungsi sulit untuk dipahami, hanya cocok untuk persoalan tertentu saja.

e.       Trace error sulit.

f.       Memerlukan stack yang lebih besar, sebab setiap kali fungsi dipanggil, variabel lokal dan parameter formal akan ditempatkan ke stack dan ada kalanya akan menyebabkan stack tak cukup lagi (Stack Overrun).

g.      Proses agak berbelit-belit karena terdapat pemangilan fungsi yang berulang-ulang dan pemanggilan data yang ditumpuk.

Contoh paling sederhana dari proses rekursif ini adalah proses menghitung nilai factorial dari suatu bilangan bulat positif dan mencari deret Fibbonacci dari suatu bilangan bulat.

Nilai factorial secara rekursif dapat ditulis sebagai :

0 ! = 1

N ! = N x (N-1) !

yang secara pemrograman dapat ditulis sebagai :

Faktorial(0)  = 1                                                                                  (1)

Faktorial(N) = N*Faktorial(N-1)                                                        (2)

Persamaan (1) tidak bersifat rekursif, disebut nilai awal atau basis. Setiap fungsi rekursif paling sedikit  mempunyai satu nilai awal, jika tidak fungsi tersebut tidak bisa dihitung secara eksplisit.

Persamaan (2) di atas adalah contoh hubungan rekurens (recurrence relation), yang berarti bahwa nilai suatu fungsi dengan argumen tertentu bisa dihitung dari fungsi yang sama dengan argumen yang lebih kecil.

Bilangan Fibbonacci didefinisikan sebagai berikut :

                 1    1    2    3    5    8    13    21    34    55    89   …

dari barisan tersebut dapat dilihat bahwa bilangan ke-N (N>2) dalam barisan dapat dicari dari dua bilangan sebelumnya yang terdekat dengan bilangan N, yaitu bilangan ke-(N-1) dan bilangan ke-(N-2),

sehingga dapat dirumuskan sebagai :

Fibbonacci(1) = 1                                                                                (1)

Fibbonacci(2) = 1                                                                                (2)

Fibbonacci(N) = Fibbonacci(N-1) + Fibbonacci(N-2)                        (3)

Dengan persamaan (1) dan (2) adalah basis dan persamaan (3) adalah rekurensnya.

5.    SORTING

Sorting adalah suatu proses pengurutan data yang sebelumnya disusun secara acak atau tidak teratur menjadi urut dan teratur menurut suatu aturan tertentu.

Sorting dapat dibedakan menjadi dua jenis yaitu ascending dan descending. 

Ø  Ascending adalah pengurutan data dari kecil ke besar

Ø  Descending adalah pengurutan data dari besar ke kecil. 

Dengan cara program yang dibuat harus dapat membandingkan antar data yang di inputkan. Artinya jika ada deretan data, maka data yang pertama akan membandingkan dengan data yang kedua. Jika data yang pertama lebih besar dari pada data yang kedua maka data yang pertama akan bertukar posisi dengan data yang kedua, begitu seterusnya sampai benar-benar data terurut dari yang terbesar hingga yang terkecil.

6.    SEARCHING

Searching adalah pencarian data dengan cara menelusuri data-data tersebut.
Tempat pencarian data dapat berupa array dalam memori, bisa juga pada file pada external storage.

Ada dua macam teknik pencarian yaitu pencarian sekuensial dan pencarian biner. Perbedaan dari dua teknik ini terletak pada keadaan data. Pencarian sekuensial digunakan apabila data dalam keadaan acak atau tidak terurut (contoh: sequential search). Sebaliknya, pencarian biner digunakan pada data yang sudah dalam keadaan urut (contoh: Binary serach dan interpolation search).

7.    POINTER

Pointer (variabel penunjuk) adalah suatu variabel yang berisi alamat memori dari suatu variabel lain. Alamat ini merupakan lokasi dari obyek lain (biasanya variabel lain) di dalam memori. Contoh, jika sebuah variabel berisi alamat dari variabel lain, variabel pertama dikatakan menunjuk ke variabel kedua.

Deklarasi Pointer
Seperti halnya variabel yang lain, variabel pointer juga harus dideklarasikan terlebih dahulu sebelum digunakan.

Bentuk Umum : Tipe_data *nama_pointer;

Contoh Program :

#include <constream.h>

int *px;

char *sh;

void main()

{ int x, y; /* x dan y bertipe int */

 int *px; /* px pointer yang menunjuk objek */

 clrscr();

 x = 87;

 px = &x; /* px berisi alamat dari x */

 y = *px; /* y berisi nilai yang ditunjuk px */

 cout<<“Alamat x =”<<&x <<\n”;

 cout<<“Isi px = \n”, px);

 cout<<“Isi x = \n”, x);

 cout<<“Nilai yang ditunjuk oleh px = \n”, *px);

 cout<<“Nilai y = \n”, y);

 getch();}

Operasi Pointer

a.      Operasi Penugasan

Suatu variable pointer seperti halnya variable yang lain, juga bisa mengalami operasi penugasan. Nilai dari suatu variable pointer dapat disalin ke variable pointer yang lain.

Contoh Program :

#include <constream.h>

void main()

{float *x1,y, *x2;

clrscr();

y = 13.45;

x1 = &y;                      /* Alamat dari y disalin ke variabel x1 */

x2 = x1;                      /* Isi variabel x1 disalin ke variabel x2 */

cout<<"Nilai variabel y =  "<<y<< " ada di alamat "<< x1<<"\n";

cout<<"Nilai variabel y =  "<<y<< " ada di alamat "<< x2<<"\n";

getch();}

b.      Operasi Aritmatika

Suatu variabel pointer hanya dapat dilakukan operasi aritmatika dengan nilai integer saja. Operasi yang biasa dilakukan adalah operasi penambahan dan pengurangan. Operasi penambahan dengan suatu nilai menunjukkan lokasi data berikutnya (index selanjutnya) dalam memori. Begitu juga operasi pengurangan.

Contoh Program :

#include <constream.h>

void main()

{int nilai[3], *penunjuk;

clrscr();

nilai[0] = 125;

nilai[1] = 345;

nilai[2] = 750;

penunjuk = &nilai[0];

cout<<"Nilai "<<*penunjuk <<" ada di alamat memori " <<penunjuk<<"\n";

cout<<"Nilai "<<*(penunjuk+1) <<" ada di alamat memori " <<penunjuk+1<<"\n";

cout<<"Nilai "<<*(penunjuk+2) <<" ada di alamat memori " <<penunjuk+2<<"\n";

getch();}

c.       Operasi Logika

Suatu pointer juga dapat dikenai operasi logika.

Contoh Program :

#include<constream.h>

void main()

{int a = 100, b = 200, *pa, *pb;

clrscr();

pa = &a;

pb = &b;

cout<<"nilai pa= "<<pa<< " nilai pb= "<<pb<<"\n";

if(pa < pb)

cout<<"pa menunjuk ke memori lebih rendah dari pb\n";

if(pa == pb)

cout<<"pa menunjuk ke memori yang sama dengan pb\n";

if(pa > pb)

cout<<"pa menunjuk ke memori lebih tinggi dari pb\n";

getch();}

8.    STACK (TUMPUKAN)

Dalam ilmu komputer, stack atau tumpukan merupakan sebuah koleksi objek yang menggunakan prinsip LIFO (Last In First Out), yaitu data yang             terakhr kali dimasukkan akan pertama kali keluar dari stack tersebut. Stack dapat diimplementasikan sebagai representasi berkait atau kontigu (dengan tabel fix).

Ciri Stack :

Elemen TOP (puncak) diketahui penisipan dan penghapusan elemen selalu dilakukan di TOP

LIFO

Pemanfaatan Stack :

Perhitungan ekspresi aritmatika (posfix) algoritma backtraking (runut balik) algoritma rekursif.

Operasi Stack yang biasanya :

Push (input E : typeelmt, input/output data : stack): menambahkan sebuah elemen ke stack.

Pop (input/output data : stack, output E : typeelmt ) : menghapus sebuah elemen stack.

v  IsEmpty ()

v  IsFull ()

dan beberapas selektor yang lain.

9.    QUEUE (ANTREAN)

Struktur data antrean atau queue adalah suatu bentuk khusus dari linear list, dengan operasi penyisipan (insertion) hanya diperbolehkan pada salah satu sisi, yang disebut sisi belakang (REAR), dan operasi penghapusan (deletion) hanya diperbolehkan pada sisi lainnya, yang disebut sisi depan (FRONT), dari list.
Sebagai contoh dapat kita lihat antrean (Q1, Q2,…,QN). Kita notasikan bagian depan dari antrean Q sebagai FRONT(Q) dan bagian belakang sebagai REAR(Q).
Jadi untuk antrean Q = [Q1, Q2, …, QN] :
FRONT(Q) = Q1 dan REAR(Q) = QN
Kita menggunakan notasi NOEL(Q) untuk menyatakan jumlah elemen di dalam antrean Q. NOEL(Q) mempunyai harga integer. Untuk antrean Q = [Q1,Q2,…, QN],
maka NOEL(Q) = N.
Operator penyisipan (insertion) disebut INSERT dan operator penghapusan (deletion)
disebut REMOVE.

10.    LINKED LIST

Linked List ada dua macam, yaitu :

Linked List adalah salah satu bentuk struktur data, berisi kumpulan data (node) yang tersusun secara sekuensial, saling sambungmenyambung, dinamis dan terbatas. 

Ø  Linked List sering disebut juga Senarai Berantai 

Ø  Linked List saling terhubung dengan bantuan variabel pointer 

Ø  Masing-masing data dalam Linked List disebut dengan node (simpul) yang menempati alokasi memori secara dinamis dan biasanya berupa struct yang terdiri dari beberapa field. 

Single Linked List adalah sebuah LINKED LIST yang menggunakan sebuah variabel pointer saja untuk menyimpan banyak data dengan metode LINKED LIST, suatu daftar isi yang saling berhubungan.

11.    TREE

Contoh Binary Search Tree pada c++ - 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 kiri 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&kanan) itu sendiri adalah juga bst.sebuah bst, pada dasarnya adalah sebuah pohon biner (binary tree), oleh karena itu, kita dapat melakukan traversal pada setiap node dengan metode inorder, preorder maupun postorder. dan jika kita melakukan traversal dengan metode inorder, pada dasarnya kita telah melakukan traversal valuenya secara terurut dari kecil ke besar, jadilah ini sebagai sorting algoritma.

Struktur data bst ( binary search tree )sangat penting dalam struktur pencarian, misalkan, dalam kasus pencarian dalam sebuah list, jika list sudah dalam keadaan terurut maka proses pencarian akan sangat cepat, jika kita menggunanan list contigue dan melakukan pencarian biner. akan tetapi, jika kita ingin melakukan perubahan isilist (insert atau delete), menggunakan list contigue akan sangat lambat, karena proses insert dan delete dalam list contigue butuh memindahkan banyak elemen setiap saat. mungkin kita bisa juga menggunakan 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 sequential. Sebaliknay binary tree memberikan jawaban sempurna atas semua permasalahan ini, dengan memanfaatkan binary tree kita dapat melakukan pencarian elemen/node value dalam kompleksitas algorimta (big O) O(n log n) langkah saja.

Contoh Binary Tree :

Traversal (Penelusuran) Pohon

Ada tiga algoritma, yaitu: Pre Order, In Order dan Post Order

Ø  Pre Order

a.      Proses akar

b.      Telusur Anak kiri dalam Pre Order

c.       Telusur Anak kanan dalam Pre Order

Ø  In Order

a.      Telusur Anak kiri dalam In Order

b.      Proses

c.       Telusur Anak kanan dalam In Order

Ø  Post Order

a.      Telusur Anak kiri dalam Post Order

b.       Telusur Anak kanan dalam Post Order

c.        Proses

12.    GRAPH

Graph adalah sekelompok simpul-simpul (nodes/vertices) V, dan sekelompok sisi (edges) E yang menghubungkan sepasang simpul. Bayangkan simpul-simpul tersebut sebagai lokasi-lokasi, maka himpunan dari simpul-simpul tersebut adalah himpunan lokasi-lokasi yang ada. Dengan analogi ini, maka sisi merepresentasikan jalan yang menghubungkan pasangan lokasi-lokasi tersebut.
Graf juga didefinisikan sebagai himpunan benda-benda yang disebut verteks (node) yang terhubung oleh sisi (atau edge ata u arc). biasanya graf digambarkan sebagai kumpulan titik-titik (melambangkan verteks) yang dihubungkan oleh garis-garis (melambangkan sisi).
Contoh implementasi graf pada struktur data :

1.      Graf tak berarah (undirected graph)

Graf yang sisinya tidak mempunyai orientasi arah disebut graf tak berarah. Paragraf tak-berarah, urutan pasangan simpul yang dihubungkan oleh sisi tidak diperhatikan. salah satu contoh graf tak berarah dimana sisi-sisi yang menghubungkan antar simpul dalam graf tersebut tidak memiliki orientasi arah.

2.      Graf Berarah (directed graph)

Graf yang setiap sisinya memiliki orientasi arah disebut sebagai graf berarah. Sisi berarah dalam graf ini dapat dinamakan sebagai busur (arc). Lain halnya dengan graf tak-berarah, urutan pasangan simpul disini sangat diperhatikan karena dapat menyatakan hal yang berbeda. contoh dari graf berarah yang memiliki sisi-sisi dengan orientasi arah (busur).

Digraph & Undigraph

1.    Graph Berarah (directed graph atau digraph)

Jika sisi-sisi pada graph, misalnya {x, y} hanya berlaku pada arah-arah tertentu saja, yaitu dari x ke y tapi tidak dari y ke x; verteks x disebut origin dan vertex y disebut terminus dari sisi tersebut. Secara grafis maka penggambaran arah sisi-sisi digraph dinyatakan dengan anak panah yang mengarah ke verteks terminus, secara notasional sisi graph berarah ditulis sebagai vektor dengan (x, y). 

2.    Graph Tak Berarah (undirected graph atau undigraph)

Setiap sisi {x, y} berlaku pada kedua arah: baik x ke y maupun y ke x. Secara grafis sisi pada undigraph tidak memiliki mata panah dan secara notasional menggunakan kurung kurawal.

Dalam masalah-masalah graph undigraph bisa dipandang sebagai suatu digraph dengan mengganti setiap sisi tak berarahnya dengan dua sisi untuk masing-masing arah yang berlawanan. 

Selain itu, berdasarkan definisi ini maka struktur data linear maupun hirarkis adalah juga graph. Node-node pada struktur linear atupun hirarkis adalah verteks-verteks dalam pengertian graph dengan sisi-sisinya menyusun node-node tersebut secara linear atau hirarkis. Sementara kita telah ketahui bahwa struktur data linear adalah juga tree dengan pencabangan pada setiap node hanya satu atau tidak ada. Linear 1-way linked list adalah digraph, linear 2-way linked list bisa disebut undigraph.

Aspek Algoritmis

Walau secara konseptual struktur linear adalah subset dari tree dan demikian pula tree adalah subset dari graph, dalam aplikasinya perlu dibedakan cara penanganan struktur-struktur tersebut untuk mencapai efisiensi algoritmis. Algoritma-algoritma untuk graph secara umum terlalu mahal apabila digunakan pada struktur hirarkis (tree), apalagi pada struktur linear. Jadi apabila masalah yang dihadapi pada dasarnya hanya merupakan masalah dengan struktur data hirarkis saja maka cukup lah kita menggunakan representasi dan algoritma-algoritma tree. 

Konektivitas pada Undigraph

Adjacency: Dua verteks x dan y yang berlainan disebut berhubungan langsung (adjacent) jika terdapat sisi {x, y} dalam E.

Ø  Path

Sederetan verteks yang mana setiap verteks adjacent dengan verteks yang tepat berada disebelahnya.

Ø  Panjang dari path

 Jumlah sisi yang dilalui path.

Ø  Siklus

Suatu path dengan panjang lebih dari satu yang dimulai dan berakhir pada suatu verteks yang sama.

Ø  Siklus sederhana

Dalam undigraph, siklus yang terbentuk pada tiga atau lebih verteks-verteks yang berlainan yang mana tidak ada verteks yang dikunjungi lebih dari satu kali kecuali verteks awal/akhir.

Dua verteks x dan y yang berbeda dalam suatu undigraph disebut berkoneksi (connected) apabila jika terdapat path yang menghubungkannya. Himpunan bagian verteks S disebut terkoneksi (connected) apabila dari setiap verteks x dalam S terdapat path ke setiap verteks y (y bukan x) dalam S. Suatu komponen terkoneksi (connected components) adalah subgraph (bagian dari graph) yang berisikan satu himpunan bagian verteks yang berkoneksi. Suatu undigraph dapat terbagi atas beberapa komponen yang terkoneksi; jika terdapat lebih dari satu komponen terkoneksi maka tidak terdapat path dari suatu verteks dalam satu komponen verteks di komponen lainnya.

Ø  Pohon bebas (free tree)

Suatu undigraph yang hanya terdapat satu komponen terkoneksi serta tidak memiliki siklus sederhana.

Konektivitas pada Digraph

Terminologi di atas berlaku juga pada Digraph kecuali dalam digraph harus dikaitkan dengan arah tertentu karena pada arah yang sebaliknya belum tentu terdefinisi. 

Ø  Adjacency ke / dari

Jika terdapat sisi (x,y) maka dalam digraph dikatakan bahwa x "adjacent ke" y atau y "adjacent dari" x. Demikian pula jika terdapat path dari x ke y maka belum tentu ada path dari y ke x Jadi dalam digraph keterkoneksian didefinisikan lebih lanjut lagi sebagai berikut.

Ø  Terkoneksi dengan kuat

Himpunan bagian verteks S dikatakan terkoneksi dengan kuat (strongly connected) bila setiap pasangan verteks berbeda x dan y dalam S, x berkoneksi dengan y dan y berkoneksi denganx (dpl., ada path dari x ke y dan sebaliknya dari y ke x).

Ø  Terkoneksi dengan Lemah

Himpunan bagian verteks S dikatakan terkoneksi dengan lemah (weakly connected) bila setiap pasangan verteks berbeda x dan y dalam S, salah satu: x berkoneksi dengan y (atau yberkoneksi dengan x) dan tidak kebalikan arahnya (dpl., hanya terdefinisi satu path: dari x ke y atau sebaliknya dari y ke x).

Himpunan Keterhubungan Langsung

Cara pendefinisian lain untuk graph adalah dengan menggunakan himpunan keterhubungan langsung Vx. Pada setiap verteks x terdefinisi Vx sebagai himpunan dari verteks-verteks yang adjacent dari x. Secara formal: 

Vx = {y | (x,y) ΠE}

Dalam digraph didefinisikan juga terminologi-terminologi berikut ini. Predesesor dari suatu verteks x (ditulis Pred(x)) adalah himpunan semua verteks yang adjacent ke x. Suksesor dari verteks x (ditulis Succ(x)) adalah himpunan semua verteks yang adjacent dari x; yaitu adjacency set di atas.

Degree

Degree dari suatu verteks x dalam undigraph adalah jumlah sisi di mana di salah satu ujungnya terdapat x.

Ø  Indegree dari suatu verteks x dalam digraph adalah jumlah dari predesesor x.

Ø  Outdegree dari suatu verteks x dalam digraph adalah jumlah dari suksesor x.

Graph berbobot (weighted graph)

Apabila sisi-sisi pada graph disertai juga dengan suatu (atau beberapa) harga yang menyatakan secara unik kondisi keterhubungan tersebut maka graph tersebut disebut graph berbobot. Biasanya dalam masalah-masalah graph bobot tersebut merupakan "biaya" dari keterhubungan ybs. Pengertian "biaya" ini menggeneralisasikan banyak aspek: biaya ekonomis dari proses/aktifitas, jarak geografis/tempuh, waktu tempuh, tingkat kesulitan, dan lain sebagainya. Dalam beberapa masalah lain bisa juga bobot tersebut memiliki pengertian "laba" yang berarti kebalikan dari "biaya" di atas. Dalam pembahasan algoritma-algoritma graph nanti pengertian bobot akan menggunakan pengertian biaya sehingga apabila diaplikasikan pada masalah yang berpengertian laba maka kuantitas-kuantitas terkait adalah kebalikannnya. Misalnya mencari jarak tempuh minimum digantikan dengan mencari laba maksimum. 

Daftar Pustaka

-       Shandy Johan Blog

-       Wiki.co.id

-       Shafiqhusein’s Blog

-       Devia christa Blog

-       Blognapi Blog

-       Panjaitan sister Blog

-       For free Blog