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

Commitcb9c29e

Browse files
authored
Merge pull request#1 from TheAlgorithms/master
update fork
2 parents4bc2b28 +33549a3 commitcb9c29e

File tree

3 files changed

+154
-0
lines changed

3 files changed

+154
-0
lines changed

‎DIRECTORY.md

Lines changed: 2 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -74,6 +74,8 @@
7474
*[ZeroOneKnapsack](https://github.com/TheAlgorithms/Javascript/blob/master/Dynamic-Programming/ZeroOneKnapsack.js)
7575

7676
##Graphs
77+
*[BreadthFirstSearch](https://github.com/TheAlgorithms/Javascript/blob/master/Graphs/BreadthFirstSearch.js)
78+
*[BreadthFirstShortestPath](https://github.com/TheAlgorithms/Javascript/blob/master/Graphs/BreadthFirstShortestPath.js)
7779
*[ConnectedComponents](https://github.com/TheAlgorithms/Javascript/blob/master/Graphs/ConnectedComponents.js)
7880
*[Density](https://github.com/TheAlgorithms/Javascript/blob/master/Graphs/Density.js)
7981
*[DepthFirstSearchIterative](https://github.com/TheAlgorithms/Javascript/blob/master/Graphs/DepthFirstSearchIterative.js)

‎Graphs/BreadthFirstSearch.js

Lines changed: 64 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,64 @@
1+
/*
2+
Breadth-first search is an algorithm for traversing a graph. It's discovers all nodes reachable from the starting position by exploring all of the neighbor nodes at the present depth prior to moving on to the nodes at the next depth level.
3+
(description adapted from https://en.wikipedia.org/wiki/Breadth-first_search )
4+
(see also: https://www.koderdojo.com/blog/breadth-first-search-and-shortest-path-in-csharp-and-net-core )
5+
*/
6+
7+
/*
8+
Doctests
9+
> Array.from(breadthFirstSearch(graph, "C"))
10+
[ 'C', 'D', 'A', 'B', 'E' ]
11+
> Array.from(breadthFirstSearch(graph, "A"))
12+
[ 'A', 'B', 'D', 'E' ]
13+
> Array.from(breadthFirstSearch(graph, "F"))
14+
[ 'F', 'G' ]
15+
*/
16+
17+
functionbreadthFirstSearch(graph,startingNode){
18+
// visited keeps track of all nodes visited
19+
constvisited=newSet()
20+
21+
// queue contains the nodes to be explored in the future
22+
constqueue=[startingNode]
23+
24+
while(queue.length>0){
25+
// start with the queue's first node
26+
constnode=queue.shift()
27+
28+
if(!visited.has(node)){
29+
// mark the node as visited
30+
visited.add(node)
31+
constneighbors=graph[node]
32+
33+
// put all its neighbors into the queue
34+
for(leti=0;i<neighbors.length;i++){
35+
queue.push(neighbors[i])
36+
}
37+
}
38+
}
39+
40+
returnvisited
41+
}
42+
43+
constgraph={
44+
A:['B','D'],
45+
B:['E'],
46+
C:['D'],
47+
D:['A'],
48+
E:['D'],
49+
F:['G'],
50+
G:[]
51+
}
52+
/*
53+
A <-> B
54+
ʌ |
55+
| |
56+
v v
57+
C --> D <-- E
58+
59+
F --> G
60+
*/
61+
62+
console.log(breadthFirstSearch(graph,'C'))
63+
console.log(breadthFirstSearch(graph,'A'))
64+
console.log(breadthFirstSearch(graph,'F'))

‎Graphs/BreadthFirstShortestPath.js

Lines changed: 88 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,88 @@
1+
/*
2+
Breadth-first approach can be applied to determine the shortest path between two nodes
3+
in an equi-weighted graph. It searches the target node among all neighbors of the
4+
starting node, then the process is repeated on the level of the neighbors of the
5+
neighbors and so on.
6+
(See also: https://en.wikipedia.org/wiki/Breadth-first_search )
7+
(see also: https://www.koderdojo.com/blog/breadth-first-search-and-shortest-path-in-csharp-and-net-core )
8+
*/
9+
10+
/*
11+
Doctests
12+
> breadthFirstShortestPath(graph, 'C', 'E')
13+
[ 'C', 'D', 'A', 'B', 'E' ]
14+
> breadthFirstShortestPath(graph, 'E', 'B')
15+
[ 'E', 'D', 'A', 'B' ]
16+
> breadthFirstShortestPath(graph, 'F', 'G')
17+
[ 'F', 'G' ]
18+
> breadthFirstShortestPath(graph, 'A', 'G')
19+
[]
20+
*/
21+
22+
functionbreadthFirstShortestPath(graph,startNode,targetNode){
23+
// check if startNode & targetNode are identical
24+
if(startNode===targetNode){
25+
return[startNode]
26+
}
27+
28+
// visited keeps track of all nodes visited
29+
constvisited=newSet()
30+
31+
// queue contains the paths to be explored in the future
32+
constinitialPath=[startNode]
33+
constqueue=[initialPath]
34+
35+
while(queue.length>0){
36+
// start with the queue's first path
37+
constpath=queue.shift()
38+
constnode=path[path.length-1]
39+
40+
// explore this node if it hasn't been visited yet
41+
if(!visited.has(node)){
42+
// mark the node as visited
43+
visited.add(node)
44+
45+
constneighbors=graph[node]
46+
47+
// create a new path in the queue for each neighbor
48+
for(leti=0;i<neighbors.length;i++){
49+
constnewPath=path.concat([neighbors[i]])
50+
51+
// the first path to contain the target node is the shortest path
52+
if(neighbors[i]===targetNode){
53+
returnnewPath
54+
}
55+
56+
// queue the new path
57+
queue.push(newPath)
58+
}
59+
}
60+
}
61+
62+
// the target node was not reachable
63+
return[]
64+
}
65+
66+
constgraph={
67+
A:['B','D'],
68+
B:['E'],
69+
C:['D'],
70+
D:['A'],
71+
E:['D'],
72+
F:['G'],
73+
G:[]
74+
}
75+
/*
76+
A <-> B
77+
ʌ |
78+
| |
79+
v v
80+
C --> D <-- E
81+
82+
F --> G
83+
*/
84+
85+
console.log(breadthFirstShortestPath(graph,'C','E'))
86+
console.log(breadthFirstShortestPath(graph,'E','B'))
87+
console.log(breadthFirstShortestPath(graph,'F','G'))
88+
console.log(breadthFirstShortestPath(graph,'A','G'))

0 commit comments

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