从最近邻搜索中创建邻接矩阵。(将邻接表转换为邻接矩阵)- Matlab

Question

我有一个矩阵2000x5，在第一列中有点号，在列2-5中有4个邻居(如果没有邻居的话是0)。有一个有效的方法来创建一个邻接矩阵吗？

1   129 0   65  0
2   130 0   66  85
3   131 169 67  0
4   132 170 68  87
5   133 0   69  81
6   134 0   70  82
7   135 173 71  83
8   136 174 72  84
9   137 161 73  0
10  138 162 74  93
11  139 163 75  0
12  140 164 76  95
13  141 165 77  89
14  142 166 78  90
15  143 167 79  91
16  144 168 80  92
17  145 0   81  65
18  146 0   82  66
....

我找到了以下线程，其中只解释了一个邻居，但我不知道如何将它用于多个邻居。matlab adjacency list to adjacency matrix

我非常感谢你的帮助。

Answer 1

首先，假设邻接列表是无向。在任何情况下，去多个邻居并不是一件很长的事。首先，您需要从第2列到第5列中检测每行非零元素的总数。一旦这样做，对于邻接矩阵中的行，您将复制点号的次数与每一行有非零元素的次数一样多。repelem函数非常适合您这样做。列索引只是第二列到第五列，删除了所有的零元素的。如何做到这一点首先是转置矩阵，结果是索引第二列到第五列，然后使用logical索引矩阵删除零项。这样做将以一种主要的方式展开您的向量，这就是为什么在执行此操作之前需要换位。完成此操作后，可以创建行和列访问索引，以便将这些索引输入到sparse中，就像您链接的帖子一样。

假设您的矩阵存储在A中，您可以这样做。这还假设连接节点的每个权重为1：

% Find total number of non-zero elements per row, skipping first column
non_zero = sum(A(:,2:end) ~= 0, 2);

% Create row indices
rows = repelem(A(:,1), non_zero);

% Create column indices
cols = A(:,2:end).';    
cols = cols(cols ~= 0);

% Create adjacency matrix
adj = sparse([rows; cols],[cols; rows], 1);

上面的表示是用sparse表示的。如果希望获得完整的数字版本，请使用full强制转换输出。

adj = full(adj);

如果你的图是有向的

如果您有一个有向图而不是一个无向图，那么上面对sparse的调用会重复边，这样您就可以创建每个邻居之间的链接。如果您的图实际上是有向的，那么您只需使用一行和列索引一次，而不是上面代码中的两倍：

% Create adjacency matrix
adj = sparse(rows, cols , 1);

测试用例

这里有一个小测试用例，向您展示这是可行的。假设我的邻接列表如下所示：

>> A = [1 0 2 3; 2 4 0 0; 3 0 0 4]

A =

     1     0     2     3
     2     4     0     0
     3     0     0     4

邻接矩阵现在是：

>> full(adj)

ans =

     0     1     1     0
     1     0     0     1
     1     0     0     1
     0     1     1     0

看看上面的列表，以及如何填充矩阵，我们可以验证这是正确的。

关于repelem的注记

repelem假设您有MATLAB R2015a或更高版本。如果您没有这样的答案，您可以通过用户Divakar查阅repelem的自定义实现：Repeat copies of array elements: Run-length decoding in MATLAB