C#基于对象构建可遍历布局/网格的技术方案问询

我尝试创建一个可作为布局的单一对象（支持遍历与查找布局内对象），布局包含Square和Connector两种对象，每个对象通过ID字段与Left、Right、Above、Below等方向属性建立引用。从根对象出发，可通过层级关系遍历找到其他对象，示例逻辑如下：

root = square1
root.Right = connector1
root.Right.Right = square2
root.Right.Right.Right = connector2
root.Right.Right.Right.Right = square3

root.Right.Left = square1
root.Right.Right.Left = connector1

我认为对象的交替方向（左→右、上→下等）对应网格布局的前后项，曾考虑使用BFS算法，但当前实现的BuildLayout方法不符合预期，也未采用BFS，现寻求可行方案建议或同类问题参考。

当前代码实现 #

Main方法 #

public void Main()
{
    LayoutObject connector1 = new LayoutObject(){ID = 1, TYPE="Connector", Left = square1, Right = square2, Above = null, Below = null};
    LayoutObject connector2 = new LayoutObject(){ID = 2, TYPE="Connector", Left = square2, Right = square3, Above = null, Below = null};

    LayoutObject square1 = new LayoutObject(){ID = 1, TYPE="Square", Left = null, Right = connector1, Above = null, Below = null};
    LayoutObject square2 = new LayoutObject(){ID = 2, TYPE="Square", Left = connector1, Right = connector2, Above = null, Below = null};
    LayoutObject square3 = new LayoutObject(){ID = 3, TYPE="Square", Left = connector2, Right = null, Above = null, Below = null};
    
    List<LayoutObject> objects = new List<LayoutObject>();
    objects.Add(square1);
    objects.Add(square2);
    objects.Add(square3);
    objects.Add(connector1);
    objects.Add(connector2);

    //This sets the first square in the layout
    LayoutObject root = new LayoutObject();
    root.Right = square1.Right;
    root.Left = square1.Left;
    root.Above = square1.Above;
    root.Below = square1.Below;
    
    root = BuildLayout(root, objects);
}

BuildLayout方法 #

private LayoutObject BuildLayout(LayoutObject root, List<LayoutObject> objects)
{
    if (root == null) return null;
    foreach (var neighbor in root.GetNeighbors())
    {
        if (neighbor == null) continue;
        if (root.Left != null && neighbor.Right != null && root.Left.ID == neighbor.Right.ID) root.Left.Left = neighbor.Right;
        if (root.Right != null && neighbor.Left != null && root.Right.ID == neighbor.Left.ID) root.Right.Right = neighbor.Left;
        if (root.Above != null && neighbor.Below != null && root.Above.ID == neighbor.Below.ID) root.Above.Above = neighbor.Below;
        if (root.Below != null && neighbor.Above != null && root.Below.ID == neighbor.Above.ID) root.Below.Below = neighbor.Above;
        BuildLayout(root.Left.Left, objects);
        BuildLayout(root.Right.Right, objects);
        BuildLayout(root.Above.Above, objects);
        BuildLayout(root.Below.Below, objects);
    };
}

LayoutObject类 #

public class LayoutObject
{
    public string TYPE { get; set; }
    public string ID { get; set; }
    public LayoutObject Parent { get; set; }
    public LayoutObject Left { get; set; }
    public LayoutObject Right { get; set; }
    public LayoutObject Above { get; set; }
    public LayoutObject Below { get; set; }

    public List<LayoutObject> GetNeighbors()
    {
        return new List<LayoutObject>() { Left, Right, Below, Above };
    }
}

可行方案建议 #

1. 修正对象初始化顺序 #

当前代码中，创建Connector时引用了尚未定义的Square对象，会导致空引用异常。需调整创建顺序：先实例化所有Square，再创建Connector并建立单向引用，最后补全Square的反向引用。

2. 用BFS实现布局引用补全 #

BFS适合层级遍历布局结构，能避免递归深度问题，同时确保每个对象的双向引用正确建立。核心逻辑是维护已访问集合避免重复处理，从根节点出发遍历所有邻居，补全反向引用。

3. 重构后的代码实现 #

