Nay*_*Cey 5 language-agnostic algorithm graph-theory graph depth-first-search
我正在尝试从以下论文中实现（未加权）反馈顶点集近似算法：FVS-Approximation-Paper。算法的步骤之一（在第4页上进行描述）是计算输入图的最大2-3个子图。
确切地说，2-3图是仅具有度顶点为2或3的图。
“最大值”是指在不违反2-3个条件的情况下，无法将原始图的一组边或顶点添加到最大子图中。
该论文的作者声称，可以通过图形上的“简单深度优先搜索（DFS）”来执行计算。但是，这种算法似乎使我难以理解。如何计算最大子图？
我想我设法弄清楚了作者的意图。但我不会说这很简单。
设 G 为图，H 为 G 的最初为空的 2-3 子图。该算法与深度优先遍历非常相似，但我不会这样称呼它。从任意节点开始，我们在图中四处走动，将步骤推入堆栈。每当我们检测到堆栈包含构成 H 的 2-3 超图的路径/循环/西格玛形状时，我们就把它从堆栈移动到 H 并继续。当不再可能找到这样的形状时，H 最大，我们就完成了。
更详细地，堆栈通常由H中不具有3阶节点的路径组成。光标位于该路径的一端。在每一步中，我们都会检查与末端相关的下一条边。如果唯一的入射边是我们到达的那条边，我们将它从 G 和堆栈中删除，并将末端移回一位。否则我们可以将路径延长一些边 e。如果 e 的另一个端点在 H 中的度数为 3，则我们从 G 中删除 e 并考虑与该端点相关的下一条边。如果 e 的另一个端点在 H 中的度数为 2，但当前不在堆栈上，那么我们已经锚定了该端点。如果另一端也被锚定，则将堆栈路径添加到 H 并继续。否则，将光标移动到堆栈的另一端，反转堆栈。最后一种情况是堆栈自行循环。然后我们可以提取路径/循环/西格玛并继续。
在手机上输入此内容，对于简洁的描述感到抱歉。也许我会找时间来实现它。