查找图中所有叶子节点

Question

我有一个函数可以确定一个节点是否是叶子。

我将叶子定义为不属于图中循环的节点。

一个例子：

叶节点用红色箭头标示，不属于循环。

在我找到图中的所有循环之前，我首先想消除检查这些叶节点以优化我的算法的需要。

我当前的方法不会遍历以查找节点是否为叶节点，因为我不确定如何去做，我有一个基本检查，如下所示：

    private static bool IsLeafNode(Node node)
    {
        int TotalLeafs(Node node)
        {
            int j = 0;
            for (int i = 0; i < node.Nodes.Count; i++){
                Node n = node.Nodes[i];
                j += n.Nodes.Count == 1 ? 1 : 0; //if leaf add 1
            }
            return j;
        }

//has 1 connection OR all its connections lead to nodes that have 1 connection
        return node.ConnectionCount == 1 || TotalLeafs(node) == node.Nodes.Count;
    }

这里的问题是没有考虑到有2个连接的两个叶节点（但是很明显还是叶节点）

我该如何消除所有叶节点？

Answer 1

根据 Hayden 的说明，这个问题的本质是递归的，这是一个多么无用的陈述，但是.. 仍然让我感到震惊...

考虑下图，让我你提交这个初步提案，

决定是或否，节点 (1) 是一片叶子（如您定义的），我将从它的每个子节点 (2), (5) 执行深度优先遍历，忽略到（1）的边，并且 DFS 将简单地 return 所有找到的节点，如果这些列表不包含边 1，我可以声明没有其他路径从 1 返回到 1，因此没有循环。

一旦我们就此达成一致，那么也许会有一个更强大的提案...... 当从任何地方执行 DFS 遍历时，节点堆栈定义了通过这些节点的当前路径，...因此，无论何时我们前往已经在该堆栈上的节点，我们都会找到一个循环 -> 所有这些节点都是循环的一部分，因此必须排除在“叶子”

Answer 2

您可以从已知叶子开始进行反向搜索，然后递归检查它们的邻居是否也是叶子。但是每次检查连接数时，您都必须“删除”您已经认为是叶子的节点。如果得到的连接数为零或一，则您找到了一片叶子。该算法可能如下所示：

创建一个新的空 Set 叶子，名为 foundLeaves。
在你的图中找到所有“真正的”叶子，它们只有一个连接。将它们放在名为 leavesToCheck.

Set

虽然 leavesToCheck 集合不为空：
- 从 leavesToCheck 中选择并删除一个节点。
- 检查此节点拥有的连接数，减去已经在 foundLeaves 集合中的节点：
  - 当连接数为零或一时：您找到了一片叶子。将找到的叶子添加到 foundLeaves 中，并将该节点的邻居（如果有的话）添加到 leavesToCheck 集合中以供将来检查。
  - 当连接数大于等于2时：什么都不做。

最终，leavesToCheck 集变空了。那时 foundLeaves 集包含所有节点，根据您的定义，这些节点被视为叶子并且没有循环。

当然，您可以为 foundLeaves 和 leavesToCheck 集合使用其他数据结构，例如列表或队列。如果您的总体 goal/algorithm 支持您可以从图中删除叶节点，则可以这样做。这样你就不需要 foundLeaves 列表。

Answer 3

查找属于循环的节点是文献中定义明确的问题，因此这可能是一个简单的起点。

A bridge of a graph is an edge whose removal increases the number of components 的图表。所以根据定义，作为桥的边不能是循环的一部分。

为了找到您的目标节点，您可以：

拆除所有桥梁。这将删除所有不属于循环的边缘。寻找桥梁的著名算法之一是 Tarjan's algorithm.
找到没有任何附加边的节点。这些是不属于任何循环的节点。

查找图中所有叶子节点

Find all nodes that are a leaf in a graph

c#

graph-theory