Find if a node is reachable using BFS
.everyoneloves__top-leaderboard:empty,.everyoneloves__mid-leaderboard:empty,.everyoneloves__bot-mid-leaderboard:empty{ height:90px;width:728px;box-sizing:border-box;
}
I am using BFS to check if a node is reachable and for printing the route.
Can anyone explain why BFS is preferred over DFS in this case?
Using below code:
LinkedList<String> queue = new LinkedList<String>();
HashSet<String> visitedNodes = new LinkedHashSet<String> ();
queue.add(source);
visitedNodes.add(source);
while (!queue.isEmpty()) {
String focusNode = queue.poll();
Set<Node> nodeSet = inputMap.getAllOutgoingNodes(focusNode);
if (null != nodeSet) {
for (Node s: nodeSet) {
if (!visitedNodes.contains(s.edge1)) {
visitedNodes.add(s.edge1);
queue.add(s.edge1);
if (destination.equals(s.edge1)) {
for (String sn: visitedNodes) {
System.out.print(sn);
break;
}
}
}
}
}
graph-theory breadth-first-search
edited Nov 16 '18 at 19:34
Dominique Fortin
1,665817
asked Mar 31 '18 at 12:07
Apoorva SharmaApoorva Sharma
82
add a comment |
I am using BFS to check if a node is reachable and for printing the route.
Can anyone explain why BFS is preferred over DFS in this case?
Using below code:
LinkedList<String> queue = new LinkedList<String>();
HashSet<String> visitedNodes = new LinkedHashSet<String> ();
queue.add(source);
visitedNodes.add(source);
while (!queue.isEmpty()) {
String focusNode = queue.poll();
Set<Node> nodeSet = inputMap.getAllOutgoingNodes(focusNode);
if (null != nodeSet) {
for (Node s: nodeSet) {
if (!visitedNodes.contains(s.edge1)) {
visitedNodes.add(s.edge1);
queue.add(s.edge1);
if (destination.equals(s.edge1)) {
for (String sn: visitedNodes) {
System.out.print(sn);
break;
}
}
}
}
}
graph-theory breadth-first-search
edited Nov 16 '18 at 19:34
Dominique Fortin
1,665817
asked Mar 31 '18 at 12:07
Apoorva SharmaApoorva Sharma
82
1
Preferred --> opinion-based. IMO there is no advantage on average, so the reasons if any would mostly be opinion-based. (avoid stack overflow, easier to code, don't have to move to a function, etc etc)
– user202729
Mar 31 '18 at 12:12
" why BFS is preferred over DFS in this case?" what is this claim based upon ?
– c0der
Apr 6 '18 at 12:55
add a comment |
I am using BFS to check if a node is reachable and for printing the route.
Can anyone explain why BFS is preferred over DFS in this case?
Using below code:
LinkedList<String> queue = new LinkedList<String>();
HashSet<String> visitedNodes = new LinkedHashSet<String> ();
queue.add(source);
visitedNodes.add(source);
while (!queue.isEmpty()) {
String focusNode = queue.poll();
Set<Node> nodeSet = inputMap.getAllOutgoingNodes(focusNode);
if (null != nodeSet) {
for (Node s: nodeSet) {
if (!visitedNodes.contains(s.edge1)) {
visitedNodes.add(s.edge1);
queue.add(s.edge1);
if (destination.equals(s.edge1)) {
for (String sn: visitedNodes) {
System.out.print(sn);
break;
}
}
}
}
}
graph-theory breadth-first-search
edited Nov 16 '18 at 19:34
Dominique Fortin
1,665817
asked Mar 31 '18 at 12:07
Apoorva SharmaApoorva Sharma
82
I am using BFS to check if a node is reachable and for printing the route.
Can anyone explain why BFS is preferred over DFS in this case?
Using below code:
LinkedList<String> queue = new LinkedList<String>();
HashSet<String> visitedNodes = new LinkedHashSet<String> ();
queue.add(source);
visitedNodes.add(source);
while (!queue.isEmpty()) {
String focusNode = queue.poll();
Set<Node> nodeSet = inputMap.getAllOutgoingNodes(focusNode);
if (null != nodeSet) {
for (Node s: nodeSet) {
if (!visitedNodes.contains(s.edge1)) {
visitedNodes.add(s.edge1);
queue.add(s.edge1);
if (destination.equals(s.edge1)) {
for (String sn: visitedNodes) {
System.out.print(sn);
break;
}
}
}
}
}
graph-theory breadth-first-search
graph-theory breadth-first-search
edited Nov 16 '18 at 19:34
Dominique Fortin
1,665817
asked Mar 31 '18 at 12:07
Apoorva SharmaApoorva Sharma
82
edited Nov 16 '18 at 19:34
Dominique Fortin
1,665817
asked Mar 31 '18 at 12:07
Apoorva SharmaApoorva Sharma
82
edited Nov 16 '18 at 19:34
Dominique Fortin
1,665817
edited Nov 16 '18 at 19:34
Dominique Fortin
1,665817
edited Nov 16 '18 at 19:34
Dominique Fortin
1,665817
1,665817
asked Mar 31 '18 at 12:07
Apoorva SharmaApoorva Sharma
82
asked Mar 31 '18 at 12:07
Apoorva SharmaApoorva Sharma
82
asked Mar 31 '18 at 12:07
Apoorva SharmaApoorva Sharma
82
82
1
Preferred --> opinion-based. IMO there is no advantage on average, so the reasons if any would mostly be opinion-based. (avoid stack overflow, easier to code, don't have to move to a function, etc etc)
– user202729
Mar 31 '18 at 12:12
" why BFS is preferred over DFS in this case?" what is this claim based upon ?
– c0der
Apr 6 '18 at 12:55
add a comment |
1
Preferred --> opinion-based. IMO there is no advantage on average, so the reasons if any would mostly be opinion-based. (avoid stack overflow, easier to code, don't have to move to a function, etc etc)
– user202729
Mar 31 '18 at 12:12
" why BFS is preferred over DFS in this case?" what is this claim based upon ?
– c0der
Apr 6 '18 at 12:55
1
1
Preferred --> opinion-based. IMO there is no advantage on average, so the reasons if any would mostly be opinion-based. (avoid stack overflow, easier to code, don't have to move to a function, etc etc)
– user202729
Mar 31 '18 at 12:12
Preferred --> opinion-based. IMO there is no advantage on average, so the reasons if any would mostly be opinion-based. (avoid stack overflow, easier to code, don't have to move to a function, etc etc)
– user202729
Mar 31 '18 at 12:12
" why BFS is preferred over DFS in this case?" what is this claim based upon ?
– c0der
Apr 6 '18 at 12:55
" why BFS is preferred over DFS in this case?" what is this claim based upon ?
– c0der
Apr 6 '18 at 12:55
add a comment |
1 Answer
1
active
oldest
votes
If the problem is to check if a node is reachable then I believe a DFS is preferred (usually just for length of code), if you also have to find a route then the one found with a DFS might be very long (and so very difficult for a human to check), therefore a BFS is preferred.
But anyway there are no general rules, it is all down to personal preference.
answered Mar 31 '18 at 17:12
gcorsogcorso
398
add a comment |
Your Answer
StackExchange.ifUsing("editor", function () {
StackExchange.using("externalEditor", function () {
StackExchange.using("snippets", function () {
StackExchange.snippets.init();
});
});
}, "code-snippets");
StackExchange.ready(function() {
var channelOptions = {
tags: "".split(" "),
id: "1"
};
initTagRenderer("".split(" "), "".split(" "), channelOptions);
StackExchange.using("externalEditor", function() {
// Have to fire editor after snippets, if snippets enabled
if (StackExchange.settings.snippets.snippetsEnabled) {
StackExchange.using("snippets", function() {
createEditor();
});
}
else {
createEditor();
}
});
function createEditor() {
StackExchange.prepareEditor({
heartbeatType: 'answer',
autoActivateHeartbeat: false,
convertImagesToLinks: true,
noModals: true,
showLowRepImageUploadWarning: true,
reputationToPostImages: 10,
bindNavPrevention: true,
postfix: "",
imageUploader: {
brandingHtml: "Powered by u003ca class="icon-imgur-white" href="https://imgur.com/"u003eu003c/au003e",
contentPolicyHtml: "User contributions licensed under u003ca href="https://creativecommons.org/licenses/by-sa/3.0/"u003ecc by-sa 3.0 with attribution requiredu003c/au003e u003ca href="https://stackoverflow.com/legal/content-policy"u003e(content policy)u003c/au003e",
allowUrls: true
},
onDemand: true,
discardSelector: ".discard-answer"
,immediatelyShowMarkdownHelp:true
});
}
});
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
StackExchange.ready(
function () {
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fstackoverflow.com%2fquestions%2f49587545%2ffind-if-a-node-is-reachable-using-bfs%23new-answer', 'question_page');
}
);
Post as a guest
Required, but never shown
1 Answer
1
active
oldest
votes
1 Answer
1
active
oldest
votes
active
oldest
votes
active
oldest
votes
If the problem is to check if a node is reachable then I believe a DFS is preferred (usually just for length of code), if you also have to find a route then the one found with a DFS might be very long (and so very difficult for a human to check), therefore a BFS is preferred.
But anyway there are no general rules, it is all down to personal preference.
answered Mar 31 '18 at 17:12
gcorsogcorso
398
add a comment |
If the problem is to check if a node is reachable then I believe a DFS is preferred (usually just for length of code), if you also have to find a route then the one found with a DFS might be very long (and so very difficult for a human to check), therefore a BFS is preferred.
But anyway there are no general rules, it is all down to personal preference.
answered Mar 31 '18 at 17:12
gcorsogcorso
398
add a comment |
If the problem is to check if a node is reachable then I believe a DFS is preferred (usually just for length of code), if you also have to find a route then the one found with a DFS might be very long (and so very difficult for a human to check), therefore a BFS is preferred.
But anyway there are no general rules, it is all down to personal preference.
answered Mar 31 '18 at 17:12
gcorsogcorso
398
If the problem is to check if a node is reachable then I believe a DFS is preferred (usually just for length of code), if you also have to find a route then the one found with a DFS might be very long (and so very difficult for a human to check), therefore a BFS is preferred.
But anyway there are no general rules, it is all down to personal preference.
answered Mar 31 '18 at 17:12
gcorsogcorso
398
answered Mar 31 '18 at 17:12
gcorsogcorso
398
answered Mar 31 '18 at 17:12
gcorsogcorso
398
answered Mar 31 '18 at 17:12
gcorsogcorso
398
398
add a comment |
add a comment |
Thanks for contributing an answer to Stack Overflow!
- Please be sure to answer the question. Provide details and share your research!
But avoid …
- Asking for help, clarification, or responding to other answers.
- Making statements based on opinion; back them up with references or personal experience.
To learn more, see our tips on writing great answers.
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
StackExchange.ready(
function () {
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fstackoverflow.com%2fquestions%2f49587545%2ffind-if-a-node-is-reachable-using-bfs%23new-answer', 'question_page');
}
);
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
1
Preferred --> opinion-based. IMO there is no advantage on average, so the reasons if any would mostly be opinion-based. (avoid stack overflow, easier to code, don't have to move to a function, etc etc)
– user202729
Mar 31 '18 at 12:12
" why BFS is preferred over DFS in this case?" what is this claim based upon ?
– c0der
Apr 6 '18 at 12:55