Mixing
How to get the max depth of a graph with BFS
When I use a BFS algorithm on a graph, I try to obtain the maximum depth of the graph.
But I don't know where to put my incrementation in this algorithm :
FUNCTION BFS(G,s)
BEGIN
FOR any vertex v of G
DO Mark[v] ← False
END FOR Mark[s] ← True
F ← Empty Queue
enqueue(s,F)
WHILE F is not empty
DO v ← dequeue(F)
FOR any vertex w neighbor of v
DO
IF Mark[w] = False THEN
Mark[w] ← True;
enqueue(w,F)
END IF
FOR END
WHILE END
I tried to put an incrementation of a number after the END FOR but it gives an number superior than the real max depth of the graph.
Please can anyone help me.
Thank You.
max graph-theory graph-algorithm breadth-first-search depth
edited Nov 21 '18 at 20:49
Dominique Fortin
1,648816
asked Apr 17 '17 at 19:21
RajRaj
11
add a comment |
When I use a BFS algorithm on a graph, I try to obtain the maximum depth of the graph.
But I don't know where to put my incrementation in this algorithm :
FUNCTION BFS(G,s)
BEGIN
FOR any vertex v of G
DO Mark[v] ← False
END FOR Mark[s] ← True
F ← Empty Queue
enqueue(s,F)
WHILE F is not empty
DO v ← dequeue(F)
FOR any vertex w neighbor of v
DO
IF Mark[w] = False THEN
Mark[w] ← True;
enqueue(w,F)
END IF
FOR END
WHILE END
I tried to put an incrementation of a number after the END FOR but it gives an number superior than the real max depth of the graph.
Please can anyone help me.
Thank You.
max graph-theory graph-algorithm breadth-first-search depth
edited Nov 21 '18 at 20:49
Dominique Fortin
1,648816
asked Apr 17 '17 at 19:21
RajRaj
11
What kind of graph is this and how do you define this maximum depth?
– gue
Apr 20 '17 at 8:55
Hello, I posted an answer just below.
– Raj
Apr 25 '17 at 21:35
add a comment |
When I use a BFS algorithm on a graph, I try to obtain the maximum depth of the graph.
But I don't know where to put my incrementation in this algorithm :
FUNCTION BFS(G,s)
BEGIN
FOR any vertex v of G
DO Mark[v] ← False
END FOR Mark[s] ← True
F ← Empty Queue
enqueue(s,F)
WHILE F is not empty
DO v ← dequeue(F)
FOR any vertex w neighbor of v
DO
IF Mark[w] = False THEN
Mark[w] ← True;
enqueue(w,F)
END IF
FOR END
WHILE END
I tried to put an incrementation of a number after the END FOR but it gives an number superior than the real max depth of the graph.
Please can anyone help me.
Thank You.
max graph-theory graph-algorithm breadth-first-search depth
edited Nov 21 '18 at 20:49
Dominique Fortin
1,648816
asked Apr 17 '17 at 19:21
RajRaj
11
When I use a BFS algorithm on a graph, I try to obtain the maximum depth of the graph.
But I don't know where to put my incrementation in this algorithm :
FUNCTION BFS(G,s)
BEGIN
FOR any vertex v of G
DO Mark[v] ← False
END FOR Mark[s] ← True
F ← Empty Queue
enqueue(s,F)
WHILE F is not empty
DO v ← dequeue(F)
FOR any vertex w neighbor of v
DO
IF Mark[w] = False THEN
Mark[w] ← True;
enqueue(w,F)
END IF
FOR END
WHILE END
I tried to put an incrementation of a number after the END FOR but it gives an number superior than the real max depth of the graph.
Please can anyone help me.
Thank You.
max graph-theory graph-algorithm breadth-first-search depth
max graph-theory graph-algorithm breadth-first-search depth
edited Nov 21 '18 at 20:49
Dominique Fortin
1,648816
asked Apr 17 '17 at 19:21
RajRaj
11
edited Nov 21 '18 at 20:49
Dominique Fortin
1,648816
asked Apr 17 '17 at 19:21
RajRaj
11
edited Nov 21 '18 at 20:49
Dominique Fortin
1,648816
edited Nov 21 '18 at 20:49
Dominique Fortin
1,648816
edited Nov 21 '18 at 20:49
Dominique Fortin
1,648816
1,648816
asked Apr 17 '17 at 19:21
RajRaj
11
asked Apr 17 '17 at 19:21
RajRaj
11
asked Apr 17 '17 at 19:21
RajRaj
11
11
What kind of graph is this and how do you define this maximum depth?
– gue
Apr 20 '17 at 8:55
Hello, I posted an answer just below.
– Raj
Apr 25 '17 at 21:35
add a comment |
What kind of graph is this and how do you define this maximum depth?
– gue
Apr 20 '17 at 8:55
Hello, I posted an answer just below.
– Raj
Apr 25 '17 at 21:35
What kind of graph is this and how do you define this maximum depth?
– gue
Apr 20 '17 at 8:55
What kind of graph is this and how do you define this maximum depth?
– gue
Apr 20 '17 at 8:55
Hello, I posted an answer just below.
– Raj
Apr 25 '17 at 21:35
Hello, I posted an answer just below.
– Raj
Apr 25 '17 at 21:35
add a comment |
2 Answers
2
active
oldest
votes
Running BFS on a graph gives you a tree and what you want actually is the depth of the tree. Putting an incrementation after the END FOR will absolutely give you a number greater than the depth of tree (depending on your code). Imagine this case: all neighbors of the current vertex 'v' are visited (all of them marked as true), this means that vertex v is leaf but your incrementation will still increase by one, which is not correct.
Solution: your incrementation should only increase when for current v there is at least one neighbor w which is not yet visited ( marked as false) and you have not yet increased the depth for any other vertex at the same level (vertices at the same distance from the root 's') as w. So what you missing in your code is you should keep track of the level in your code to know when to increase.
This question has already been asked for a tree, so you might have to look to this How to keep track of depth in breadth first search? just to let you know how to update your code to keep track of the level. Simply the idea is to push a NULL to the queue at the end of each level. The root itself is at level0, so after pushing root to the queue, push also a NULL. After that, each time you encounter NULL, push NULL to the queue for the next level and check if the top of the queue is not NULL increase the depth by one and continue else break.
FUNCTION BFS(G,s)
BEGIN
FOR any vertex v of G DO
Mark[v] ← False
END FOR
Mark[s] ← True
F ← Empty Queue
depth=0
enqueue(s,F), enqueue(NULL,F) // this is the level 0
WHILE F is not empty DO
v ← dequeue(F)
IF v=NULL THEN
enqueue(NULL,F)
IF(F.peek()==NULL) THEN
BREAK
ELSE
depth++
Continue
FOR any vertex w neighbor of v DO
IF Mark[w] = False THEN
Mark[w] ← True;
enqueue(w,F)
END IF
FOR END
WHILE END
edited May 23 '17 at 12:34
Community♦
11
answered Apr 20 '17 at 16:17
AbdulhakeemAbdulhakeem
1235
Thank you very much for your answer. I also tried one different solution very similar to yours and it works
– Raj
Apr 25 '17 at 21:31
add a comment |
With my friend we found this solution :
FUNCTION BFS(G,s)
BEGIN
FOR any vertex v of G
DO Mark[v] ← False
END FOR Mark[s] ← True
F ← Empty Queue
DIST ← Empty Tab
COUNTER = 0
enqueue(s,F)
WHILE F is not empty
DO v ← dequeue(F)
DIST[v] ← 0
FOR any vertex w neighbor of v
DO
IF Mark[w] = False THEN
Mark[w] ← True;
enqueue(w,F)
DIST[w] ← DIST[v] + 1
IF [COUNTER < DIST[w]] THEN
COUNTER = DIST[w];
END IF
END IF
FOR END
WHILE END
RETURN (COUNTER);
END FUNCTION
I editied this answer after the comment of Abdulhakeem Apr 26 at 3:36, because previsouly I posted the wrong one.
answered Apr 25 '17 at 21:35
RajRaj
11
That is not what you have asked. This is the mere BFS algorithm which finds the distance of all vertices of graph G from a source vertex. DIST is an array of values, you need to do one extra O(V) (V is the number of vertices in graph G) to find the max value from DIST which will be the depth of the tree. So if you want to find the depth of tree in just O(V+E), I would say the other approach is more efficient.
– Abdulhakeem
Apr 26 '17 at 3:36
Hello, Thank you for your comment, i just corrected my answer, i posted the wrong one. Now its correct normally.
– Raj
May 6 '17 at 10:55
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%2f43458102%2fhow-to-get-the-max-depth-of-a-graph-with-bfs%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
Running BFS on a graph gives you a tree and what you want actually is the depth of the tree. Putting an incrementation after the END FOR will absolutely give you a number greater than the depth of tree (depending on your code). Imagine this case: all neighbors of the current vertex 'v' are visited (all of them marked as true), this means that vertex v is leaf but your incrementation will still increase by one, which is not correct.
Solution: your incrementation should only increase when for current v there is at least one neighbor w which is not yet visited ( marked as false) and you have not yet increased the depth for any other vertex at the same level (vertices at the same distance from the root 's') as w. So what you missing in your code is you should keep track of the level in your code to know when to increase.
This question has already been asked for a tree, so you might have to look to this How to keep track of depth in breadth first search? just to let you know how to update your code to keep track of the level. Simply the idea is to push a NULL to the queue at the end of each level. The root itself is at level0, so after pushing root to the queue, push also a NULL. After that, each time you encounter NULL, push NULL to the queue for the next level and check if the top of the queue is not NULL increase the depth by one and continue else break.
FUNCTION BFS(G,s)
BEGIN
FOR any vertex v of G DO
Mark[v] ← False
END FOR
Mark[s] ← True
F ← Empty Queue
depth=0
enqueue(s,F), enqueue(NULL,F) // this is the level 0
WHILE F is not empty DO
v ← dequeue(F)
IF v=NULL THEN
enqueue(NULL,F)
IF(F.peek()==NULL) THEN
BREAK
ELSE
depth++
Continue
FOR any vertex w neighbor of v DO
IF Mark[w] = False THEN
Mark[w] ← True;
enqueue(w,F)
END IF
FOR END
WHILE END
edited May 23 '17 at 12:34
Community♦
11
answered Apr 20 '17 at 16:17
AbdulhakeemAbdulhakeem
1235
Thank you very much for your answer. I also tried one different solution very similar to yours and it works
– Raj
Apr 25 '17 at 21:31
add a comment |
Running BFS on a graph gives you a tree and what you want actually is the depth of the tree. Putting an incrementation after the END FOR will absolutely give you a number greater than the depth of tree (depending on your code). Imagine this case: all neighbors of the current vertex 'v' are visited (all of them marked as true), this means that vertex v is leaf but your incrementation will still increase by one, which is not correct.
Solution: your incrementation should only increase when for current v there is at least one neighbor w which is not yet visited ( marked as false) and you have not yet increased the depth for any other vertex at the same level (vertices at the same distance from the root 's') as w. So what you missing in your code is you should keep track of the level in your code to know when to increase.
This question has already been asked for a tree, so you might have to look to this How to keep track of depth in breadth first search? just to let you know how to update your code to keep track of the level. Simply the idea is to push a NULL to the queue at the end of each level. The root itself is at level0, so after pushing root to the queue, push also a NULL. After that, each time you encounter NULL, push NULL to the queue for the next level and check if the top of the queue is not NULL increase the depth by one and continue else break.
FUNCTION BFS(G,s)
BEGIN
FOR any vertex v of G DO
Mark[v] ← False
END FOR
Mark[s] ← True
F ← Empty Queue
depth=0
enqueue(s,F), enqueue(NULL,F) // this is the level 0
WHILE F is not empty DO
v ← dequeue(F)
IF v=NULL THEN
enqueue(NULL,F)
IF(F.peek()==NULL) THEN
BREAK
ELSE
depth++
Continue
FOR any vertex w neighbor of v DO
IF Mark[w] = False THEN
Mark[w] ← True;
enqueue(w,F)
END IF
FOR END
WHILE END
edited May 23 '17 at 12:34
Community♦
11
answered Apr 20 '17 at 16:17
AbdulhakeemAbdulhakeem
1235
Thank you very much for your answer. I also tried one different solution very similar to yours and it works
– Raj
Apr 25 '17 at 21:31
add a comment |
Running BFS on a graph gives you a tree and what you want actually is the depth of the tree. Putting an incrementation after the END FOR will absolutely give you a number greater than the depth of tree (depending on your code). Imagine this case: all neighbors of the current vertex 'v' are visited (all of them marked as true), this means that vertex v is leaf but your incrementation will still increase by one, which is not correct.
Solution: your incrementation should only increase when for current v there is at least one neighbor w which is not yet visited ( marked as false) and you have not yet increased the depth for any other vertex at the same level (vertices at the same distance from the root 's') as w. So what you missing in your code is you should keep track of the level in your code to know when to increase.
This question has already been asked for a tree, so you might have to look to this How to keep track of depth in breadth first search? just to let you know how to update your code to keep track of the level. Simply the idea is to push a NULL to the queue at the end of each level. The root itself is at level0, so after pushing root to the queue, push also a NULL. After that, each time you encounter NULL, push NULL to the queue for the next level and check if the top of the queue is not NULL increase the depth by one and continue else break.
FUNCTION BFS(G,s)
BEGIN
FOR any vertex v of G DO
Mark[v] ← False
END FOR
Mark[s] ← True
F ← Empty Queue
depth=0
enqueue(s,F), enqueue(NULL,F) // this is the level 0
WHILE F is not empty DO
v ← dequeue(F)
IF v=NULL THEN
enqueue(NULL,F)
IF(F.peek()==NULL) THEN
BREAK
ELSE
depth++
Continue
FOR any vertex w neighbor of v DO
IF Mark[w] = False THEN
Mark[w] ← True;
enqueue(w,F)
END IF
FOR END
WHILE END
edited May 23 '17 at 12:34
Community♦
11
answered Apr 20 '17 at 16:17
AbdulhakeemAbdulhakeem
1235
Running BFS on a graph gives you a tree and what you want actually is the depth of the tree. Putting an incrementation after the END FOR will absolutely give you a number greater than the depth of tree (depending on your code). Imagine this case: all neighbors of the current vertex 'v' are visited (all of them marked as true), this means that vertex v is leaf but your incrementation will still increase by one, which is not correct.
Solution: your incrementation should only increase when for current v there is at least one neighbor w which is not yet visited ( marked as false) and you have not yet increased the depth for any other vertex at the same level (vertices at the same distance from the root 's') as w. So what you missing in your code is you should keep track of the level in your code to know when to increase.
This question has already been asked for a tree, so you might have to look to this How to keep track of depth in breadth first search? just to let you know how to update your code to keep track of the level. Simply the idea is to push a NULL to the queue at the end of each level. The root itself is at level0, so after pushing root to the queue, push also a NULL. After that, each time you encounter NULL, push NULL to the queue for the next level and check if the top of the queue is not NULL increase the depth by one and continue else break.
FUNCTION BFS(G,s)
BEGIN
FOR any vertex v of G DO
Mark[v] ← False
END FOR
Mark[s] ← True
F ← Empty Queue
depth=0
enqueue(s,F), enqueue(NULL,F) // this is the level 0
WHILE F is not empty DO
v ← dequeue(F)
IF v=NULL THEN
enqueue(NULL,F)
IF(F.peek()==NULL) THEN
BREAK
ELSE
depth++
Continue
FOR any vertex w neighbor of v DO
IF Mark[w] = False THEN
Mark[w] ← True;
enqueue(w,F)
END IF
FOR END
WHILE END
edited May 23 '17 at 12:34
Community♦
11
answered Apr 20 '17 at 16:17
AbdulhakeemAbdulhakeem
1235
edited May 23 '17 at 12:34
Community♦
11
edited May 23 '17 at 12:34
Community♦
11
edited May 23 '17 at 12:34
Community♦
11
11
answered Apr 20 '17 at 16:17
AbdulhakeemAbdulhakeem
1235
answered Apr 20 '17 at 16:17
AbdulhakeemAbdulhakeem
1235
answered Apr 20 '17 at 16:17
AbdulhakeemAbdulhakeem
1235
1235
Thank you very much for your answer. I also tried one different solution very similar to yours and it works
– Raj
Apr 25 '17 at 21:31
add a comment |
Thank you very much for your answer. I also tried one different solution very similar to yours and it works
– Raj
Apr 25 '17 at 21:31
Thank you very much for your answer. I also tried one different solution very similar to yours and it works
– Raj
Apr 25 '17 at 21:31
Thank you very much for your answer. I also tried one different solution very similar to yours and it works
– Raj
Apr 25 '17 at 21:31
add a comment |
With my friend we found this solution :
FUNCTION BFS(G,s)
BEGIN
FOR any vertex v of G
DO Mark[v] ← False
END FOR Mark[s] ← True
F ← Empty Queue
DIST ← Empty Tab
COUNTER = 0
enqueue(s,F)
WHILE F is not empty
DO v ← dequeue(F)
DIST[v] ← 0
FOR any vertex w neighbor of v
DO
IF Mark[w] = False THEN
Mark[w] ← True;
enqueue(w,F)
DIST[w] ← DIST[v] + 1
IF [COUNTER < DIST[w]] THEN
COUNTER = DIST[w];
END IF
END IF
FOR END
WHILE END
RETURN (COUNTER);
END FUNCTION
I editied this answer after the comment of Abdulhakeem Apr 26 at 3:36, because previsouly I posted the wrong one.
answered Apr 25 '17 at 21:35
RajRaj
11
That is not what you have asked. This is the mere BFS algorithm which finds the distance of all vertices of graph G from a source vertex. DIST is an array of values, you need to do one extra O(V) (V is the number of vertices in graph G) to find the max value from DIST which will be the depth of the tree. So if you want to find the depth of tree in just O(V+E), I would say the other approach is more efficient.
– Abdulhakeem
Apr 26 '17 at 3:36
Hello, Thank you for your comment, i just corrected my answer, i posted the wrong one. Now its correct normally.
– Raj
May 6 '17 at 10:55
add a comment |
With my friend we found this solution :
FUNCTION BFS(G,s)
BEGIN
FOR any vertex v of G
DO Mark[v] ← False
END FOR Mark[s] ← True
F ← Empty Queue
DIST ← Empty Tab
COUNTER = 0
enqueue(s,F)
WHILE F is not empty
DO v ← dequeue(F)
DIST[v] ← 0
FOR any vertex w neighbor of v
DO
IF Mark[w] = False THEN
Mark[w] ← True;
enqueue(w,F)
DIST[w] ← DIST[v] + 1
IF [COUNTER < DIST[w]] THEN
COUNTER = DIST[w];
END IF
END IF
FOR END
WHILE END
RETURN (COUNTER);
END FUNCTION
I editied this answer after the comment of Abdulhakeem Apr 26 at 3:36, because previsouly I posted the wrong one.
answered Apr 25 '17 at 21:35
RajRaj
11
That is not what you have asked. This is the mere BFS algorithm which finds the distance of all vertices of graph G from a source vertex. DIST is an array of values, you need to do one extra O(V) (V is the number of vertices in graph G) to find the max value from DIST which will be the depth of the tree. So if you want to find the depth of tree in just O(V+E), I would say the other approach is more efficient.
– Abdulhakeem
Apr 26 '17 at 3:36
Hello, Thank you for your comment, i just corrected my answer, i posted the wrong one. Now its correct normally.
– Raj
May 6 '17 at 10:55
add a comment |
With my friend we found this solution :
FUNCTION BFS(G,s)
BEGIN
FOR any vertex v of G
DO Mark[v] ← False
END FOR Mark[s] ← True
F ← Empty Queue
DIST ← Empty Tab
COUNTER = 0
enqueue(s,F)
WHILE F is not empty
DO v ← dequeue(F)
DIST[v] ← 0
FOR any vertex w neighbor of v
DO
IF Mark[w] = False THEN
Mark[w] ← True;
enqueue(w,F)
DIST[w] ← DIST[v] + 1
IF [COUNTER < DIST[w]] THEN
COUNTER = DIST[w];
END IF
END IF
FOR END
WHILE END
RETURN (COUNTER);
END FUNCTION
I editied this answer after the comment of Abdulhakeem Apr 26 at 3:36, because previsouly I posted the wrong one.
answered Apr 25 '17 at 21:35
RajRaj
11
With my friend we found this solution :
FUNCTION BFS(G,s)
BEGIN
FOR any vertex v of G
DO Mark[v] ← False
END FOR Mark[s] ← True
F ← Empty Queue
DIST ← Empty Tab
COUNTER = 0
enqueue(s,F)
WHILE F is not empty
DO v ← dequeue(F)
DIST[v] ← 0
FOR any vertex w neighbor of v
DO
IF Mark[w] = False THEN
Mark[w] ← True;
enqueue(w,F)
DIST[w] ← DIST[v] + 1
IF [COUNTER < DIST[w]] THEN
COUNTER = DIST[w];
END IF
END IF
FOR END
WHILE END
RETURN (COUNTER);
END FUNCTION
I editied this answer after the comment of Abdulhakeem Apr 26 at 3:36, because previsouly I posted the wrong one.
answered Apr 25 '17 at 21:35
RajRaj
11
edited May 6 '17 at 10:54
answered Apr 25 '17 at 21:35
RajRaj
11
answered Apr 25 '17 at 21:35
RajRaj
11
answered Apr 25 '17 at 21:35
RajRaj
11
11
That is not what you have asked. This is the mere BFS algorithm which finds the distance of all vertices of graph G from a source vertex. DIST is an array of values, you need to do one extra O(V) (V is the number of vertices in graph G) to find the max value from DIST which will be the depth of the tree. So if you want to find the depth of tree in just O(V+E), I would say the other approach is more efficient.
– Abdulhakeem
Apr 26 '17 at 3:36
Hello, Thank you for your comment, i just corrected my answer, i posted the wrong one. Now its correct normally.
– Raj
May 6 '17 at 10:55
add a comment |
That is not what you have asked. This is the mere BFS algorithm which finds the distance of all vertices of graph G from a source vertex. DIST is an array of values, you need to do one extra O(V) (V is the number of vertices in graph G) to find the max value from DIST which will be the depth of the tree. So if you want to find the depth of tree in just O(V+E), I would say the other approach is more efficient.
– Abdulhakeem
Apr 26 '17 at 3:36
Hello, Thank you for your comment, i just corrected my answer, i posted the wrong one. Now its correct normally.
– Raj
May 6 '17 at 10:55
That is not what you have asked. This is the mere BFS algorithm which finds the distance of all vertices of graph G from a source vertex. DIST is an array of values, you need to do one extra O(V) (V is the number of vertices in graph G) to find the max value from DIST which will be the depth of the tree. So if you want to find the depth of tree in just O(V+E), I would say the other approach is more efficient.
– Abdulhakeem
Apr 26 '17 at 3:36
That is not what you have asked. This is the mere BFS algorithm which finds the distance of all vertices of graph G from a source vertex. DIST is an array of values, you need to do one extra O(V) (V is the number of vertices in graph G) to find the max value from DIST which will be the depth of the tree. So if you want to find the depth of tree in just O(V+E), I would say the other approach is more efficient.
– Abdulhakeem
Apr 26 '17 at 3:36
Hello, Thank you for your comment, i just corrected my answer, i posted the wrong one. Now its correct normally.
– Raj
May 6 '17 at 10:55
Hello, Thank you for your comment, i just corrected my answer, i posted the wrong one. Now its correct normally.
– Raj
May 6 '17 at 10:55
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%2f43458102%2fhow-to-get-the-max-depth-of-a-graph-with-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
What kind of graph is this and how do you define this maximum depth?
– gue
Apr 20 '17 at 8:55
Hello, I posted an answer just below.
– Raj
Apr 25 '17 at 21:35