Created
October 8, 2019 06:49
-
-
Save kingsleytan/8a687ccc93f1c3cb3d7ccf13b865b352 to your computer and use it in GitHub Desktop.
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
function bfs(graph, root) { | |
var nodesLen = {}; | |
for (var i = 0; i < graph.length; i++) { | |
nodesLen[i] = Infinity; | |
} | |
nodesLen[root] = 0; | |
var queue = [root]; | |
var current; | |
while (queue.length != 0) { | |
current = queue.shift(); | |
var curConnected = graph[current]; | |
var neighborIdx = []; | |
var idx = curConnected.indexOf(1); | |
while (idx != -1) { | |
neighborIdx.push(idx); | |
idx = curConnected.indexOf(1, idx + 1); | |
} | |
for (var j = 0; j < neighborIdx.length; j++) { | |
if (nodesLen[neighborIdx[j]] == Infinity) { | |
nodesLen[neighborIdx[j]] = nodesLen[current] + 1; | |
queue.push(neighborIdx[j]); | |
} | |
} | |
} | |
return nodesLen; | |
} |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment