Performant way to find all leaf nodes in a undirected graph

Question

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

2. 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))
        {
            leaves.Add(nodes);
            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?

Answer 1

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.