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