Skip to content

Commit 47010c4

Browse files
TornjVTornjV
authored
Merge pull request algorithm-visualizer#218 from AdhityaRamadhanus/depth-limited-search
Depth-limited search
2 parents 9a1d26b + c278ed0 commit 47010c4

File tree

6 files changed

+80
-0
lines changed

6 files changed

+80
-0
lines changed

‎algorithm/category.json

+1
Original file line numberDiff line numberDiff line change
@@ -37,6 +37,7 @@
3737
"bfs": "BFS",
3838
"bridges": "Find-Bridges",
3939
"dfs": "DFS",
40+
"dls": "Depth-Limited Search",
4041
"dijkstra": "Dijkstra",
4142
"floyd_warshall": "Floyd-Warshall",
4243
"page_rank": "PageRank Algorithm",

‎algorithm/graph_search/dls/count_descendant/code.js

+17
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,17 @@
1+
// This is a sample DLS applications where
2+
// we try to find number of descendant of root within some depth
3+
function DLSCount (limit, node, parent) { // node = current node, parent = previous node
4+
tracer._visit(node, parent)._wait();
5+
var child = 0;
6+
if (limit>0) { // cut off the search
7+
for (var i = 0; i < G[node].length; i++) {
8+
if (G[node][i]) { // if current node has the i-th node as a child
9+
child += 1 + DLSCount(limit-1, i, node); // recursively call DLS
10+
}
11+
}
12+
return child;
13+
}else{
14+
return child;
15+
}
16+
}
17+
logger._print('Number of descendant is ' + DLSCount(2,0));

‎algorithm/graph_search/dls/count_descendant/data.js

+17
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,17 @@
1+
var tracer = new DirectedGraphTracer();
2+
var logger = new LogTracer();
3+
tracer.attach(logger);
4+
var G = [ // G[i][j] indicates whether the path from the i-th node to the j-th node exists or not
5+
[0, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0],
6+
[0, 0, 0, 1, 1, 0, 0, 0, 0, 0, 0],
7+
[0, 0, 0, 0, 0, 1, 1, 0, 0, 0, 0],
8+
[0, 0, 0, 0, 0, 0, 0, 1, 1, 0, 0],
9+
[0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 1],
10+
[0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
11+
[0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
12+
[0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
13+
[0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
14+
[0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
15+
[0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
16+
];
17+
tracer._setTreeData(G, 0);

‎algorithm/graph_search/dls/desc.json

+15
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,15 @@
1+
{
2+
"DLS": "Depth-Limited search (DLS) is an algorithm for traversing or searching tree or graph data structures. It's actually specific type of DFS where the search is limited to some depth from start node (root). One starts at the root (selecting some arbitrary node as the root in the case of a graph) and explores as far as possible (within some limit) along each branch before backtracking.",
3+
"Complexity": {
4+
"time": "worst $O(b^l)$",
5+
"space": "worst $O(bl)$",
6+
"notes" : "</br>b is branching factor, for example binary tree has branching factor 2 </br> l is limit that we define"
7+
},
8+
"References": [
9+
"<a href='http://www.cs.colostate.edu/~anderson/cs440/index.html/doku.php?id=notes:week2b'>Colorado State University Lecture Notes</a>"
10+
],
11+
"files": {
12+
"tree": "Searching a tree (limited depth)",
13+
"count_descendant": "Count all descendant of root within some depth"
14+
}
15+
}

‎algorithm/graph_search/dls/tree/code.js

+13
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,13 @@
1+
// This is a sample DLS where
2+
// we try to find number of descendant of root within some depth
3+
function DLS (limit, node, parent) { // node = current node, parent = previous node
4+
tracer._visit(node, parent)._wait();
5+
if (limit>0) { // cut off the search
6+
for (var i = 0; i < G[node].length; i++) {
7+
if (G[node][i]) { // if current node has the i-th node as a child
8+
DLS(limit-1, i, node); // recursively call DLS
9+
}
10+
}
11+
}
12+
}
13+
DLS(2,0);

‎algorithm/graph_search/dls/tree/data.js

+17
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,17 @@
1+
var tracer = new DirectedGraphTracer();
2+
var logger = new LogTracer();
3+
tracer.attach(logger);
4+
var G = [ // G[i][j] indicates whether the path from the i-th node to the j-th node exists or not
5+
[0, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0],
6+
[0, 0, 0, 1, 1, 0, 0, 0, 0, 0, 0],
7+
[0, 0, 0, 0, 0, 1, 1, 0, 0, 0, 0],
8+
[0, 0, 0, 0, 0, 0, 0, 1, 1, 0, 0],
9+
[0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 1],
10+
[0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
11+
[0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
12+
[0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
13+
[0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
14+
[0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
15+
[0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
16+
];
17+
tracer._setTreeData(G, 0);

0 commit comments

Comments
 (0)