Tree center(s) | Graph Theory
Вставка
- Опубліковано 5 жов 2024
- How to find the center node(s) of tree
Algorithms repository:
github.com/wil...
Video slides:
github.com/wil...
Video source code:
github.com/wil...
Previous video (rooting a tree): • Rooting a tree | Graph...
Next video (isomorphic trees): • Identifying Isomorphic...
===================================
Practicing for interviews? I have used, and recommend `Cracking the Coding Interview` which got me a job at Google. Link on Amazon: amzn.to/3cvMof5
A lot of the content on this channel is inspired by the book `Competitive Programming` by Steven Halim which I frequently use as a resource and reference. Link on Amazon: amzn.to/3wC2nix
Support me by purchasing the full graph theory course on Udemy which includes additional problems, exercises and quizzes not available on UA-cam:
www.udemy.com/...
I watched this video few months back and was not able to grasp much. But then today as I was solving a few questions on LeetCode related to graphs, I came across this question, LC 310. Minimum Height Trees, where we need to return the possible value of roots so that tree is of minimum height. I gave it a dry run and concluded that I needed centre (s) and as I have watched the video way back, I had some idea that we can find the centre if we want so I watched it again and was able to solve the question. I just wanted to thank you for this series and especially the Github codes. And anyone who is finding this series difficult in first time, do watch his videos twice or thrice.
Thanks for sharing, I'm glad this helped!
Thanks a lot for mentioning the leetcode problem, where I could implement the algorithm and have it tested automatically.
Your solution is basically a multi-source BFS. To make it more explicit, here's a psuedocode using a queue:
function treeCenters(g):
n = g.length
degree = [0]*n
q = Queue()
for (i = 0; i < n; i++):
degree[i] = g[i].length
if degree[i] == 0 or degree[i] == 1:
q.enqueue(i)
degree[i] = 0
count = q.size
while count < n:
for (_ = 0; _ < q.size; _++):
node = q.dequeue()
for neighbor in g[node]:
degree[neighbor]--
if degree[neighbor] == 1:
count++
q.enqueue(neighbor)
degree[node] = 0
return q
The basic idea is to first enqueue all the leaf nodes, prune it, then enqueue all the next layer nodes with the lower degree, etc.
Saw some people wondering why the algorithm terminates at count < n and not count < n-2, so I figured I should post my personal explanation.
I believe it is because count keeps a running total of the amount of nodes that have become/are leaves. When the algorithm removes the current leaf nodes, it finds the newly formed leaf nodes and adds them to the count. Therefore, on the last iteration, when it removes nodes so that only the center nodes are left, the center node(s) will have become leaf nodes. In the case where there is one center, before the removal of the last non-center leaf node, the center will only be connected to one node thereby being a leaf node, and in the case where there are two centers, the centers will be leaf nodes when all other nodes are removed because the centers are connected to each other. In either case, at that point, the running total "count" will be n, terminating the loop.
algorithm terminates at count >= n right? when all nodes have been processed.
Bobbing my head rhythmically at the beginning of every video. Sick intro.
Thanks a lot for ur effort. U really have made all these topics quite simple to understand.
I guess 'degree[i] = 0' (not in if- statement) and 'degree[node] = 0'
are redundant since we aren't using them anywhere.
in case of lc 310, it only worked when i did while count_of_nodes_visited < n - 2:
and not count_of_nodes_visited < n
What would be the time complexity for this algorithm? It seems like the first for-loop that calculates the initial set of leaves is O(V), and the while-loop runs in O(V+E) = O(V + V - 1) = O(V). Thus the overall complexity is just O(V). Is this correct?
Yup
Wow! very clean explanation, Thank you :)
There are two phases in this algorithm: 1. building the degrees(and collecting the first group of leaves). 2. peeling the leaves.
I confused on why aren't the degree[i] = 0 in the building phase and the degree[node] = 0 in the peeling phase are repetitive? Shouldn't only one is needed?
Answer to my own question: because the second assignment can only work on the new leaves, not the initial ones.
Such an amazing problem and an even more amazing explanation. Thanks for such great videos. Just one point, do we really need to set degree[i] = 0 in the first for loop's if condition where we are finding the degree's of the nodes in the graph ( tree ) ? Isn't it being taken care in the while loop by default ? Because in the while loop we are processing the list of nodes with degree 1 (essentially the leaf nodes at each layer) and setting it's degree to 0 after visiting all it's neighbours. Also is this setting required ?
Hi! Thanks for video :-)
Do you take care of already pruned/removed nodes when getting neighbours?
Nodes with degree 0 should be excluded from further processing. Either they should removed from the graph or their degree should be checked when iterating over neighbours. For example we could skip a node if its deg is 0 in the inner for-loop.
Once we have calculated the degree of each node, Is there reason why we cannot just select the node with highest degree as the center? I think I'm missing something here as no one else has asked it. With assumption that I'm storing degree of each node say in a map along with reference to node.
I had this same exact thought. I assume it is because any arbitrary node may have the largest degree, but the key is to understand that the center of a tree is the middle of the longest path. The fact that in this example is it also the node with the highest degree is coincidental. Using the thumbnail image of this video, we can image node labeled as "1" as having 100 neighbors. This would make it the node with the highest degree, however it's not any closer to being the center.
just curious, will there be a condition degree[i] < 0 == true, when all processed? Because you are not checking the degree[neighbor] < 0? I think we are going to process the leaf node again because in degree[neighbor] = degree[neighbor] - 1, the neighbor can be the leaf node we processed before.
I know degree[node] isn't that important, but if trying to give meaning of code, I think it's still important. Thank you.
You’re a legend
Thank you! It is a lot of work to generate such high quality lectures! btw, the
video source code link does not work
Thanks for catching that, just updated it :)
Great video. In 3:27 I think there's no need to do `degree[node] = 0`
I think so to o, however it is used to mark the node done purpose only
hey, I think it is redundant when you put this line "for (neighbor : g[node])" in the loop, your g[node] is a leaf and has already been one neighbor, so you don't need to put it in the loop, people will be confused.
Awesome thank you!
should n't the while condition be
while (count > 2)
instead of
while (count < n) ?
SInce the tree can have atmost 2 centers
Hi, I believe it is because count keeps a running total of the amount of nodes that have become/are leaves. When the algorithm removes the current leaf nodes, it finds the newly formed leaf nodes and adds them to the count. Therefore, on the last iteration, when it removes nodes so that only the center nodes are left, the center node(s) will have become leaf nodes. In the case where there is one center, before the removal of the last non-center leaf node, the center will only be connected to one node thereby being a leaf node, and in the case where there are two centers, the centers will be leaf nodes when all other nodes are removed because the centers are connected to each other. In either case, at that point, the running total "count" will be n, terminating the loop.
If this is a directed graph then what happens
Willaim, thanks a ton for these high quality videos. One question, when a graph represented as an Adjacency List is given and asked to create a Tree out of it. Do we first need to find the center node (this video) and then apply Rooting a Tree algo (previous video) ?? Or my understanding is completely wrong.
It would help if you can elaborate on this, thanks.
Find the center of the tree from the graph then establish tree with that root node will give you a more balance tree than the opposite way.
@@kevintran6102 Thanks buddy !
Could you help to explain why the stop condition is (count < n)? why it's not count < n-2 since we should stop when we get to the last one or two nodes?
Hi, I believe it is because count keeps a running total of the amount of nodes that have become/are leaves. When the algorithm removes the current leaf nodes, it finds the newly formed leaf nodes and adds them to the count. Therefore, on the last iteration, when it removes nodes so that only the center nodes are left, the center node(s) will have become leaf nodes. In the case where there is one center, before the removal of the last non-center leaf node, the center will only be connected to one node thereby being a leaf node, and in the case where there are two centers, the centers will be leaf nodes when all other nodes are removed because the centers are connected to each other. In either case, at that point, the running total "count" will be n, terminating the loop.
You are awesome!
what if there are no leaaf nodes? will you algorithm work then? I think it will not.
So we can find the centre(s) by finding the longest path as well I suppose?
Correct! Both approaches would yield the same result, I just really like this onion peeling approach. I wrote up a quick n fast impl using the longest path method in case you were interested:
github.com/williamfiset/Algorithms/blob/master/src/main/java/com/williamfiset/algorithms/graphtheory/treealgorithms/TreeCenterLongestPathImpl.java
Yeah this is smart , but there is a way faster and easier way to find the center, with the centroid decomposition algorithm which is (n+logn)
please correct me if I am wrong, but will this approach work if there are no leaf nodes initially?like if its a cycle initially.... or after removing some leaves it comes out to a cycle?
If there's a cycle in your tree, then your graph is not a tree.
Can we do this way that we run 3 BFS
In first BFS we select any random node as a source and go the farthest node (as v)
In the second BFS, we go from v to the farthest node once again let's say it is v'.
In the last BFS, we go from v' to v but this time storing all the intermediate nodes in an array and check if the size of array if even this means 2 centers otherwise 1 center.
Kindly check if there is any mistake. It's just an attempt from my side.
You're describing finding the longest path and then retrieving the center(s) of the longest path through the tree. This approach works, but you would only need two BFSs. I implemented this idea (using a DFS instead of a BFS) in case you're interested:
github.com/williamfiset/Algorithms/blob/master/src/main/java/com/williamfiset/algorithms/graphtheory/treealgorithms/TreeCenterLongestPathImpl.java
@@WilliamFiset-videos thanks for correcting me.
Thanks ! Seems like you didn't define what is the center of tree... ;)
I think the center node(s) along the longest path is how the center(s) of a tree is usually defined.
@@WilliamFiset-videos Thanks !
Minimum Height Tree.
Where you are supposed to find root in a given non-cyclic graph(Tree), such that height is minimum
practice problem:leetcode.com/problems/minimum-height-trees/