在matlab导入坐标点并用prim算法找出最小生成树,并用邻接矩阵表示出来
时间: 2023-11-07 12:59:10 浏览: 35
假设已经将坐标点存储在一个n行2列的矩阵中,每行代表一个坐标点的横纵坐标。可以使用以下代码来实现prim算法找出最小生成树并用邻接矩阵表示出来:
```matlab
% 导入坐标点
points = importdata('points.txt');
n = size(points, 1); % 坐标点数量
adjMat = zeros(n, n); % 邻接矩阵
visited = zeros(n, 1); % 记录节点是否已经访问过
% 计算各点之间的距离
dists = pdist(points);
% 将距离转化为邻接矩阵
for i = 1:n
for j = i+1:n
dist = dists((i-1)*(n-i/2)+j-i);
adjMat(i, j) = dist;
adjMat(j, i) = dist;
end
end
% prim算法找出最小生成树
visited(1) = 1; % 从第一个点开始
while sum(visited) < n
minDist = Inf;
for i = 1:n
if visited(i) == 1
% 找到已经访问过的节点与未访问过节点之间的最小距离
for j = 1:n
if visited(j) == 0 && adjMat(i, j) > 0 && adjMat(i, j) < minDist
minDist = adjMat(i, j);
minNode = j;
fromNode = i;
end
end
end
end
visited(minNode) = 1;
adjMat(fromNode, minNode) = 0;
adjMat(minNode, fromNode) = 0;
adjMat(fromNode, fromNode) = -1;
end
% 输出邻接矩阵
disp(adjMat);
```
其中,points.txt文件为存储坐标点的文件,每行两个数字表示一个坐标点的横纵坐标。该代码会输出一个n*n的邻接矩阵,其中值为0表示两个点之间没有边,值为正整数表示两个点之间的边权重。需要注意的是,如果两个点之间没有边,则距离应该被设为0而非Inf,因为prim算法中需要找到已经访问过的节点与未访问过节点之间的最小距离。因此,当两个点之间没有边时,应将邻接矩阵中的距离设为0。