# Performant way to find all leaf nodes in a undirected graph

I am trying to find a better way to find all leaf nodes in my undirected waypoint graph.

This is how I define a leaf node:

A leaf node is a node that is never part of a cycle and so has to meet one of these two criteria:

1. It has only one connection

Or

1. The node's total connections minus the total leaves connected to said node is less than 2

Here is a visual example: My current approach doesn't feel too efficient, I loop through all nodes and mark those nodes that meet criteria 1.

I loop again and again and mark every node that meets criteria 2. I do this until no further nodes are marked - then I exit the function.

Here is the logic:

int count;
do
{
count = 0;
foreach (node in allNodes)
{
//leaves is a hashset of marked nodes
if (leaves.Contains(node)) // already marked as leaf
continue;

if (IsLeaf(node))
{
count = 1;
}
}
} while (count > 0);


My IsLeaf function has:

bool IsLeaf(node)
{
total = node.Connections;

// only has 1 or less connections, so it must be a leaf
if (total < 2)
return true;

//count all leaves connected to the node
totalLeaves = 0;
foreach (segment in node)
{
node2 = segment.GetOtherNode();

if (_leaves.Contains(node2))
totalLeaves ++;
}

//A node is a leaf when it has less than 2 connections to non-leaf nodes
return (total - totalLeaves ) < 2;
}


I am wondering if there is a more performant way to go about this other than looping all the nodes over and over until all leaves have been found?

• I'm not sure I understand the definition of "leaf". Part of the problem might be that you are using standard terminology with a different meaning, and part of the problem is that the definition seems recursive. Can check that the following formal definition is correct? Given a graph $G$ on $n$ vertices, define $L_1$ as the set of vertices of degree $1$. Then, for $i > 1$, iteratively define $L_i$ as a function of $L_{i-1}$. In particular, $L_i$ contains all vertices that have exactly $0$ or $1$ neighbors not in $L_{i-1}$ (notice that $L_i \supseteq L_{i-1}$). A "leaf" is a vertex in $L_n$. Apr 30 at 8:18
• @Steven well i am self taught so i don't know the notation you are using so well, but i presume criteria 2 you are most confused with since criteria 1 is quite obvious? If a node N has 5 connections to other nodes, and 4 of these other nodes are known to be leaf nodes, it must be the case then that N is also a leaf node - that is what criteria 2 basically means. You will find in the image the leaf node that has 5 connections fits this criteria.
– WDUK
Apr 30 at 8:29
• I am trying to say that, since $N$ is a leaf node, this will possibly cause a bunch of other nodes to become leaves too. In turn, these new leaves will create even more leaves, etc... (of course this process of adding leaves will eventually stop). I want to make sure that this is what you intended. Think, for example of a graph that is a path. All the nodes are leaves: Only the endpoints of the path satisfy condition 1, then their neighbors satisfy condition $2$, then their neighbors' neighbors also satisfy condition $2$, and so on until every node becomes a leaf. Apr 30 at 8:32
• Yeah if you mark a leaf its possible the nodes connecting to it will also become leaves as well by the 2nd criteria. My algorithm currently works starting from singularly connected nodes - then works its way "inwards" if that makes sense. It iterates through all the nodes again and again. Which is where I feel the performance could be improved.
– WDUK
Apr 30 at 8:34

You can compute the set of "leaves" in linear time. I will color the vertices of $$G$$ as either white or black. Initially all vertices are white. At the end of the algorithm the leaves will be exactly the vertices colored black. I will additionally associate, to each vertex $$v$$, a quantity $$w(v)$$ representing its "white degree", i.e., the current number of white neighbors of $$v$$. Initially each $$w(v)$$ is initialized to the degree of $$v$$. Finally, we keep a "bucket" (e.g., a list) $$B$$ containing all white vertices $$v$$ such that $$w(v) \le 1$$ (this is initialized to contain all vertices with degree $$0$$ or $$1$$).
The algorithm repeats the following until $$B$$ is empty. It extracts one arbitrary vertex $$v$$ from $$B$$, and colors $$v$$ black. Then, it examines each edge $$(v,u)$$ incident to $$v$$ and decreases $$w(u)$$ by $$1$$. If $$u$$ is white and $$w(u)$$ is now exactly $$1$$ (i.e., the value of $$w(v)$$ just went from $$2$$ to $$1$$), it also adds $$u$$ to $$B$$.
To upper bound the time complexity notice that, except for constant multiplicative and additive factors, it is upper bounded by the number of vertices of $$G$$ (to initialize $$w(\cdot)$$ and $$B$$, and to account for the time spent extracting and inserting each vertex into $$B$$, if needed) plus the overall number of times the edges $$(v,u)$$ are examined. This latter quantity can be at most twice the number of edges of $$G$$.
Edit: (the complement of) what you want has a name. You are interested in the vertices not in the $$2$$-core of $$G$$. Wikipedia even has a similar algorithm to the one above.
• The number of edges examined is in $O(n)$, since there are only $O(n)$ edges outside the 2-core and only those edges have to be examined. So the algorithm runs in linear time $O(n)$ if the degrees $w(v)$ can be determined in $O(1)$ each (not by counting). So in this case, the total running time is in $O(n)$. Apr 30 at 20:49