Graph

Graph adalah kumpulan dari titik ( node ) dan garis dimana pasangan-pasangan titik ( node ) tersebut dihubungkan oleh segmen garis. Node ini biasa disebut simpul (verteks) dan segmen garis disebut ruas (edge).

Graph dipakai untuk membantu pemecahan masalah. Dari model graph yang dibuat, suatu masalah dapat dipahami menjadi lebih mudah. Untuk kemudian diturunkan metode pemecahannya.

• ·         Berdasarkan jumlah simpul pada suatu graph, maka secara umum graph dapat digolongkan menjadi dua jenis:

1. Graph berhingga (limited graph)

Graph berhingga adalah graph yang jumlah simpulnya, n, berhingga.

2. Graph tak-berhingga (unlimited graph)

• Graph yang jumlah simpulnya, n, tidak berhingga banyaknya disebut graph tak-berhingga.

·         Berdasarkan orientasi arah pada sisi, maka secara umum graph dibedakan atas 2 jenis:

1. Graph tak-berarah (undirected graph)

Graph yang sisinya tidak mempunyai orientasi arah disebut graph tak-berarah.

2. Graph berarah (directed graph atau digraph)

Contoh Program Graph :

#include 
#include 
void main(){
bool ketemu,nolsemua;
int matrix[10] [10];
int i,j,jumlah_simpul,jumlah_sisi,asal,tujuan;
//isnisialisasi matrix
cout<<"jumlah simpul:";
cin>>jumlah_simpul;
cout<<"jumlah_sisi:";
cin>>jumlah_sisi;
for (i=1;i<=jumlah_simpul;i++)
for (j=1;j<=jumlah_simpul;j++)
matrix[i][j]=0;
//isi matrix sesuai input graf
for (i=1;i<=jumlah_sisi;i++){
cout<<"simpul asal:";
cin>>asal;
cout<<"simpul tujuan:";
cin>>tujuan;
matrix[asal][tujuan]=1;
matrix[tujuan][asal]=1;
}
//telusuri graf
i=1;nolsemua=false;
while (i<=jumlah_simpul && !nolsemua){
j=1;ketemu=false;
while (j<=jumlah_simpul && !ketemu){
if (matrix[i][j]==1)
ketemu=true;
else
j++;
}
if (!ketemu)
nolsemua=true;
else
i++;
}

if(nolsemua)
cout<<"graf tidak terhubung";
else
cout<<"graf terhubung";
getch();

}