在MATLAB中构造邻接矩阵 [英] Construct adjacency matrix in MATLAB
问题描述
考虑一组点，这些点排列在大小为N×M的网格上. 我正在尝试建立邻接矩阵 相邻的点已连接.
Consider a set of points arranged on a grid of size N-by-M. I am trying to build the adjacency matrix such that neighboring points are connected.
例如，在带有图形的3x3网格中:
For example, in a 3x3 grid with a graph:
1-2-3
| | |
4-5-6
| | |
7-8-9
我们应该有相应的邻接矩阵:
We should have the corresponding adjacency matrix:
+---+------------------------------------------------------+
| | 1 2 3 4 5 6 7 8 9 |
+---+------------------------------------------------------+
| 1 | 0 1 0 1 0 0 0 0 0 |
| 2 | 1 0 1 0 1 0 0 0 0 |
| 3 | 0 1 0 0 0 1 0 0 0 |
| 4 | 1 0 0 0 1 0 1 0 0 |
| 5 | 0 1 0 1 0 1 0 1 0 |
| 6 | 0 0 1 0 1 0 0 0 1 |
| 7 | 0 0 0 1 0 0 0 1 0 |
| 8 | 0 0 0 0 1 0 1 0 1 |
| 9 | 0 0 0 0 0 1 0 1 0 |
+---+------------------------------------------------------+
作为奖励，该解决方案应适用于4和8连接的相邻点，即:
As a bonus, the solution should work for both 4- and 8-connected neighboring points, that is:
o o o o
o X o vs. o X o
o o o o
这是我到目前为止的代码:
This the code that I have so far:
N = 3; M = 3;
adj = zeros(N*M);
for i=1:N
for j=1:M
k = sub2ind([N M],i,j);
if i>1
ii=i-1; jj=j;
adj(k,sub2ind([N M],ii,jj)) = 1;
end
if i<N
ii=i+1; jj=j;
adj(k,sub2ind([N M],ii,jj)) = 1;
end
if j>1
ii=i; jj=j-1;
adj(k,sub2ind([N M],ii,jj)) = 1;
end
if j<M
ii=i; jj=j+1;
adj(k,sub2ind([N M],ii,jj)) = 1;
end
end
end
如何进行改进以避免所有循环?
How can this improved to avoid all the looping?
推荐答案
如果您注意到，所创建的邻接矩阵有一个独特的模式.具体来说，它们是对称的，并且绑定.您可以利用这一事实来轻松使用 diag 函数(或 spdiags 函数)制作稀疏矩阵).以下是使用上面的示例矩阵作为示例的每种情况下创建邻接矩阵的方法:
If you notice, there is a distinct pattern to the adjacency matrices you are creating. Specifically, they are symmetric and banded. You can take advantage of this fact to easily create your matrices using the diag function (or the spdiags function if you want to make a sparse matrix). Here is how you can create the adjacency matrix for each case, using your sample matrix above as an example:
mat = [1 2 3; 4 5 6; 7 8 9]; % Sample matrix
[r, c] = size(mat); % Get the matrix size
diagVec1 = repmat([ones(c-1, 1); 0], r, 1); % Make the first diagonal vector
% (for horizontal connections)
diagVec1 = diagVec1(1:end-1); % Remove the last value
diagVec2 = ones(c*(r-1), 1); % Make the second diagonal vector
% (for vertical connections)
adj = diag(diagVec1, 1)+diag(diagVec2, c); % Add the diagonals to a zero matrix
adj = adj+adj.'; % Add the matrix to a transposed copy of
% itself to make it symmetric
您将获得以下矩阵:
adj =
0 1 0 1 0 0 0 0 0
1 0 1 0 1 0 0 0 0
0 1 0 0 0 1 0 0 0
1 0 0 0 1 0 1 0 0
0 1 0 1 0 1 0 1 0
0 0 1 0 1 0 0 0 1
0 0 0 1 0 0 0 1 0
0 0 0 0 1 0 1 0 1
0 0 0 0 0 1 0 1 0
mat = [1 2 3; 4 5 6; 7 8 9]; % Sample matrix
[r, c] = size(mat); % Get the matrix size
diagVec1 = repmat([ones(c-1, 1); 0], r, 1); % Make the first diagonal vector
% (for horizontal connections)
diagVec1 = diagVec1(1:end-1); % Remove the last value
diagVec2 = [0; diagVec1(1:(c*(r-1)))]; % Make the second diagonal vector
% (for anti-diagonal connections)
diagVec3 = ones(c*(r-1), 1); % Make the third diagonal vector
% (for vertical connections)
diagVec4 = diagVec2(2:end-1); % Make the fourth diagonal vector
% (for diagonal connections)
adj = diag(diagVec1, 1)+... % Add the diagonals to a zero matrix
diag(diagVec2, c-1)+...
diag(diagVec3, c)+...
diag(diagVec4, c+1);
adj = adj+adj.'; % Add the matrix to a transposed copy of
% itself to make it symmetric
您将获得以下矩阵:
adj =
0 1 0 1 1 0 0 0 0
1 0 1 1 1 1 0 0 0
0 1 0 0 1 1 0 0 0
1 1 0 0 1 0 1 1 0
1 1 1 1 0 1 1 1 1
0 1 1 0 1 0 0 1 1
0 0 0 1 1 0 0 1 0
0 0 0 1 1 1 1 0 1
0 0 0 0 1 1 0 1 0
这篇关于在MATLAB中构造邻接矩阵的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
