开发者

how to find leaves of a tree

There开发者_如何学Python is a problem that wants to find the center of a tree and I want to delete the leaves until there are more than 2 vertices. But how can I find the leaves ?

PS sorry for my English


Edit: I have just seen you probably have a rooted tree. You can make a DFS of the tree and when from the current node you don't have an edge to a node different from the parent, then you have found a leaf.

Quoting Wikipedia:

The degree of a vertex in a graph is the number of edges incident to it. An isolated vertex is a vertex with degree zero; that is, a vertex that is not an endpoint of any edge. A leaf vertex (also pendant vertex) is a vertex with degree one.

Just count the degree of every node. If it is 1 then you have a leaf.

0

上一篇:

下一篇:

精彩评论

暂无评论...
验证码 换一张
取 消

最新问答

问答排行榜