Breadth First Search Counter Example
up vote
0
down vote
favorite
Statement:
"Consider an arbitrary graph G=(V,E) and a source vertex s that is in V. For each shortest paths tree rooted at s, there exists an ordering of the vertices in an adjacency list representation of G which results in precisely this shortest-paths tree when BFS is run from s."
I am struggling to come up with a counter-example for this statement that I have taken for face value to be FALSE.
I understand that the ordering matters when it comes to the shortest-paths tree derived from BFS assuming that the order of the vertex's in the adjacency list is the order BFS follows but can't seem to think of a counter-example that violates this statement.
Edit: I am not asking how to find the other shortest-tree paths, but an example that shows that there are OTHER shortest-tree paths that are not found by BFS.
graph-theory
asked Nov 20 at 2:01
John Larkos
177
add a comment |
up vote
0
down vote
favorite
Statement:
"Consider an arbitrary graph G=(V,E) and a source vertex s that is in V. For each shortest paths tree rooted at s, there exists an ordering of the vertices in an adjacency list representation of G which results in precisely this shortest-paths tree when BFS is run from s."
I am struggling to come up with a counter-example for this statement that I have taken for face value to be FALSE.
I understand that the ordering matters when it comes to the shortest-paths tree derived from BFS assuming that the order of the vertex's in the adjacency list is the order BFS follows but can't seem to think of a counter-example that violates this statement.
Edit: I am not asking how to find the other shortest-tree paths, but an example that shows that there are OTHER shortest-tree paths that are not found by BFS.
graph-theory
asked Nov 20 at 2:01
John Larkos
177
Possible duplicate of Finding all the shortest paths between two nodes in unweighted undirected graph
– bishop
Nov 20 at 2:05
add a comment |
up vote
0
down vote
favorite
up vote
0
down vote
favorite
Statement:
"Consider an arbitrary graph G=(V,E) and a source vertex s that is in V. For each shortest paths tree rooted at s, there exists an ordering of the vertices in an adjacency list representation of G which results in precisely this shortest-paths tree when BFS is run from s."
I am struggling to come up with a counter-example for this statement that I have taken for face value to be FALSE.
I understand that the ordering matters when it comes to the shortest-paths tree derived from BFS assuming that the order of the vertex's in the adjacency list is the order BFS follows but can't seem to think of a counter-example that violates this statement.
Edit: I am not asking how to find the other shortest-tree paths, but an example that shows that there are OTHER shortest-tree paths that are not found by BFS.
graph-theory
asked Nov 20 at 2:01
John Larkos
177
Statement:
"Consider an arbitrary graph G=(V,E) and a source vertex s that is in V. For each shortest paths tree rooted at s, there exists an ordering of the vertices in an adjacency list representation of G which results in precisely this shortest-paths tree when BFS is run from s."
I am struggling to come up with a counter-example for this statement that I have taken for face value to be FALSE.
I understand that the ordering matters when it comes to the shortest-paths tree derived from BFS assuming that the order of the vertex's in the adjacency list is the order BFS follows but can't seem to think of a counter-example that violates this statement.
Edit: I am not asking how to find the other shortest-tree paths, but an example that shows that there are OTHER shortest-tree paths that are not found by BFS.
graph-theory
graph-theory
asked Nov 20 at 2:01
John Larkos
177
asked Nov 20 at 2:01
John Larkos
177
edited Nov 20 at 2:18
asked Nov 20 at 2:01
John Larkos
177
asked Nov 20 at 2:01
John Larkos
177
asked Nov 20 at 2:01
John Larkos
177
177
Possible duplicate of Finding all the shortest paths between two nodes in unweighted undirected graph
– bishop
Nov 20 at 2:05
add a comment |
Possible duplicate of Finding all the shortest paths between two nodes in unweighted undirected graph
– bishop
Nov 20 at 2:05
Possible duplicate of Finding all the shortest paths between two nodes in unweighted undirected graph
– bishop
Nov 20 at 2:05
Possible duplicate of Finding all the shortest paths between two nodes in unweighted undirected graph
– bishop
Nov 20 at 2:05
add a comment |
1 Answer
1
active
oldest
votes
up vote
0
down vote
Confirm your graph is unweighted and undirected ?
answered Nov 22 at 15:37
TheWildHealer
405216
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',
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%2f53385179%2fbreadth-first-search-counter-example%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
up vote
0
down vote
Confirm your graph is unweighted and undirected ?
answered Nov 22 at 15:37
TheWildHealer
405216
add a comment |
up vote
0
down vote
Confirm your graph is unweighted and undirected ?
answered Nov 22 at 15:37
TheWildHealer
405216
add a comment |
up vote
0
down vote
up vote
0
down vote
Confirm your graph is unweighted and undirected ?
answered Nov 22 at 15:37
TheWildHealer
405216
Confirm your graph is unweighted and undirected ?
answered Nov 22 at 15:37
TheWildHealer
405216
answered Nov 22 at 15:37
TheWildHealer
405216
answered Nov 22 at 15:37
TheWildHealer
405216
answered Nov 22 at 15:37
TheWildHealer
405216
405216
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.
Some of your past answers have not been well-received, and you're in danger of being blocked from answering.
Please pay close attention to the following guidance:
- 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%2f53385179%2fbreadth-first-search-counter-example%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
Possible duplicate of Finding all the shortest paths between two nodes in unweighted undirected graph
– bishop
Nov 20 at 2:05