Graph menggunakan Adjacent Matrix dan Traversal DFS - Deep First Search

Latihan Graph Menggunakan Adjacent Matrix dan Traversal DFS - Deep First Search Secara Recursive DFS

1:  #include <iostream> 
2:  using namespace std; 
3:  int e = 7;     //jumlah edge 
4:  int n = 5;     //jumlah vertex/node 
5:  bool mat[5][5] = { false };     //matrix 2D untuk menyimpan graph 
6:  int result[5]; 
7:  int idxResult = 0; 
8:  bool isInResult(int n) { 
9:       for (int i = 0; i < idxResult; i++) { 
10:            if (n == result[i])return true; 
11:       } 
12:       return false; 
13:  } 
14:  void addToResult(int n) { 
15:       result[idxResult] = n; 
16:       idxResult++; 
17:  } 
18:  void DFS(int parent) { 
19:       if (!isInResult(parent)) {               //cek di Result sebelumnya 
20:            addToResult(parent); 
21:            for (int i = 0; i < n; i++) {     //mencari childs from parent 
22:                 if (mat[parent][i] == true) { 
23:                      DFS(i);                         //memasukkan setiap child ke DFS 
24:                 } 
25:            } 
26:       } 
27:  } 
28:  int main() {     //Undirected Graph 
29:       int v1[] = { 1,1,2,2,2,3,4 };     //hubungan antar vertex 
30:       int v2[] = { 2,5,3,4,5,4,5 }; 
31:       for (int i = 0; i < e; i++) {          //memasukkan undirected graph kedalam matrix 
32:            mat[v1[i] - 1][v2[i] - 1] = true; 
33:            mat[v2[i] - 1][v1[i] - 1] = true; 
34:       } 
35:       for (int i = 0; i < n; i++) {          //menampilkan matriks graph 
36:            for (int j = 0; j < n; j++) { 
37:                 cout << mat[i][j] << " "; 
38:            } 
39:            cout << endl; 
40:       } cout << endl; 
41:       int firstVertex = 0;     //inisialisasi vertex awal 
42:       DFS(firstVertex); 
43:       for (int i = 0; i &lt; n; i++) { 
44:            cout << result[i] + 1 << " "; 
45:       } cout << endl; 
46:       system("pause"); 
47:  } 

Special thanks to Samsung Academy SRIN Lecturer:
1. Pak Risman Adnan Mattotorang
2. Mas Leonardi
3. Mas Gilang
4. Mas Susanto Tedja

Graph menggunakan Adjacent List dan Traversal BFS - Bread First Search

Latihan Graph Menggunakan Adjacent List (Linked List) dan Traversal BFS - Bread First Search Menggunakan Queue


