c# - 将网格 N*N 存储到邻接图中？位置和邻居

Question

再次更新这篇文章。

这次是为了让事情更清楚。我正在尝试在大小为 9x9 的 Grid 中进行解析，但此大小可能会随着时间的推移而变化，而不是固定的。这是一款名为 Quoridor 的棋盘游戏.我所拥有的是一个 Board 类。这为我提供了以下内容，horizo​​ntal bool[,] 和 vertical bool[,]，我可以遍历每个并打印出 x, y位置。但这些不同，取决于它是水平方向，还是垂直方向和位置。

根据方向，玩家可以仅移动一步向北、向南、向西或向东。另一个玩家(人类)可以放置一堵墙(障碍物)，水平或垂直覆盖两个方 block 。我的自动播放器必须从棋盘构建一个节点图，并根据棋盘上的变化和它自己的位置刷新图。例如，如果玩家不能从当前位置向左移动，则连接两个节点的边将被删除，只有在障碍物引起的情况下。然后 BFS 将再次针对图形运行并返回这个(自动)玩家使用并执行其移动的新位置(x，y)。

9x9 网格上的每个 block ，将代表 Graph 中的一个 Node。这意味着 Graph 中的顶点或节点数 List 将为 9x9=81。每个节点都包含一个列表或大小为4的二维数组，用于表示北、South、West 和 East，它们可以是 bool 类型。

现在，我提供了我编写的 Graph 类和 Node 类的示例代码。我希望这里的最新信息能说明问题。我已经实现了 BFS 算法。但这部分是我无法正确理解的。我看了这个视频是为了一些想法:https://www.youtube.com/watch?v=KiCBXu4P-2Y

---

---

代码

class Graph<T>
{        
    private int _V;
    private List<T>[] _Nodes;

    public Graph(int v) 
    {
        _V = v;
        _Nodes = new List<T>[v];
        for (int i = 0; i < _Nodes.Length; i++)
            _Nodes [i] = new List<T>();
    }

    public IEnumerable<T> Nodes(int v) { return (IEnumerable<T>)_Nodes[v];}
    public int V { get => _V; }
    public bool EdgeExists(){}
    public void AddEdge(Node n, T u, T w){}
    public void RemoveEdge(){}
}

和，

class Node<T>
{        
    private int _E;    
    private List<T>[] _Adj;

    public Node(int e) 
    {
        _E = e;
        _Adj = new List<T>[e];
        for (int i = 0; i < _Adj.Length; i++)
            _Adj [e] = new List<T>();
    }

    public IEnumerable<T> Adj(int e) { return (IEnumerable<T>)_Adj[e];}
    public int E { get => _E; }

    public void AddEdge(Node n, T u, T w){}
    public void RemoveEdge(T value){}
}

---

我阅读了以下 SO 线程:

• How can you make an adjacency matrix which would emulate a 2d grid
• Implementing 2D Grid Network ( Graph ) and Adjacency Matrix of it in C
• Representing a graph with a 2D array
• How can I build a graph from a 2D array?
• Creating an adjacency list graph from a matrix in python
• https://learn.microsoft.com/en-us/previous-versions/ms379574(v=vs.80)?redirectedfrom=MSDN
• How can I make my BFS algorithm run faster?

Answer 1

这是构建与二维数组具有相同布局的邻接矩阵的一种方法:

internal record Graph
{
    public List<Node> Nodes { get; set; }

    public Graph(int numberOfTiles)
    {
        var matrixSize = (int)Math.Sqrt(numberOfTiles);
        var rows = matrixSize;
        var columns = matrixSize;
        var nodes = new Node[rows, columns];
        for (int row = 0; row < rows; row++)
        {
            for (int column = 0; column < columns; column++)
            {
                nodes[row, column] = new Node(row, column);
            }
        }

        Nodes = new List<Node>(rows * columns);
        foreach (var node in nodes)
        {
            var row = node.Row;
            var column = node.Column;
            if (row > 0) node.West = nodes[row - 1, column];
            if (column > 0) node.North = nodes[row, column - 1];
            if (row < rows - 1) node.East = nodes[row + 1, column];
            if (column < columns - 1) node.South = nodes[row, column + 1];
            Nodes.Add(node);
        }

    }
}

internal record Node
{
    public int Row { get; }
    public int Column { get; }
    public Node[] Neighbors { get; } = new Node[4];
    public Node North
    {
        get => Neighbors[0];
        set => Neighbors[0] = value;
    }
    public Node East
    {
        get => Neighbors[1];
        set => Neighbors[1] = value;
    }
    public Node South
    {
        get => Neighbors[2];
        set => Neighbors[2] = value;
    }
    public Node West
    {
        get => Neighbors[3];
        set => Neighbors[3] = value;
    }
    public Node(int row, int column)
    {
        Row = row;
        Column = column;
    }
}

这适用于 BFS。边/边界由节点的邻居定义为空。要创建边，只需将适当的邻居设置为空。例如要创建一条水平边，将西节点的东邻居设置为空，将东节点的西邻居设置为空。