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