1 function Stack() {
2 var items = [];
3 this.push = function(item) {
4 items.push(item)
5 }
6 this.pop = function() {
7 return items.pop()
8 }
9 this.peek = function() {
10 return items[items.length - 1]
11 }
12 this.isEmpty = function() {
13 return items.length == 0
14 }
15 this.size = function() {
16 return items.length
17 }
18 this.clear = function() {
19 items = []
20 }
21 this.printf = function() {
22 console.log(items.toString())
23 }
24 this.divideBy2 = function(decNumber) {
25 var remStack = new Stack(),
26 rem,
27 binaryString = '';
28 while (decNumber > 0) {
29 rem = Math.floor(decNumber % 2);
30 remStack.push(rem);
31 decNumber = Math.floor(decNumber / 2)
32 }
33 while (!remStack.isEmpty()) {
34 binaryString += remStack.pop().toString()
35 }
36 return binaryString
37 }
38 }
39
40 function Queue() {
41 var items = [];
42 this.enqueue = function(element) {
43 items.push(element)
44 }
45 this.dequeue = function(element) {
46 return items.shift();
47 }
48 this.front = function() {
49 return items[0]
50 }
51 this.isEmpty = function() {
52 return items.length == 0
53 }
54 this.size = function() {
55 return items.length
56 }
57 this.printf = function() {
58 console.log(items.toString())
59 }
60 this.print = function() {
61 console.log(items.toString())
62 }
63 }
64
65
66 function Dictionary() {
67 var items = {};
68 this.has = function(key) {
69 return key in items
70 }
71 this.set = function(key, value) {
72 items[key] = value
73 }
74 this.remove = function(key) {
75 if (this.has(key)) {
76 delete items[key];
77 return true
78 }
79 return false
80 }
81 this.get = function(key) {
82 return this.has(key) ? items[key] : undefined
83 }
84 this.values = function() {
85 var values = [];
86 for (var key in items) {
87 if (this.has(key)) {
88 values.push(items[key])
89 }
90 }
91 return values
92 }
93 this.getItems = function() {
94 return items
95 }
96 this.size = function() {
97 return Object.keys(items).length
98 }
99 this.clear = function() {
100 this.items = {}
101 }
102 this.keys = function() {
103 return Object.keys(items)
104 }
105 }
106
107 function Graph() {
108 var vertices = [];
109 var adjList = new Dictionary();
110 this.addVertex = function(v) {
111 vertices.push(v);
112 adjList.set(v, []);
113 }
114 this.addEdge = function(v, w) {
115 adjList.get(v).push(w);
116 adjList.get(w).push(v);
117 }
118 this.toString = function() {
119 var s = '';
120 for (var i = vertices.length - 1; i >= 0; i--) {
121 s += vertices[i] + '->';
122 var neighbors = adjList.get(vertices[i]);
123 for (var j = neighbors.length - 1; j >= 0; j--) {
124 s += neighbors[j] + '';
125 };
126 s += ' ';
127 };
128 return s;
129 }
130
131 this.bfs = function(v, callback) {
132 var color = initializeColor(),
133 queue = new Queue();
134 queue.enqueue(v);
135 while (!queue.isEmpty()) {
136 var u = queue.dequeue(),
137 neighbors = adjList.get(u);
138 color[u] = 'grey';
139 for (var i = 0; i < neighbors.length; i++) {
140 var w = neighbors[i];
141 if (color[w] === 'white') {
142 color[w] = 'grey';
143 queue.enqueue(w);
144 }
145 };
146 color[u] = 'black';
147 if (callback) {
148 callback(u);
149 }
150 }
151 }
152
153 this.shortBFS = function(v) {
154 var color = initializeColor(),
155 queue = new Queue(),
156 d = [],
157 pred = [];
158 queue.enqueue(v);
159 for (var i = 0; i < vertices.length; i++) {
160 d[vertices[i]] = 0;
161 pred[vertices[i]] = null;
162 }
163 while (!queue.isEmpty()) {
164 var u = queue.dequeue(),
165 neighbors = adjList.get(u);
166 color[u] = 'gery';
167 for (var i = 0; i < neighbors.length; i++) {
168 var w = neighbors[i];
169 if (color[w] === 'white') {
170 color[w] = 'gery';
171 d[w] = d[u] + 1;
172 pred[w] = u;
173 queue.enqueue(w);
174 }
175 }
176 color[u] = 'black';
177 }
178 return {
179 distances: d,
180 predecessors: pred
181 }
182 }
183
184 this.dfs = function(callback) {
185 var color = initializeColor();
186 for (var i = 0; i < vertices.length; i++) {
187 if (color[vertices[i]] === 'white') {
188 dfsVisit(vertices[i], color, callback);
189 }
190 }
191 }
192
193
194 var dfsVisit = function(u, color, callback) {
195 color[u] = 'gery';
196 if (callback) {
197 callback(u);
198 }
199 var neighbors = adjList.get(u);
200 for (var i = 0; i < neighbors.length; i++) {
201 var w = neighbors[i];
202 if (color[w] === 'white') {
203 dfsVisit(w, color, callback);
204 }
205 }
206 color[u] = 'black';
207 }
208
209
210
211 var time = 0;
212 this.DFS = function() {
213 var color = initializeColor(),
214 d = [],
215 f = [],
216 p = [];
217 time = 0;
218 for (var i = 0; i < vertices.length; i++) {
219 f[vertices[i]] = 0;
220 d[vertices[i]] = 0;
221 p[vertices[i]] = null;
222
223 }
224 for (i = 0; i < vertices.length; i++) {
225 if (color[vertices[i]] === 'white') {
226 DFSVisit(vertices[i], color, d, f, p);
227 }
228 }
229 return {
230 discovery: d,
231 finished: f,
232 predecsssors: p
233 }
234 }
235 var DFSVisit = function(u, color, d, f, p) {
236 console.log('discoverd ' + u);
237 color[u] = 'gery';
238 d[u] = ++time;
239 var neighbors = adjList.get(u);
240 for (var i = 0; i < neighbors.length; i++) {
241 var w = neighbors[i];
242 if (color[w] === 'white') {
243 p[w] = u;
244 DFSVisit(w, color, d, f, p);
245
246 }
247 }
248 color[u] = 'black';
249 f[u] = ++time;
250 console.log('explored ' + u);
251 }
252
253 }
254 var graph = new Graph();
255 var myVertices = ['A', 'B', 'C', 'D', 'E', 'F', 'G', 'H', 'H', 'I'];
256 for (var i = 0, length1 = myVertices.length; i < length1; i++) {
257 graph.addVertex(myVertices[i]);
258 }
259 graph.addEdge('A', 'B');
260 graph.addEdge('A', 'C');
261 graph.addEdge('A', 'D');
262 graph.addEdge('C', 'D');
263 graph.addEdge('C', 'G');
264 graph.addEdge('D', 'G');
265 graph.addEdge('D', 'H');
266 graph.addEdge('B', 'E');
267 graph.addEdge('B', 'F');
268 graph.addEdge('E', 'I');
269
270
271 console.log(graph.toString());
272
273 var initializeColor = function() {
274 var color = [];
275 for (var i = 0; i < myVertices.length; i++) {
276 color[myVertices[i]] = 'white';
277 };
278 return color;
279 };
280
281 function printNode(value) {
282 console.log("VIsited vertex:" + value);
283 }
284 console.log('---------------')
285 graph.bfs(myVertices[0], printNode);
286 console.log('---------------')
287 var shortestPathA = graph.shortBFS(myVertices[0]);
288 console.log(shortestPathA);
289 console.log('---------------')
290
291 var fromVertex = myVertices[0];
292 for (var i = 0; i < myVertices.length; i++) {
293 var toVertex = myVertices[i],
294 path = new Stack();
295 for (var v = toVertex; v !== fromVertex; v = shortestPathA.predecessors[v]) {
296 path.push(v);
297 }
298 path.push(fromVertex);
299 var s = path.pop();
300 while (!path.isEmpty()) {
301 s += '-' + path.pop();
302 }
303 console.log(s);
304 }
305
306 console.log('---------------')
307
308 graph.dfs(printNode);
309
310 console.log('---------------')
311 graph.DFS();
2 var items = [];
3 this.push = function(item) {
4 items.push(item)
5 }
6 this.pop = function() {
7 return items.pop()
8 }
9 this.peek = function() {
10 return items[items.length - 1]
11 }
12 this.isEmpty = function() {
13 return items.length == 0
14 }
15 this.size = function() {
16 return items.length
17 }
18 this.clear = function() {
19 items = []
20 }
21 this.printf = function() {
22 console.log(items.toString())
23 }
24 this.divideBy2 = function(decNumber) {
25 var remStack = new Stack(),
26 rem,
27 binaryString = '';
28 while (decNumber > 0) {
29 rem = Math.floor(decNumber % 2);
30 remStack.push(rem);
31 decNumber = Math.floor(decNumber / 2)
32 }
33 while (!remStack.isEmpty()) {
34 binaryString += remStack.pop().toString()
35 }
36 return binaryString
37 }
38 }
39
40 function Queue() {
41 var items = [];
42 this.enqueue = function(element) {
43 items.push(element)
44 }
45 this.dequeue = function(element) {
46 return items.shift();
47 }
48 this.front = function() {
49 return items[0]
50 }
51 this.isEmpty = function() {
52 return items.length == 0
53 }
54 this.size = function() {
55 return items.length
56 }
57 this.printf = function() {
58 console.log(items.toString())
59 }
60 this.print = function() {
61 console.log(items.toString())
62 }
63 }
64
65
66 function Dictionary() {
67 var items = {};
68 this.has = function(key) {
69 return key in items
70 }
71 this.set = function(key, value) {
72 items[key] = value
73 }
74 this.remove = function(key) {
75 if (this.has(key)) {
76 delete items[key];
77 return true
78 }
79 return false
80 }
81 this.get = function(key) {
82 return this.has(key) ? items[key] : undefined
83 }
84 this.values = function() {
85 var values = [];
86 for (var key in items) {
87 if (this.has(key)) {
88 values.push(items[key])
89 }
90 }
91 return values
92 }
93 this.getItems = function() {
94 return items
95 }
96 this.size = function() {
97 return Object.keys(items).length
98 }
99 this.clear = function() {
100 this.items = {}
101 }
102 this.keys = function() {
103 return Object.keys(items)
104 }
105 }
106
107 function Graph() {
108 var vertices = [];
109 var adjList = new Dictionary();
110 this.addVertex = function(v) {
111 vertices.push(v);
112 adjList.set(v, []);
113 }
114 this.addEdge = function(v, w) {
115 adjList.get(v).push(w);
116 adjList.get(w).push(v);
117 }
118 this.toString = function() {
119 var s = '';
120 for (var i = vertices.length - 1; i >= 0; i--) {
121 s += vertices[i] + '->';
122 var neighbors = adjList.get(vertices[i]);
123 for (var j = neighbors.length - 1; j >= 0; j--) {
124 s += neighbors[j] + '';
125 };
126 s += ' ';
127 };
128 return s;
129 }
130
131 this.bfs = function(v, callback) {
132 var color = initializeColor(),
133 queue = new Queue();
134 queue.enqueue(v);
135 while (!queue.isEmpty()) {
136 var u = queue.dequeue(),
137 neighbors = adjList.get(u);
138 color[u] = 'grey';
139 for (var i = 0; i < neighbors.length; i++) {
140 var w = neighbors[i];
141 if (color[w] === 'white') {
142 color[w] = 'grey';
143 queue.enqueue(w);
144 }
145 };
146 color[u] = 'black';
147 if (callback) {
148 callback(u);
149 }
150 }
151 }
152
153 this.shortBFS = function(v) {
154 var color = initializeColor(),
155 queue = new Queue(),
156 d = [],
157 pred = [];
158 queue.enqueue(v);
159 for (var i = 0; i < vertices.length; i++) {
160 d[vertices[i]] = 0;
161 pred[vertices[i]] = null;
162 }
163 while (!queue.isEmpty()) {
164 var u = queue.dequeue(),
165 neighbors = adjList.get(u);
166 color[u] = 'gery';
167 for (var i = 0; i < neighbors.length; i++) {
168 var w = neighbors[i];
169 if (color[w] === 'white') {
170 color[w] = 'gery';
171 d[w] = d[u] + 1;
172 pred[w] = u;
173 queue.enqueue(w);
174 }
175 }
176 color[u] = 'black';
177 }
178 return {
179 distances: d,
180 predecessors: pred
181 }
182 }
183
184 this.dfs = function(callback) {
185 var color = initializeColor();
186 for (var i = 0; i < vertices.length; i++) {
187 if (color[vertices[i]] === 'white') {
188 dfsVisit(vertices[i], color, callback);
189 }
190 }
191 }
192
193
194 var dfsVisit = function(u, color, callback) {
195 color[u] = 'gery';
196 if (callback) {
197 callback(u);
198 }
199 var neighbors = adjList.get(u);
200 for (var i = 0; i < neighbors.length; i++) {
201 var w = neighbors[i];
202 if (color[w] === 'white') {
203 dfsVisit(w, color, callback);
204 }
205 }
206 color[u] = 'black';
207 }
208
209
210
211 var time = 0;
212 this.DFS = function() {
213 var color = initializeColor(),
214 d = [],
215 f = [],
216 p = [];
217 time = 0;
218 for (var i = 0; i < vertices.length; i++) {
219 f[vertices[i]] = 0;
220 d[vertices[i]] = 0;
221 p[vertices[i]] = null;
222
223 }
224 for (i = 0; i < vertices.length; i++) {
225 if (color[vertices[i]] === 'white') {
226 DFSVisit(vertices[i], color, d, f, p);
227 }
228 }
229 return {
230 discovery: d,
231 finished: f,
232 predecsssors: p
233 }
234 }
235 var DFSVisit = function(u, color, d, f, p) {
236 console.log('discoverd ' + u);
237 color[u] = 'gery';
238 d[u] = ++time;
239 var neighbors = adjList.get(u);
240 for (var i = 0; i < neighbors.length; i++) {
241 var w = neighbors[i];
242 if (color[w] === 'white') {
243 p[w] = u;
244 DFSVisit(w, color, d, f, p);
245
246 }
247 }
248 color[u] = 'black';
249 f[u] = ++time;
250 console.log('explored ' + u);
251 }
252
253 }
254 var graph = new Graph();
255 var myVertices = ['A', 'B', 'C', 'D', 'E', 'F', 'G', 'H', 'H', 'I'];
256 for (var i = 0, length1 = myVertices.length; i < length1; i++) {
257 graph.addVertex(myVertices[i]);
258 }
259 graph.addEdge('A', 'B');
260 graph.addEdge('A', 'C');
261 graph.addEdge('A', 'D');
262 graph.addEdge('C', 'D');
263 graph.addEdge('C', 'G');
264 graph.addEdge('D', 'G');
265 graph.addEdge('D', 'H');
266 graph.addEdge('B', 'E');
267 graph.addEdge('B', 'F');
268 graph.addEdge('E', 'I');
269
270
271 console.log(graph.toString());
272
273 var initializeColor = function() {
274 var color = [];
275 for (var i = 0; i < myVertices.length; i++) {
276 color[myVertices[i]] = 'white';
277 };
278 return color;
279 };
280
281 function printNode(value) {
282 console.log("VIsited vertex:" + value);
283 }
284 console.log('---------------')
285 graph.bfs(myVertices[0], printNode);
286 console.log('---------------')
287 var shortestPathA = graph.shortBFS(myVertices[0]);
288 console.log(shortestPathA);
289 console.log('---------------')
290
291 var fromVertex = myVertices[0];
292 for (var i = 0; i < myVertices.length; i++) {
293 var toVertex = myVertices[i],
294 path = new Stack();
295 for (var v = toVertex; v !== fromVertex; v = shortestPathA.predecessors[v]) {
296 path.push(v);
297 }
298 path.push(fromVertex);
299 var s = path.pop();
300 while (!path.isEmpty()) {
301 s += '-' + path.pop();
302 }
303 console.log(s);
304 }
305
306 console.log('---------------')
307
308 graph.dfs(printNode);
309
310 console.log('---------------')
311 graph.DFS();