如何使用half-edge（半边）数据结构获取指定深度范围的顶点/边

核心问题诊断 #

你当前方案的高开销来源于重复遍历已处理过的顶点和边，每个顶点都全量扫一遍自身邻接，产生了大量冗余迭代，没有做访问去重。

最优实现方案：带深度标记的去重BFS #

这个方案的时间复杂度为O(K)，K为目标深度范围内的总顶点数，没有任何冗余遍历，性能远高于全顶点距离比对，也远高于你当前的复用单顶点邻接查询的方案。
具体实现逻辑如下：

• 用队列管理待遍历的顶点，同时记录每个顶点的当前深度
• 用哈希集合（或顶点结构体的临时标记位）记录已访问过的顶点，避免重复处理
• 只有当前深度小于目标最大深度时，才遍历该顶点的邻接顶点

示例代码 #

// 参数：targetIndex 目标顶点索引，maxDepth 要查询的最大深度（比如示例里的2）
public List<Vertex> GetVertsInDepth(int targetIndex, int maxDepth)
{
    List<Vertex> result = new List<Vertex>();
    // 记录已访问的顶点索引，避免重复添加
    HashSet<int> visited = new HashSet<int>();
    // 队列存储<顶点索引, 当前深度>
    Queue<(int vertIndex, int depth)> processQueue = new Queue<(int, int)>();

    // 初始化：加入目标顶点，深度为0
    processQueue.Enqueue((targetIndex, 0));
    visited.Add(targetIndex);
    result.Add(Vertices[targetIndex]);

    while (processQueue.Count > 0)
    {
        var (currentIdx, currentDepth) = processQueue.Dequeue();
        // 已经到最大深度，不需要再遍历邻接
        if (currentDepth >= maxDepth)
        {
            continue;
        }

        // 直接用半边遍历逻辑查询邻接，避免额外的列表创建开销
        HalfEdge startHE = Vertices[currentIdx].SourceHE;
        HalfEdge currentHE = startHE;
        do
        {
            int neighborIdx = currentHE.Next.SourceVert.Index;
            if (!visited.Contains(neighborIdx))
            {
                visited.Add(neighborIdx);
                processQueue.Enqueue((neighborIdx, currentDepth + 1));
                result.Add(Vertices[neighborIdx]);
            }
            currentHE = currentHE.Twin.Next;
        } while (currentHE != startHE);
    }

    return result;
}

额外优化建议 #

• 如果你的场景拓扑不会频繁变更，可以预计算每个顶点的邻接顶点列表缓存，查询时直接读缓存，不用每次遍历半边，能进一步提升查询速度
• 顶点数量少的场景可以不用HashSet，直接在Vertex结构体里加一个临时的bool访问标记位，查询结束后统一重置，省掉哈希查找的开销
• 如果你需要的是沿指定径向方向的链式顶点（比如你提到的0→1→7→19→37路径），可以在遍历邻接顶点时，计算邻接顶点与目标顶点的方向向量夹角，保留同方向的顶点即可实现链式遍历

内容的提问来源于stack exchange，提问作者niko nemanja