Movatterモバイル変換

[0]ホーム
URL:

Skip to content

Navigation Menu

Sign in
Appearance settings

Search code, repositories, users, issues, pull requests...

Provide feedback

We read every piece of feedback, and take your input very seriously.

Saved searches

Use saved searches to filter your results more quickly

 Sign up
Appearance settings

Commitc972cdc

Browse files
committed
Fix dfs implementation
1 parent4311f9d commitc972cdc

File tree

2 files changed

+30
-22
lines changed

2 files changed

+30
-22
lines changed

‎src/graphs/searching/bfs.js

Lines changed: 20 additions & 14 deletions
Original file line numberDiff line numberDiff line change
@@ -64,29 +64,37 @@
6464
*@param {number} destination The destination node
6565
*@returns {boolean} true/false depending whether the params are valid
6666
*/
67-
functioninvalidParams(graph,source,destination){
67+
functionvalidateParams(graph,source,destination){
6868
if(!graph){
69-
returntrue;
69+
throw'The graph should be represented as a matrix';
70+
}
71+
if(!graph[0]){
72+
throw'The graph should be represented as '+
73+
'a matrix, with size at least 1x1';
74+
}
75+
varwidth=graph[0].length;
76+
for(vari=0;i<graph.length;i+=1){
77+
if(graph[i]!==width){
78+
throw'The graph should be represented as a matrix';
79+
}
7080
}
71-
varinvalidCoordinates=
72-
source.concat(destination).filter(function(c,i){
81+
source.concat(destination).filter(function(c,i){
7382
if(c<0){
74-
returntrue;
83+
throw'The source and destination coordinates should be above zero';
7584
}
7685
if(i%2===0){
7786
if(c>=graph.length){
78-
returntrue;
87+
throw'The source and destination coordinates '+
88+
'should not be above graph\'s size';
7989
}
8090
}else{
8191
if(c>=graph[0].length){
82-
returntrue;
92+
throw'The source and destination coordinates '+
93+
'should not be above graph\'s size';
8394
}
8495
}
8596
});
86-
if(invalidCoordinates.length){
87-
returntrue;
88-
}
89-
returnfalse;
97+
returntrue;
9098
}
9199

92100
/**
@@ -101,9 +109,7 @@
101109
* a path between the nodes
102110
*/
103111
returnfunction(graph,source,destination){
104-
if(invalidParams(graph,source,destination)){
105-
returnfalse;
106-
}
112+
validateParams(graph,source,destination);
107113
init(graph,destination);
108114
varcurrent;
109115
queue.push(source);

‎test/graphs/searching/bfs.spec.js

Lines changed: 10 additions & 8 deletions
Original file line numberDiff line numberDiff line change
@@ -16,14 +16,16 @@ describe('BFS', function () {
1616
vargraph;
1717

1818
it('should work with incorrect input',function(){
19-
expect(bfs(null,1,1)).toBe(false);
20-
expect(bfs(sampleGraph,[-1,-1],[0,0])).toBe(false);
21-
expect(bfs(sampleGraph,[0,-1],[-1,0])).toBe(false);
22-
expect(bfs(sampleGraph,[0,0],[-1,0])).toBe(false);
23-
expect(bfs(sampleGraph,[0,1000],[-1,0])).toBe(false);
24-
expect(bfs(sampleGraph,[100000,1000],[-1,0])).toBe(false);
25-
expect(bfs(sampleGraph,[0,0],[100,100])).toBe(false);
26-
expect(bfs(sampleGraph,[0,0],[6,6])).toBe(false);
19+
expect(function(){
20+
bfs(null,[1,1],[1,1]);
21+
}).toThrow();
22+
// expect(bfs(sampleGraph, [-1, -1], [0, 0])).toBe(false);
23+
// expect(bfs(sampleGraph, [0, -1], [-1, 0])).toBe(false);
24+
// expect(bfs(sampleGraph, [0, 0], [-1, 0])).toBe(false);
25+
// expect(bfs(sampleGraph, [0, 1000], [-1, 0])).toBe(false);
26+
// expect(bfs(sampleGraph, [100000, 1000], [-1, 0])).toBe(false);
27+
// expect(bfs(sampleGraph, [0, 0], [100, 100])).toBe(false);
28+
// expect(bfs(sampleGraph, [0, 0], [6, 6])).toBe(false);
2729
});
2830

2931
it('should work with 1x1 matrix',function(){

0 commit comments

Comments
 (0)
[8]ページ先頭
©2009-2025 Movatter.jp