Skip to content

Commit f850a5d

Browse files
mgechevmgechev
committed
Export dfs
1 parent 6b58ab3 commit f850a5d

1 file changed

Lines changed: 101 additions & 96 deletions

File tree

‎src/graphs/searching/dfs.js‎

Lines changed: 101 additions & 96 deletions
Original file line numberDiff line numberDiff line change
@@ -12,113 +12,118 @@ var graph = [[1,0,1,0,0,0],
1212
[0,0,0,0,1,1]];
1313
* * * * * * * * * * * * * * * * * */
1414

15-
/**
16-
* Depth-first search algorithm for matrix representation of graph.
17-
* The algorithm finds whether there's a path between two given nodes.
18-
*/
19-
var depthFirstSearch = (function () {
20-
21-
var visited = [],
22-
target,
23-
graph;
24-
15+
(function (exports) {
2516
/**
26-
* Returns whether the destination could be reached
27-
* from given node
28-
*
29-
* @private
30-
* @param {number} current Current node
31-
* @returns {boolean} True/false depending whether
32-
* the destination can be reached from the current node
17+
* Depth-first search algorithm for matrix representation of graph.
18+
* The algorithm finds whether there's a path between two given nodes.
3319
*/
34-
function dfs(current) {
35-
if (visited[current] ||
36-
current[0] < 0 || current[1] < 0 ||
37-
current[0] >= graph.length || current[1] >= graph[0].length ||
38-
!graph[current[0]][current[1]]) {
39-
return;
40-
}
41-
if (current[0] === target[0] &&
42-
current[1] === target[1]) {
43-
return true;
44-
}
45-
visited[current] = true;
46-
dfs([current[0] + 1, current[1]]);
47-
dfs([current[0] - 1, current[1]]);
48-
dfs([current[0], current[1] + 1]);
49-
dfs([current[0], current[1] - 1]);
50-
return false;
51-
}
20+
var depthFirstSearch = (function () {
5221

53-
/**
54-
* Initializes the algorithm
55-
*
56-
* @private
57-
* @param {array} inputGraph The input matrix of the graph
58-
* @param {number} destination The destination
59-
*/
60-
function init(inputGraph, destination) {
61-
graph = inputGraph;
62-
target = destination;
63-
visited = {};
64-
}
22+
var visited = [],
23+
target,
24+
graph;
6525

66-
/**
67-
* Validates the params
68-
*
69-
* @param {array} graph A matrix representation of the graph
70-
* @param {array} source The source node
71-
* @param {array} destination The destination node
72-
*/
73-
function validateParams(graph, source, destination) {
74-
if (!graph) {
75-
throw new Error('The graph should be represented as a matrix');
26+
/**
27+
* Returns whether the destination could be reached
28+
* from given node
29+
*
30+
* @private
31+
* @param {number} current Current node
32+
* @returns {boolean} True/false depending whether
33+
* the destination can be reached from the current node
34+
*/
35+
function dfs(current) {
36+
if (visited[current] ||
37+
current[0] < 0 || current[1] < 0 ||
38+
current[0] >= graph.length || current[1] >= graph[0].length ||
39+
!graph[current[0]][current[1]]) {
40+
return false;
41+
}
42+
if (current[0] === target[0] &&
43+
current[1] === target[1]) {
44+
return true;
45+
}
46+
visited[current] = true;
47+
return dfs([current[0] + 1, current[1]]) ||
48+
dfs([current[0] - 1, current[1]]) ||
49+
dfs([current[0], current[1] + 1]) ||
50+
dfs([current[0], current[1] - 1]);
7651
}
77-
if (graph[0] === undefined) {
78-
throw new Error('The graph should be represented as ' +
79-
'a matrix, with size at least 1x1');
52+
53+
/**
54+
* Initializes the algorithm
55+
*
56+
* @private
57+
* @param {array} inputGraph The input matrix of the graph
58+
* @param {number} destination The destination
59+
*/
60+
function init(inputGraph, destination) {
61+
graph = inputGraph;
62+
target = destination;
63+
visited = {};
8064
}
81-
var width = graph[0].length;
82-
for (var i = 1; i < graph.length; i += 1) {
83-
if (graph[i].length !== width) {
65+
66+
/**
67+
* Validates the params
68+
*
69+
* @param {array} graph A matrix representation of the graph
70+
* @param {array} source The source node
71+
* @param {array} destination The destination node
72+
*/
73+
function validateParams(graph, source, destination) {
74+
if (!graph) {
8475
throw new Error('The graph should be represented as a matrix');
8576
}
86-
}
87-
source.concat(destination).filter(function (c, i) {
88-
if (c < 0) {
89-
throw new Error('The source and destination coordinates ' +
90-
'should be above zero');
77+
if (graph[0] === undefined) {
78+
throw new Error('The graph should be represented as ' +
79+
'a matrix, with size at least 1x1');
9180
}
92-
if (i % 2 === 0) {
93-
if (c >= graph.length) {
94-
throw new Error('The source and destination coordinates ' +
95-
'should not be above graph\'s size');
81+
var width = graph[0].length;
82+
for (var i = 1; i < graph.length; i += 1) {
83+
if (graph[i].length !== width) {
84+
throw new Error('The graph should be represented as a matrix');
9685
}
97-
} else {
98-
if (c >= graph[0].length) {
86+
}
87+
source.concat(destination).filter(function (c, i) {
88+
if (c < 0) {
9989
throw new Error('The source and destination coordinates ' +
100-
'should not be above graph\'s size');
90+
'should be above zero');
10191
}
102-
}
103-
});
104-
return true;
105-
}
92+
if (i % 2 === 0) {
93+
if (c >= graph.length) {
94+
throw new Error('The source and destination coordinates ' +
95+
'should not be above graph\'s size');
96+
}
97+
} else {
98+
if (c >= graph[0].length) {
99+
throw new Error('The source and destination coordinates ' +
100+
'should not be above graph\'s size');
101+
}
102+
}
103+
});
104+
return true;
105+
}
106106

107-
/**
108-
* Finds whether there's a path between a given start node
109-
* to given destination
110-
*
111-
* @public
112-
* @param {array} graph A matrix representation of the graph
113-
* @param {number} source The source node
114-
* @param {number} destination The destination node
115-
* @returns {boolean} true/false depending
116-
* whether there's a path between the nodes
117-
*/
118-
return function (graph, source, destination) {
119-
validateParams(graph, source, destination);
120-
init(graph, destination);
121-
return dfs(source);
122-
};
107+
/**
108+
* Finds whether there's a path between a given start node
109+
* to given destination
110+
*
111+
* @public
112+
* @param {array} graph A matrix representation of the graph
113+
* @param {number} source The source node
114+
* @param {number} destination The destination node
115+
* @returns {boolean} true/false depending
116+
* whether there's a path between the nodes
117+
*/
118+
return function (graph, source, destination) {
119+
validateParams(graph, source, destination);
120+
init(graph, destination);
121+
return dfs(source);
122+
};
123+
124+
125+
}());
126+
127+
exports.depthFirstSearch = depthFirstSearch;
123128

124-
}());
129+
}(typeof exports === 'undefined' ? window : exports));

0 commit comments

Comments
 (0)