POHON & GRAPH C++

POHON & GRAPH C++

A. Pengertian Pohon Algoritma
Pohon adalah graf tak berarah terhubung yang tidak mengandung sirkuit.Hutan(forest) adalah kumpulan  pohon yang saling lepas, atau graf tidak terhubung yang tidak mengandung sirkuit. Setiap komponen di dalam graf terhubung tersebut adalah pohon.

     Teorema. Misalkan G = (V, E) adalah graf tak-berarah sederhana dan jumlah simpulnya n. Maka, semua pernyataan di bawah ini adalah ekivalen:

1.  G adalah pohon.

2.  Setiap pasang simpul di dalam G terhubung dengan lintasan tunggal.

3.  G terhubung dan memiliki m = n – 1 buah sisi.

4.  G tidak mengandung sirkuit dan memiliki m = n – 1  buah sisi.

5.  G tidak mengandung sirkuit dan penambahan satu sisi pada graf akan membuat hanya satu sirkuit.

6.  G terhubung dan semua sisinya adalah jembatan.

      Teorema di atas dapat dikatakan sebagai definisi lain dari pohon.

Algoritma Kruskal  ( Langkah 0: sisi-sisi dari graf sudah diurut menaik berdasarkan bobotnya – dari bobot kecil ke bobot besar)

Algoritma Kruskal

Langkah 1:  T masih kosong 

Langkah 2: pilih sisi (u, v) dengan bobot minimum yang tidak membentuk  sirkuit di T. Tambahkan (u, v) ke dalam T.

Langkah 3:   ulangi langkah 2 sebanyak n – 1 kali.

Procedure Kruskal(input G : graf, output T : pohon) { Membentuk pohon merentang minimum T dari graf terhubung – berbobot G.  Masukan: graf-berbobot terhubung G = (V, E), dengan  V  = n Keluaran: pohon rentang minimum T = (V, E’)  } Deklarasi   i, p, q, u, v : integer

Algoritma   ( Asumsi: sisi-sisi dari graf sudah diurut menaik       berdasarkan bobotnya – dari bobot kecil ke bobot       besar)   T  {}    while jumlah sisi T < n-1 do     Pilih sisi (u,v) dari E yang bobotnya terkecil     if (u,v) tidak membentuk siklus di T then        T  T  {(u,v)}    

B.     Pengertian Graph algoritma

Graph digunakan untuk merepresentasikan objek-objek diskrit dan hubungan antara objek-objek tersebut.

Gambar berikut ini sebuah graph yang menyatakan peta jaringan jalan raya yang menghubungkan sejumlah kota di Provinsi Jawa Tengah.
 

Graph G = (V, E), yang dalam hal ini:

     V  = himpunan tidak-kosong dari simpul-simpul

             (vertices)

          = { v1 , v2 , ... , vn }

     E  = himpunan sisi  (edges) yang 

            menghubungkan sepasang simpul

         = {e1 , e2 , ... , en }

G₁ adalah graph dengan

V = { 1, 2, 3, 4 }

E = { (1, 2), (1, 3), (2, 3),

         (2, 4), (3, 4)} 

C. Contoh program pohon atau kruskal
 
Hasil running : 

D. Contoh program djikstral (graph)


 
 
 

Hasil running :
 

Daftar pustaka :

https://gapuriberbagi.wordpress.com/program-c-stack-queue-searching-sorting-pohon-dan-graph/ 

Ridho Ramadhan

1801301095

2C