图论matlab代码整理
时间: 2023-06-16 22:03:46 浏览: 35
以下是一些基本的图论算法的Matlab代码实现:
## 图的邻接矩阵表示法
```matlab
% 建立一个邻接矩阵
n = 5;
A = zeros(n);
A(1,2) = 1;
A(2,1) = 1;
A(2,3) = 1;
A(3,2) = 1;
A(3,4) = 1;
A(4,3) = 1;
A(4,5) = 1;
A(5,4) = 1;
% 输出邻接矩阵
disp('邻接矩阵:');
disp(A);
```
## 图的深度优先遍历算法
```matlab
function DFS(v, A, visited)
% v:当前遍历的顶点
% A:邻接矩阵
% visited:已经访问过的顶点
% 标记当前顶点已经访问
visited(v) = true;
% 输出当前顶点
disp(v);
% 遍历与当前顶点相邻的所有顶点
for i = 1:size(A,1)
if A(v,i) == 1 && ~visited(i)
DFS(i, A, visited);
end
end
end
% 测试
A = [0 1 0 1 0;
1 0 1 0 0;
0 1 0 1 1;
1 0 1 0 1;
0 0 1 1 0];
visited = zeros(size(A,1),1);
DFS(1, A, visited);
```
## 图的宽度优先遍历算法
```matlab
function BFS(s, A)
% s:起始顶点
% A:邻接矩阵
% 初始化
queue = [s];
visited = zeros(size(A,1),1);
visited(s) = 1;
% 遍历队列
while ~isempty(queue)
v = queue(1);
queue(1) = [];
disp(v);
% 遍历与当前顶点相邻的所有顶点
for i = 1:size(A,1)
if A(v,i) == 1 && visited(i) == 0
visited(i) = 1;
queue = [queue i];
end
end
end
end
% 测试
A = [0 1 0 1 0;
1 0 1 0 0;
0 1 0 1 1;
1 0 1 0 1;
0 0 1 1 0];
BFS(1, A);
```
## 最短路径算法(Dijkstra算法)
```matlab
function [dist, path] = dijkstra(s, A)
% s:起始顶点
% A:邻接矩阵
n = size(A,1);
% 初始化
dist = inf(1,n);
dist(s) = 0;
prev = zeros(1,n);
visited = zeros(1,n);
% 遍历所有顶点
while sum(visited) < n
% 找到未访问的顶点中距离最短的一个
[d, u] = min(dist + visited*inf);
visited(u) = 1;
% 遍历与当前顶点相邻的所有顶点
for v = 1:n
if A(u,v) == 1 && visited(v) == 0
alt = dist(u) + 1;
if alt < dist(v)
dist(v) = alt;
prev(v) = u;
end
end
end
end
% 生成路径
path = cell(1,n);
for i = 1:n
if i == s
path{i} = s;
continue
end
p = i;
while p ~= s
path{i} = [prev(p) path{i}];
p = prev(p);
end
path{i} = [s path{i}];
end
end
% 测试
A = [0 1 0 1 0;
1 0 1 0 0;
0 1 0 1 1;
1 0 1 0 1;
0 0 1 1 0];
[s, t] = [1 5];
[dist, path] = dijkstra(s, A);
disp(['从顶点' num2str(s) '到顶点' num2str(t) '的最短距离为:' num2str(dist(t))]);
disp(['最短路径为:' num2str(path{t})]);
```
这些代码只是基本实现,可能还需要根据具体的问题进行修改和优化。