public void Main()
{
    // 先创建Square对象
    LayoutObject square1 = new LayoutObject(){ID = "1", TYPE="Square", Left = null, Right = null, Above = null, Below = null};
    LayoutObject square2 = new LayoutObject(){ID = "2", TYPE="Square", Left = null, Right = null, Above = null, Below = null};
    LayoutObject square3 = new LayoutObject(){ID = "3", TYPE="Square", Left = null, Right = null, Above = null, Below = null};
    
    // 创建Connector并建立单向引用
    LayoutObject connector1 = new LayoutObject(){ID = "1", TYPE="Connector", Left = square1, Right = square2, Above = null, Below = null};
    LayoutObject connector2 = new LayoutObject(){ID = "2", TYPE="Connector", Left = square2, Right = square3, Above = null, Below = null};
    
    // 补全Square的反向引用
    square1.Right = connector1;
    square2.Left = connector1;
    square2.Right = connector2;
    square3.Left = connector2;
    
    List<LayoutObject> objects = new List<LayoutObject>(){square1, square2, square3, connector1, connector2};

    // 以square1作为根节点
    LayoutObject root = square1;
    BuildLayout(root);
}

private void BuildLayout(LayoutObject root)
{
    if (root == null) return;
    
    HashSet<LayoutObject> visited = new HashSet<LayoutObject>();
    Queue<LayoutObject> queue = new Queue<LayoutObject>();
    
    queue.Enqueue(root);
    visited.Add(root);
    
    while (queue.Count > 0)
    {
        LayoutObject current = queue.Dequeue();
        
        // 补全Left方向的反向引用
        if (current.Left != null && current.Left.Right != current)
        {
            current.Left.Right = current;
            if (!visited.Contains(current.Left))
            {
                visited.Add(current.Left);
                queue.Enqueue(current.Left);
            }
        }
        
        // 补全Right方向的反向引用
        if (current.Right != null && current.Right.Left != current)
        {
            current.Right.Left = current;
            if (!visited.Contains(current.Right))
            {
                visited.Add(current.Right);
                queue.Enqueue(current.Right);
            }
        }
        
        // 补全Above方向的反向引用
        if (current.Above != null && current.Above.Below != current)
        {
            current.Above.Below = current;
            if (!visited.Contains(current.Above))
            {
                visited.Add(current.Above);
                queue.Enqueue(current.Above);
            }
        }
        
        // 补全Below方向的反向引用
        if (current.Below != null && current.Below.Above != current)
        {
            current.Below.Above = current;
            if (!visited.Contains(current.Below))
            {
                visited.Add(current.Below);
                queue.Enqueue(current.Below);
            }
        }
    }
}

public class LayoutObject
{
    public string TYPE { get; set; }
    public string ID { get; set; }
    public LayoutObject Parent { get; set; }
    public LayoutObject Left { get; set; }
    public LayoutObject Right { get; set; }
    public LayoutObject Above { get; set; }
    public LayoutObject Below { get; set; }

    public List<LayoutObject> GetNeighbors()
    {
        return new List<LayoutObject>() { Left, Right, Below, Above };
    }
}

4. 布局遍历与查找实现 #

完成引用补全后，可通过BFS实现全量遍历和ID查找：

// 遍历所有布局对象
public List<LayoutObject> TraverseLayout(LayoutObject root)
{
    List<LayoutObject> allObjects = new List<LayoutObject>();
    if (root == null) return allObjects;
    
    HashSet<LayoutObject> visited = new HashSet<LayoutObject>();
    Queue<LayoutObject> queue = new Queue<LayoutObject>();
    
    queue.Enqueue(root);
    visited.Add(root);
    
    while (queue.Count > 0)
    {
        LayoutObject current = queue.Dequeue();
        allObjects.Add(current);
        
        foreach (var neighbor in current.GetNeighbors())
        {
            if (neighbor != null && !visited.Contains(neighbor))
            {
                visited.Add(neighbor);
                queue.Enqueue(neighbor);
            }
        }
    }
    
    return allObjects;
}

// 根据ID查找布局对象
public LayoutObject FindObjectById(LayoutObject root, string id)
{
    if (root == null || string.IsNullOrEmpty(id)) return null;
    
    HashSet<LayoutObject> visited = new HashSet<LayoutObject>();
    Queue<LayoutObject> queue = new Queue<LayoutObject>();
    
    queue.Enqueue(root);
    visited.Add(root);
    
    while (queue.Count > 0)
    {
        LayoutObject current = queue.Dequeue();
        if (current.ID == id)
        {
            return current;
        }
        
        foreach (var neighbor in current.GetNeighbors())
        {
            if (neighbor != null && !visited.Contains(neighbor))
            {
                visited.Add(neighbor);
                queue.Enqueue(neighbor);
            }
        }
    }
    
    return null;
}

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