matlab中prim算法代码实例
时间: 2024-03-13 20:41:53 浏览: 19
Prim算法是一种用于求解最小生成树的经典算法,它可以在一个加权连通图中找到一棵包含所有顶点的树,并且使得树的边权重之和最小。
以下是一个使用MATLAB实现Prim算法的代码示例:
```matlab
function MST = primAlgorithm(adjMatrix)
numVertices = size(adjMatrix, 1);
% 初始化小生成树和顶点集合
MST = zeros(numVertices, numVertices);
visited = false(1, numVertices);
% 选择任意一个顶点作为起始点
startVertex = 1;
visited(startVertex) = true;
while sum(visited) < numVertices
minWeight = Inf;
fromVertex = 0;
toVertex = 0;
% 在已访问的顶点中找到与未访问的顶点相连的最小权重边
for i = 1:numVertices
if visited(i)
for j = 1:numVertices
if ~visited(j) && adjMatrix(i, j) < minWeight
minWeight = adjMatrix(i, j);
fromVertex = i;
toVertex = j;
end
end
end
end
% 将找到的边添加到最小生成树中
MST(fromVertex, toVertex) = minWeight;
MST(toVertex, fromVertex) = minWeight;
% 标记已访问的顶点
visited(toVertex) = true;
end
end
```
这段代码实现了Prim算法,输入参数`adjMatrix`是一个邻接矩阵,表示加权连通图的边权重。函数返回一个最小生成树的邻接矩阵`MST`。