1:  #include <iostream>; 
2:  using namespace std; 
3:   
4:  struct node { 
5:       int value; 
6:       node *next; 
7:  }; 
8:   
9:  struct linkedList { 
10:       node *head=NULL; 
11:       node *tail=NULL; 
12:   
13:       void addList(int n) { 
14:            node *node_isi = new node(); 
15:            node_isi->value = n; 
16:            node_isi->next = NULL; 
17:   
18:            if (head == NULL) { 
19:                 head = node_isi; 
20:                 tail = node_isi; 
21:            } 
22:            else { 
23:                 tail->next = node_isi; 
24:                 tail = node_isi; 
25:            } 
26:   
27:       } 
28:   
29:       bool isEmpty() { 
30:            return head == NULL; 
31:       } 
32:  }; 
33:   
34:  struct queue { 
35:       node *head = NULL; 
36:       node *tail = NULL; 
37:   
38:       void enqueue(int n) { 
39:            node *node_isi = new node(); 
40:            node_isi->value = n; 
41:            node_isi->next = NULL; 
42:   
43:            if (head == NULL) { 
44:                 head = node_isi; 
45:                 tail = node_isi; 
46:            } 
47:            else { 
48:                 tail->next = node_isi; 
49:                 tail = node_isi; 
50:            } 
51:       } 
52:   
53:       int dequeue() { 
54:            node *buff = head; 
55:            head = head->next; 
56:            int result_dequeue = buff->value; 
57:            delete buff; 
58:            return result_dequeue; 
59:       } 
60:   
61:       bool isEmpty() { 
62:            return head == NULL; 
63:       } 
64:  }; 
65:   
66:  int result[5]; 
67:  int idxResult = 0; 
68:  void addToResult(int n) { 
69:       result[idxResult] = n; 
70:       idxResult++; 
71:  } 
72:  bool isInResult(int n) { 
73:       for (int i = 0; i < idxResult; i++) { 
74:            if (n == result[i]) return true; 
75:       } 
76:       return false; 
77:  } 
78:   
79:  int main() { 
80:   
81:       int n = 5; 
82:       int e = 7; 
83:       int v1[] = {1,1,2,2,2,3,4}; 
84:       int v2[] = {2,5,3,4,5,4,5}; 
85:       linkedList mat[5], buff; 
86:       queue antrian; 
87:   
88:       for (int i = 0; i < e; i++) { 
89:            mat[v1[i]-1].addList(v2[i]); 
90:            mat[v2[i]-1].addList(v1[i]); 
91:       } 
92:   
93:       cout << "Hasil adjacent list" << endl; 
94:       for (int i = 0; i < n; i++) {               //untuk cek isi adjacent list      
95:            buff = mat[i]; 
96:            cout << "List (" << i+1 << "): "; 
97:            while (!buff.isEmpty()) { 
98:                 cout << buff.head->value << " "; 
99:                 buff.head = buff.head->next; 
100:            } 
101:            cout << endl; 
102:       } 
103:   
104:       int firstque=0; 
105:       int parent; 
106:       antrian.enqueue(firstque); 
107:   
108:       while (!antrian.isEmpty()) { 
109:            parent = antrian.dequeue(); 
110:            if (!isInResult(parent)) { 
111:                 addToResult(parent); 
112:                 buff=mat[parent];
113:                 while (!buff.isEmpty()) { 
114:                      antrian.enqueue((buff.head->value)-1); 
115:                      buff.head = buff.head->next; 
116:                 } 
117:            } 
118:       } 
119:   
120:       cout << endl << "Hasil BFS" << endl; 
121:       for (int i = 0; i < n; i++) { 
122:            cout << result[i]+1 << " "; 
123:       } 
124:       cout << endl; 
125:   
126:       system("pause"); 
127:       return 0; 
128:  } 

Special thanks to Samsung Academy SRIN Lecturer:
1. Pak Risman Adnan Mattotorang
2. Mas Leonardi
3. Mas Gilang
4. Mas Susanto Tedja

Tes Algorithm

(note: late publish)

Tes Algorithm

Baik. Waktu pengerjaan 3 jam. Kalo gak salah ingat, kira-kira begini soalnya (kata-kata yang Saya gunakan tidak sama persis ya..):

Untuk mengetahui volume dari suatu danau, suatu perusahaan menggunakan data dari citra digital dua dimensi (2D). Dengan ukuran matriks (NxN).

Nilai "0" merepresentasikan tanah (land) dan nilai "1" merepresentasikan air (water). Volume (kedalaman) air pada suatu posisi tergantung posisi air tersebut terhadap tanah yang terdekat. Semakin jauh posisi air tersebut terhadap tanah berarti semakin dalam (volume semakin besar). Jika posisi air tepat disebelah tanah maka volumenya adalah 1, jika posisi air selisih satu piksel terhadap tanah maka volumenya 2, begitu seterusnya. Perhatikan bahwa posisi air terhadap tanah ditinjau dari arah utara, selatan, barat, timur (pada pembahasan ini Saya andaikan atas, bawah, kiri, kanan ---> dari representasi matriks 2D). Dan ingat dari ke empat arah tersebut kedalaman air ditentukan dari jarak yang "paling pendek" terhadap tanah.

oiya,, data digital (matriks 2D) dapat berisi lebih dari 1 danau, dan tepi-tepi dari matriks tersebut adalah tanah (0).

Input program:

-jumlah pengetesan matriks

-ukuran matriks N (ingat matriks berukuran NxN)

-nilai matriks

