2

假设我有一个矩阵

0 -1  0  0
0  0 -1  0
0  0  0  0
0  0 -1 -1

所以在这种情况下 矩阵表示： 在此处输入图像描述

0 已连接，-1 未连接 如何从中获取邻接矩阵？

我知道

h[i][j] = 0, if there is no direct link from i to j 
(i and j are not neighbors)
h[i][j] = 1, if there is a direct link from i to j 
(i and j are neighbors)

所以我正在做类似的事情：

Int32[,] original = new int[4, 4]
{
  {0, -1,  0,  0},
  {0,  0, -1,  0},
  {0,  0,  0,  0},
  {0,  0, -1, -1}
}

Int32[,] adjacent;
for (int i = 0; i < original.GetLength(0); i++){
    for (int j = 0; j < original.GetLength(1); j++) {
         //How to know if there is direct link from i to j 
         //if(){
         //   adjacent[i,j]=0;
         //}else{
         //   adjacent[i,j]=1;
         //}
    }
 }
4

2 回答 2

2

原始代码有一个问题 - 矩阵adjacent通常original大小不同。

但在某种程度上，它很接近。

代码未测试：

int size = original.GetLength(0) * original.GetLength(1);
int[,] adjacent = new int[size, size];
for (int i = 0; i < original.GetLength(0); i++) {
    for (int j = 0; j < original.GetLength(1); j++) {
        if (original[i, j] == 0) {
            // up/down
            if (j > 0 && original[i, j - 1] == 0) {
                adjacent[remap(i, j), remap(i, j - 1)] = 1;
                adjacent[remap(i, j - 1), remap(i, j)] = 1;
            }
            // left/right
            if (i > 0 && original[i - 1, j] == 0) {
                adjacent[remap(i, j), remap(i - 1, j)] = 1;
                adjacent[remap(i - 1, j), remap(i, j)] = 1;
            }
        }
    }
 }

remap将 2D 点映射到“节点索引”。它可能需要更多的论据。它可能是这样的：

int remap(int i, int j, int width)
{
    return width * i + j;
}

还有其他可能性，但这是最简单的。

于 2013-09-18T22:18:16.017 回答
1

正如@harold 已经说过的，邻接矩阵是带有节点的图n的矩阵（参见此处的示例）。因此，您需要在网格中节点的物理坐标和介于和之间的节点编号之间进行映射。nn(i,j)0n-1

这是一些正确的代码。我查看了调试器中的输出并检查了前几行，它看起来没问题。

class Program
{
    static void AddToAdjacencyMatrix(Int32[,] adjacency, Int32[,] original,
        Dictionary<Tuple<int, int>, int> coordinate2NodeNum,
        Tuple<int, int> fromCoord, int deltaX, int deltaY)
    {
        Tuple<int, int> toCoord = new Tuple<int, int>(
            fromCoord.Item1 + deltaX, fromCoord.Item2 + deltaY);
        try { // quick and dirty way of catching out of range coordinates
            if (original[toCoord.Item1,toCoord.Item2] == 0) {
                int fromNodeNum = coordinate2NodeNum[fromCoord];
                int toNodeNum = coordinate2NodeNum[toCoord];
                adjacency[fromNodeNum, toNodeNum] = 1;
                adjacency[toNodeNum, fromNodeNum] = 1;
            }
        }
        catch {
        }
    }

    static void Main(string[] args)
    {
        Int32[,] original = new int[4, 4]  
        {
          {0, -1,  0,  0},
          {0,  0, -1,  0},
          {0,  0,  0,  0},
          {0,  0, -1, -1}
        };

        // Adjacency matrix has column and row headings for each node in graph
        // Therefore we need to map between the node number in the adjacency matrix
        // (i.e. the column or row heading) and the physical grid coordinates
        Dictionary<int, Tuple<int, int>> nodeNum2Coordinate = new Dictionary<int, Tuple<int, int>>();
        Dictionary<Tuple<int, int>, int> coordinate2NodeNum = new Dictionary<Tuple<int, int>, int>();
        int nodeCount = 0;
        for (int i = 0; i < original.GetLength(0); i++){
            for (int j = 0; j < original.GetLength(1); j++) {
                if (original[i, j] == 0) {
                    Tuple<int, int> coord = new Tuple<int, int>(i,j);
                    nodeNum2Coordinate.Add(nodeCount, coord);
                    coordinate2NodeNum.Add(coord, nodeCount);
                    nodeCount++;
                }
            }
        }

        // Now create the adacency matrix
        Int32[,] adjacency = new int[nodeCount, nodeCount];
        for (int i = 0; i < original.GetLength(0); i++){
            for (int j = 0; j < original.GetLength(1); j++) {
                if (original[i, j] == 0) {
                    Tuple<int, int> fromCoord = new Tuple<int, int>(i,j);
                    // Check connections
                    AddToAdjacencyMatrix(adjacency, original, coordinate2NodeNum, fromCoord,
                        -1, 0); // UP
                    AddToAdjacencyMatrix(adjacency, original, coordinate2NodeNum, fromCoord,
                        +1, 0); // DOWN
                    AddToAdjacencyMatrix(adjacency, original, coordinate2NodeNum, fromCoord,
                        0, -1); // LEFT
                    AddToAdjacencyMatrix(adjacency, original, coordinate2NodeNum, fromCoord,
                        0, +1); // UP
                }
            }
        }
        Console.ReadLine();
    }
}
于 2013-09-18T22:29:49.507 回答