Graph dan Tree

GRAPH DAN TREE

1. Graph

Sebuath graph G=<V,E> terdiri dari sekumpulan titik (nodes atau vertices) V dan sekumpulan garis (arcs atau edges) E. Sebuah garis menghubungkan dua titik u dan v; v dikatakan adjacent to u. Pada graph berarah (directed graph), setiap garis mempunyai arah dari u ke v dan dituliskan sebagai pasangan <u,v> atau u->v. Pada graph tak berarah (undirected graph), garis tidak mempunyai arah dan dituliskan sebagai pasangan {u,v} atau u<->v. Graph tak berarah merupakan graph berarah jika setiap garis tak berarah {u,v} merupakan dua garis berarah <u,v> dan <v,u>.

Sebuah jalur (path) pada G adalah sekumpulan titik <v₀, v₁, v₂, …, v_n> sehingga <v_i, v_i+1> (atau {v_i, v_i+1}), untuk setiap I dari 0 ke n-1 adalah garis pada G. Jalur menjadi sederhana jika tidak ada dua titik yang identik. Jalur merupakan sebuah siklus jika v₀=v_n. Jalur merupakan siklus yang sederhana jika v₀=v_n dan tidak ada dua titik yang identik.

Graph banyak digunakan untuk menggambarkan jaringan dan peta jalan, jalan kereta api, lintasan pesawat, system perpipaan, saluran telepon, koneksi elektrik, ketergantungan diantara task pada sistem manufaktur dan lain-lain. Terdapat banyak hasil dan struktur penting yang didapatkan dari perhitungan dengan graph.

source code algoritma djikstra

#include<stdio.h> #include<conio.h> #include<process.h> #include<string.h> #include<math.h> #define IN 10000 #define N 9 //int dijkstra(int cost[][N], int source, int target); int dijsktra(int cost[][N],int source,int target) { int dist[N],prev[N],selected[N]={0},i,m,min,start,d,j; char path[N]; for(i=1;i< N;i++) {             dist[i] = IN;              prev[i] = -1;             } start = source; selected[start]=1; dist[start] = 0; while(selected[target] ==0) {             min = IN;              m = 0;              for(i=1;i< N;i++)                         {                         d = dist[start] +cost[start][i];                          if(d< dist[i]&&selected[i]==0)                         {                         dist[i] = d;                          prev[i] = start;                         }              if(min>dist[i] && selected[i]==0)                         {                         min = dist[i];                          m = i;                         }             }     start = m;     selected[start] = 1;     } start = target; j = 0; while(start != -1) {             path[j++] = start+65;             start = prev[start];             } path[j]='\0'; strrev(path); //printf("%s", path); return dist[target]; } int main() {             int cost[N][N],i,j,w,ch,co;             int source, target,x,y;             printf("\t****Lintaan Algoritma Terpendek (DIJKSRTRA's ALGORITHM)****\n\n");             for(i=1;i< N;i++)             for(j=1;j< N;j++)             cost[i][j] = IN;             for(x=1;x< N;x++)                         {                          for(y=x+1;y< N;y++)                               {                                     printf(" Masukkan nilai dari jalur antara simpul %d dan %d: ",x,y);                                     scanf("%d",&w);                                     cost [x][y] = cost[y][x] = w;                                     }                         printf("\n");                         }             printf("\n Masukkan asal simpul: ");             scanf("%d", &source);             printf("\n Masukkan target simpul: ");             scanf("%d", &target);             co = dijsktra(cost,source,target);             printf("\n Jalur Terpendek: %d",co);             getch();             return(0);  }

2. Tree

Struktur pohon (tree) biasanya digunakan untuk menggambarkan hubungan yang bersifat hirarkis antara elemen-elemen yang ada. Contoh penggunaan struktur pohon :

• Silsilah keluarga

• Hasil pertandingan yang berbentuk turnamen

• Struktur organisasi dari sebuah perusahaan

Sebuah binary tree adalah sebuah pengorganisasian secara hirarki dari beberapa buah simpul, dimana masing-masing simpul tidak mempunyai anak lebih dari 2. Simpul yang berada di bawah sebuah simpul dinamakan anak dari simpul tersebut. Simpul yang berada di atas sebuah simpul dinamakan induk dari simpul tersebut.

Pohon biner dapat disajikan secara berurutan dengan menggunakan array atau file dan list.

Simpul dalam pohon biner dapat disajikan dengan list sebagai berikut: 

 Deklarasi struktur pohon : 

typedef char TypeInfo; typedef struct Simpul *Tree; struct Simpul { TypeInfo Info; tree Kiri, /* cabang kiri */ tree Kanan; /* cabang kanan */ };

Pohon Biner

Diketahui suatu persamaan ( A + B ) * ( ( B – C ) + D ), maka pembentukan pohon biner dapat dilihat pada tabel di bawah ini :

DAFTAR PUSTAKA

Kadir, Abdul. 2013. From Zero to A Pro Pemrograman C++. Yogyakarta: Andi.