output program:

-"#[pengukuran ke] [volume]

contoh (ini agak lupa) hehe
input:
2                -->ket: jumlah pengetesan = 2
4                -->ket: ukuran matriks 4x4
0 0 0 0                -->ket: matriks 4x4
0 1 1 0
0 1 1 0                -->ket: perhatikan bahwa posisi air memiliki kedalaman yang sama yaitu 1, jadi total adalah 4x1=4
0 0 0 0
7                              -->ket: ukuran matriks 7x7
0 0 0 0 0 0 0            -->ket: matriks 7x7
0 0 0 1 0 0 0
0 0 0 1 0 0 0
0 1 1 1 1 1 0            -->ket: perhatikan bahwa air memiliki 8 posisi dengan kedalaman 1 dan 1 posisi dengan kedalaman 3
0 0 0 1 0 0 0                sehingga total adalah (8x1) + (1x3) = 11
0 0 0 1 0 0 0
0 0 0 0 0 0 0

output:
#1 4                  -->ket: hasil pengukuran matriks pertama
#2 11                -->ket: hasil pengukuran matriks kedua

Naaaahhh, ini adalah jawaban setelah Saya kerjakan dikosan hehe. Tes udah lewat eh kok malah dapat jawabannya. Alhamdulillah mudah-mudahan benar (paling tidak dari beberapa pengujian yang Saya coba hasilnya sesuai :p )... mungkin efek sudah kenyang hahaha.. halah ngelesss hahaha

Sebenernya alur codingnya sih hampir sama dengan saat Saya ngerjakan tadi saat tes. Bedanya disini sudah Saya bikin function terpisah dengan kode utama sehingga mudah untuk penelusuran kesalahan. Dan bedanya lagi di sini Saya ada menggunakan sintax "while" karena Saya lupa sintax caranya exit dari for.hahaha --> inilah yang membuat tadi pas tess bingung... huuuuuufttt.. Mudah mudahan tulisan ini bisa terupload kalo sdh larut malam.

#include <iostream>

using namespace std;
int matriks[100][100];
int T, N, volumeN, kedalaman_pertitik;
int fungsi_min(int a, int b, int c, int d);
int fungsi_cek(int j, int k);
int main()
{
    cin >> T;   //jumlah pengetesan matriks
    for(int i=0; i<T; i++){
    cin >> N;   //ukuran matriks
        for(int j=0; j<N; j++){
            for (int k=0; k<N; k++){
            cin >> matriks[j][k];
            }
        }
    volumeN=0;
    for(int j=1; j<(N-1); j++){
        for (int k=1; k<(N-1); k++){
            if (matriks[j][k]==1){
                kedalaman_pertitik=fungsi_cek(j,k);
                volumeN=volumeN+kedalaman_pertitik;
            }
        }
    }

    cout << "#"<< i+1 << " "<< volumeN << endl;
    }
return 0;
}


int fungsi_cek(int j, int k)
{
int kiri=1, kanan=1, atas=1, bawah=1;
int l,m;
//cek kiri
l=j;
m=k;
while(matriks[l-1][m]==1){
    kiri++;
    l--;
}

//cek kanan
l=j;
m=k;
while(matriks[l+1][m]==1){
    kanan++;
    l++;
}

//cek atas
l=j;
m=k;
while(matriks[l][m-1]==1){
    atas++;
    m--;
}

//cek bawah
l=j;
m=k;
while(matriks[l][m+1]==1){
    bawah++;
    m++;
}

return fungsi_min(kiri,kanan,atas,bawah);
}

int fungsi_min(int a, int b, int c, int d)
{
int nilai_min=a;

if(nilai_min>b) nilai_min=b;
if(nilai_min>c) nilai_min=c;
if(nilai_min>d) nilai_min=d;

return nilai_min;
}

Berikut adalah printscreen hasil runningnya

Attention: Code ini menggunakan compiler cpp (code::blocks under Ubuntu Linux 14.04)

##Code diatas belum tentu yang paling efisien, maklum hanya menuangkan isi kepala

Terimakasih. Semoga bermanfaat.

Salam berbagi..