implement of DFS algorithm
$begingroup$
i would like to check myself whether following procedures for DFS -Depth First search is correct( so i would like to check if i understood it correctly)
we have following Graph
we use stack for DFS, so let start :
initially vertex A is added to the stack and it is marked as visited(first output is A), next adjacent element are (B,C,D), first let add B, because B has no any adjacent element pop B(so we have A B), now next visiting element of A is C, we push C on stack and C will be also output (A B C), C has only non visited element K, so add k to the stack and write on output (A B C K), K we has following non visited elements D and and L, push D(A B C K D), but D has no non visited adjacent vertex , so pop from stack , and push L, (A B C K D L), now L has only J so push J ( A B C K D L J) and J has only M so finally we have
A B C K D L J M
am i right?thanks in advance
graph-theory
asked Dec 2 '18 at 21:24
dato datuashvilidato datuashvili
5,5011354107
$endgroup$
add a comment |
$begingroup$
i would like to check myself whether following procedures for DFS -Depth First search is correct( so i would like to check if i understood it correctly)
we have following Graph
we use stack for DFS, so let start :
initially vertex A is added to the stack and it is marked as visited(first output is A), next adjacent element are (B,C,D), first let add B, because B has no any adjacent element pop B(so we have A B), now next visiting element of A is C, we push C on stack and C will be also output (A B C), C has only non visited element K, so add k to the stack and write on output (A B C K), K we has following non visited elements D and and L, push D(A B C K D), but D has no non visited adjacent vertex , so pop from stack , and push L, (A B C K D L), now L has only J so push J ( A B C K D L J) and J has only M so finally we have
A B C K D L J M
am i right?thanks in advance
graph-theory
asked Dec 2 '18 at 21:24
dato datuashvilidato datuashvili
5,5011354107
$endgroup$
add a comment |
$begingroup$
i would like to check myself whether following procedures for DFS -Depth First search is correct( so i would like to check if i understood it correctly)
we have following Graph
we use stack for DFS, so let start :
initially vertex A is added to the stack and it is marked as visited(first output is A), next adjacent element are (B,C,D), first let add B, because B has no any adjacent element pop B(so we have A B), now next visiting element of A is C, we push C on stack and C will be also output (A B C), C has only non visited element K, so add k to the stack and write on output (A B C K), K we has following non visited elements D and and L, push D(A B C K D), but D has no non visited adjacent vertex , so pop from stack , and push L, (A B C K D L), now L has only J so push J ( A B C K D L J) and J has only M so finally we have
A B C K D L J M
am i right?thanks in advance
graph-theory
asked Dec 2 '18 at 21:24
dato datuashvilidato datuashvili
5,5011354107
$endgroup$
i would like to check myself whether following procedures for DFS -Depth First search is correct( so i would like to check if i understood it correctly)
we have following Graph
we use stack for DFS, so let start :
initially vertex A is added to the stack and it is marked as visited(first output is A), next adjacent element are (B,C,D), first let add B, because B has no any adjacent element pop B(so we have A B), now next visiting element of A is C, we push C on stack and C will be also output (A B C), C has only non visited element K, so add k to the stack and write on output (A B C K), K we has following non visited elements D and and L, push D(A B C K D), but D has no non visited adjacent vertex , so pop from stack , and push L, (A B C K D L), now L has only J so push J ( A B C K D L J) and J has only M so finally we have
A B C K D L J M
am i right?thanks in advance
graph-theory
graph-theory
asked Dec 2 '18 at 21:24
dato datuashvilidato datuashvili
5,5011354107
asked Dec 2 '18 at 21:24
dato datuashvilidato datuashvili
5,5011354107
asked Dec 2 '18 at 21:24
dato datuashvilidato datuashvili
5,5011354107
asked Dec 2 '18 at 21:24
dato datuashvilidato datuashvili
5,5011354107
asked Dec 2 '18 at 21:24
dato datuashvilidato datuashvili
5,5011354107
5,5011354107
add a comment |
add a comment |
2 Answers
2
active
oldest
votes
$begingroup$
Not sure what you said but in case you chose to discover L from node K that is incorrect. You go to node K from node D.
So basically the DFS graph has the following arcs:(A,B), (A,C), (C,K), (K,D),(D,L), (L,J), (J,M).
answered Dec 2 '18 at 21:39
Alina.ChAlina.Ch
263
$endgroup$
$begingroup$
aaaa one mistake right, from D i can go to L, right i saw now
$endgroup$
– dato datuashvili
Dec 2 '18 at 21:42
$begingroup$
Small mistake. Keep up the good work !!
$endgroup$
– Alina.Ch
Dec 2 '18 at 21:44
$begingroup$
what about BFS ?
$endgroup$
– dato datuashvili
Dec 2 '18 at 21:46
$begingroup$
Try yourself first and I shall correct you if needed ;)
$endgroup$
– Alina.Ch
Dec 2 '18 at 21:47
$begingroup$
My teacher once told me a very good example to remember BFS and DFS. You go to a party and you bring some friends with you. In DFS you go to the checklist and you enter first and than your friends and then the rest of people in line. In BFS you enter but your friends are told to stay at the back of the queue in case there is any place left for them to enter.
$endgroup$
– Alina.Ch
Dec 2 '18 at 21:51
|
show 4 more comments
$begingroup$
so for breadth first algorithm we use Queue -FIFO=first in first out, first will be node A, new A has three node which is adjacent , alphabetically we push
B
C
D,
now current working node is B, B has no any adjacent node, so deque B ( we have A B as list),in queue we have left
C
D
so current working node is C and remove from queue (A B C), now C has only non visited node K so enque in queue , we have
D
K
now currently working node is D, we has L as an visited so enque L and remove D
( A B C D)
K
L
now K has no any non visited so deque it ( A B C D K), now we gave L on top of queue , deque L( A B C D K L) and L has only J so enqueue J
(A B C D K L J M) will be answer i think i am right
answered Dec 2 '18 at 22:03
dato datuashvilidato datuashvili
5,5011354107
$endgroup$
add a comment |
Your Answer
StackExchange.ifUsing("editor", function () {
return StackExchange.using("mathjaxEditing", function () {
StackExchange.MarkdownEditor.creationCallbacks.add(function (editor, postfix) {
StackExchange.mathjaxEditing.prepareWmdForMathJax(editor, postfix, [["$", "$"], ["\\(","\\)"]]);
});
});
}, "mathjax-editing");
StackExchange.ready(function() {
var channelOptions = {
tags: "".split(" "),
id: "69"
};
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
},
noCode: 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%2fmath.stackexchange.com%2fquestions%2f3023217%2fimplement-of-dfs-algorithm%23new-answer', 'question_page');
}
);
Post as a guest
Required, but never shown
2 Answers
2
active
oldest
votes
2 Answers
2
active
oldest
votes
active
oldest
votes
active
oldest
votes
$begingroup$
Not sure what you said but in case you chose to discover L from node K that is incorrect. You go to node K from node D.
So basically the DFS graph has the following arcs:(A,B), (A,C), (C,K), (K,D),(D,L), (L,J), (J,M).
answered Dec 2 '18 at 21:39
Alina.ChAlina.Ch
263
$endgroup$
$begingroup$
aaaa one mistake right, from D i can go to L, right i saw now
$endgroup$
– dato datuashvili
Dec 2 '18 at 21:42
$begingroup$
Small mistake. Keep up the good work !!
$endgroup$
– Alina.Ch
Dec 2 '18 at 21:44
$begingroup$
what about BFS ?
$endgroup$
– dato datuashvili
Dec 2 '18 at 21:46
$begingroup$
Try yourself first and I shall correct you if needed ;)
$endgroup$
– Alina.Ch
Dec 2 '18 at 21:47
$begingroup$
My teacher once told me a very good example to remember BFS and DFS. You go to a party and you bring some friends with you. In DFS you go to the checklist and you enter first and than your friends and then the rest of people in line. In BFS you enter but your friends are told to stay at the back of the queue in case there is any place left for them to enter.
$endgroup$
– Alina.Ch
Dec 2 '18 at 21:51
|
show 4 more comments
$begingroup$
Not sure what you said but in case you chose to discover L from node K that is incorrect. You go to node K from node D.
So basically the DFS graph has the following arcs:(A,B), (A,C), (C,K), (K,D),(D,L), (L,J), (J,M).
answered Dec 2 '18 at 21:39
Alina.ChAlina.Ch
263
$endgroup$
$begingroup$
aaaa one mistake right, from D i can go to L, right i saw now
$endgroup$
– dato datuashvili
Dec 2 '18 at 21:42
$begingroup$
Small mistake. Keep up the good work !!
$endgroup$
– Alina.Ch
Dec 2 '18 at 21:44
$begingroup$
what about BFS ?
$endgroup$
– dato datuashvili
Dec 2 '18 at 21:46
$begingroup$
Try yourself first and I shall correct you if needed ;)
$endgroup$
– Alina.Ch
Dec 2 '18 at 21:47
$begingroup$
My teacher once told me a very good example to remember BFS and DFS. You go to a party and you bring some friends with you. In DFS you go to the checklist and you enter first and than your friends and then the rest of people in line. In BFS you enter but your friends are told to stay at the back of the queue in case there is any place left for them to enter.
$endgroup$
– Alina.Ch
Dec 2 '18 at 21:51
|
show 4 more comments
$begingroup$
Not sure what you said but in case you chose to discover L from node K that is incorrect. You go to node K from node D.
So basically the DFS graph has the following arcs:(A,B), (A,C), (C,K), (K,D),(D,L), (L,J), (J,M).
answered Dec 2 '18 at 21:39
Alina.ChAlina.Ch
263
$endgroup$
Not sure what you said but in case you chose to discover L from node K that is incorrect. You go to node K from node D.
So basically the DFS graph has the following arcs:(A,B), (A,C), (C,K), (K,D),(D,L), (L,J), (J,M).
answered Dec 2 '18 at 21:39
Alina.ChAlina.Ch
263
answered Dec 2 '18 at 21:39
Alina.ChAlina.Ch
263
answered Dec 2 '18 at 21:39
Alina.ChAlina.Ch
263
answered Dec 2 '18 at 21:39
Alina.ChAlina.Ch
263
263
$begingroup$
aaaa one mistake right, from D i can go to L, right i saw now
$endgroup$
– dato datuashvili
Dec 2 '18 at 21:42
$begingroup$
Small mistake. Keep up the good work !!
$endgroup$
– Alina.Ch
Dec 2 '18 at 21:44
$begingroup$
what about BFS ?
$endgroup$
– dato datuashvili
Dec 2 '18 at 21:46
$begingroup$
Try yourself first and I shall correct you if needed ;)
$endgroup$
– Alina.Ch
Dec 2 '18 at 21:47
$begingroup$
My teacher once told me a very good example to remember BFS and DFS. You go to a party and you bring some friends with you. In DFS you go to the checklist and you enter first and than your friends and then the rest of people in line. In BFS you enter but your friends are told to stay at the back of the queue in case there is any place left for them to enter.
$endgroup$
– Alina.Ch
Dec 2 '18 at 21:51
|
show 4 more comments
$begingroup$
aaaa one mistake right, from D i can go to L, right i saw now
$endgroup$
– dato datuashvili
Dec 2 '18 at 21:42
$begingroup$
Small mistake. Keep up the good work !!
$endgroup$
– Alina.Ch
Dec 2 '18 at 21:44
$begingroup$
what about BFS ?
$endgroup$
– dato datuashvili
Dec 2 '18 at 21:46
$begingroup$
Try yourself first and I shall correct you if needed ;)
$endgroup$
– Alina.Ch
Dec 2 '18 at 21:47
$begingroup$
My teacher once told me a very good example to remember BFS and DFS. You go to a party and you bring some friends with you. In DFS you go to the checklist and you enter first and than your friends and then the rest of people in line. In BFS you enter but your friends are told to stay at the back of the queue in case there is any place left for them to enter.
$endgroup$
– Alina.Ch
Dec 2 '18 at 21:51
$begingroup$
aaaa one mistake right, from D i can go to L, right i saw now
$endgroup$
– dato datuashvili
Dec 2 '18 at 21:42
$begingroup$
aaaa one mistake right, from D i can go to L, right i saw now
$endgroup$
– dato datuashvili
Dec 2 '18 at 21:42
$begingroup$
Small mistake. Keep up the good work !!
$endgroup$
– Alina.Ch
Dec 2 '18 at 21:44
$begingroup$
Small mistake. Keep up the good work !!
$endgroup$
– Alina.Ch
Dec 2 '18 at 21:44
$begingroup$
what about BFS ?
$endgroup$
– dato datuashvili
Dec 2 '18 at 21:46
$begingroup$
what about BFS ?
$endgroup$
– dato datuashvili
Dec 2 '18 at 21:46
$begingroup$
Try yourself first and I shall correct you if needed ;)
$endgroup$
– Alina.Ch
Dec 2 '18 at 21:47
$begingroup$
Try yourself first and I shall correct you if needed ;)
$endgroup$
– Alina.Ch
Dec 2 '18 at 21:47
$begingroup$
My teacher once told me a very good example to remember BFS and DFS. You go to a party and you bring some friends with you. In DFS you go to the checklist and you enter first and than your friends and then the rest of people in line. In BFS you enter but your friends are told to stay at the back of the queue in case there is any place left for them to enter.
$endgroup$
– Alina.Ch
Dec 2 '18 at 21:51
$begingroup$
My teacher once told me a very good example to remember BFS and DFS. You go to a party and you bring some friends with you. In DFS you go to the checklist and you enter first and than your friends and then the rest of people in line. In BFS you enter but your friends are told to stay at the back of the queue in case there is any place left for them to enter.
$endgroup$
– Alina.Ch
Dec 2 '18 at 21:51
|
show 4 more comments
$begingroup$
so for breadth first algorithm we use Queue -FIFO=first in first out, first will be node A, new A has three node which is adjacent , alphabetically we push
B
C
D,
now current working node is B, B has no any adjacent node, so deque B ( we have A B as list),in queue we have left
C
D
so current working node is C and remove from queue (A B C), now C has only non visited node K so enque in queue , we have
D
K
now currently working node is D, we has L as an visited so enque L and remove D
( A B C D)
K
L
now K has no any non visited so deque it ( A B C D K), now we gave L on top of queue , deque L( A B C D K L) and L has only J so enqueue J
(A B C D K L J M) will be answer i think i am right
answered Dec 2 '18 at 22:03
dato datuashvilidato datuashvili
5,5011354107
$endgroup$
add a comment |
$begingroup$
so for breadth first algorithm we use Queue -FIFO=first in first out, first will be node A, new A has three node which is adjacent , alphabetically we push
B
C
D,
now current working node is B, B has no any adjacent node, so deque B ( we have A B as list),in queue we have left
C
D
so current working node is C and remove from queue (A B C), now C has only non visited node K so enque in queue , we have
D
K
now currently working node is D, we has L as an visited so enque L and remove D
( A B C D)
K
L
now K has no any non visited so deque it ( A B C D K), now we gave L on top of queue , deque L( A B C D K L) and L has only J so enqueue J
(A B C D K L J M) will be answer i think i am right
answered Dec 2 '18 at 22:03
dato datuashvilidato datuashvili
5,5011354107
$endgroup$
add a comment |
$begingroup$
so for breadth first algorithm we use Queue -FIFO=first in first out, first will be node A, new A has three node which is adjacent , alphabetically we push
B
C
D,
now current working node is B, B has no any adjacent node, so deque B ( we have A B as list),in queue we have left
C
D
so current working node is C and remove from queue (A B C), now C has only non visited node K so enque in queue , we have
D
K
now currently working node is D, we has L as an visited so enque L and remove D
( A B C D)
K
L
now K has no any non visited so deque it ( A B C D K), now we gave L on top of queue , deque L( A B C D K L) and L has only J so enqueue J
(A B C D K L J M) will be answer i think i am right
answered Dec 2 '18 at 22:03
dato datuashvilidato datuashvili
5,5011354107
$endgroup$
so for breadth first algorithm we use Queue -FIFO=first in first out, first will be node A, new A has three node which is adjacent , alphabetically we push
B
C
D,
now current working node is B, B has no any adjacent node, so deque B ( we have A B as list),in queue we have left
C
D
so current working node is C and remove from queue (A B C), now C has only non visited node K so enque in queue , we have
D
K
now currently working node is D, we has L as an visited so enque L and remove D
( A B C D)
K
L
now K has no any non visited so deque it ( A B C D K), now we gave L on top of queue , deque L( A B C D K L) and L has only J so enqueue J
(A B C D K L J M) will be answer i think i am right
answered Dec 2 '18 at 22:03
dato datuashvilidato datuashvili
5,5011354107
answered Dec 2 '18 at 22:03
dato datuashvilidato datuashvili
5,5011354107
answered Dec 2 '18 at 22:03
dato datuashvilidato datuashvili
5,5011354107
answered Dec 2 '18 at 22:03
dato datuashvilidato datuashvili
5,5011354107
5,5011354107
add a comment |
add a comment |
Thanks for contributing an answer to Mathematics Stack Exchange!
- 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.
Use MathJax to format equations. MathJax reference.
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%2fmath.stackexchange.com%2fquestions%2f3023217%2fimplement-of-dfs-algorithm%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
