从最近邻居搜索创建邻接矩阵. (将邻接列表转换为邻接矩阵)-Matlab [英] Create adjacency matrix from nearest neighbour search. (convert adjacency list to adjacency matrix) - Matlab

问题描述

我有一个矩阵2000x5，在第一列中是点号，在第2-5列中有4个邻居(如果没有邻居，则为0).有没有一种有效的方法可以据此创建邻接矩阵?

I have a matrix 2000x5, in the first column the point number, and in columns 2-5 the 4 neighbours (0s if there isnt a neighbour). Is there an efficient way to create an adjacency matrix out of this ?

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邻接表到邻接矩阵

I found the following thread, where it is explained for just one neighbour, but I am not sure how to use it for multiple neighbours. matlab adjacency list to adjacency matrix

非常感谢您的帮助.

推荐答案

一种快速简单的技术:

adjMat = zeros(size(A,1));
for ind = 1:size(A,1)
    % Flag 1 on each row 'ind' at the indices mentioned in col 2-5
    adjMat(ind, nonzeros(A(ind,2:end))) = 1;
end

由于您已经提到使用最近的邻居搜索，因此邻接表很可能应该被完全填充以产生无向图，也就是说，如果第1行有20个邻居，那么第20行很可能有1个邻居作为邻居.

Since you have mentioned using the nearest neighbour search, it is likely that the adjacency list should be completely filled to result in a undirected graph, in the sense that if row 1 has 20 as a neighbour, row 20 very likely has 1 as a neighbour.

但是，从技术上讲，这将产生与邻接表完全等效的邻接矩阵，而无需单独假设.

However technically speaking, this will produce an adjacency matrix exactly equivalent to the adjacency list, assuming nothing by itself.

示例:

有关邻接表

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

A =

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

结果是:

adjMat =

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

---

P.S.要强制无向 -ness，您只需在for循环主体中添加另一条语句即可:

---

P.S. To force undirected-ness, you can simply add another statement in the for loop body:

adjMat(nonzeros(A(ind,2:end)),ind) = 1;

这将确保邻接矩阵是对称的，这是无向图的特征.

This will ensure that the adjacency matrix will be symmetric, which is a characteristic of undirected graphs.

这篇关于从最近邻居搜索创建邻接矩阵. (将邻接列表转换为邻接矩阵)-Matlab的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！