图论matlab代码整理
时间: 2023-07-02 17:05:37 浏览: 41
以下是一些常用的图论算法的 MATLAB 代码示例:
1. 深度优先搜索(DFS)
```matlab
function DFS(G, i, visited)
visited(i) = true;
fprintf('%d ', i);
neighbors = G(i, :);
for j = 1:length(neighbors)
if neighbors(j) == 1 && ~visited(j)
DFS(G, j, visited);
end
end
end
% 示例
G = [0 1 1 0;
1 0 0 1;
1 0 0 1;
0 1 1 0];
visited = false(1, size(G, 1));
DFS(G, 1, visited);
```
2. 广度优先搜索(BFS)
```matlab
function BFS(G, i, visited)
queue = i;
visited(i) = true;
while ~isempty(queue)
node = queue(1);
queue(1) = [];
fprintf('%d ', node);
neighbors = G(node, :);
for j = 1:length(neighbors)
if neighbors(j) == 1 && ~visited(j)
visited(j) = true;
queue(end+1) = j;
end
end
end
end
% 示例
G = [0 1 1 0;
1 0 0 1;
1 0 0 1;
0 1 1 0];
visited = false(1, size(G, 1));
BFS(G, 1, visited);
```
3. 最短路径算法(Dijkstra)
```matlab
function [dist, path] = Dijkstra(G, s)
n = size(G, 1);
unvisited = ones(1, n);
dist = Inf(1, n);
dist(s) = 0;
path = zeros(1, n);
while any(unvisited)
[~, u] = min(dist .* unvisited);
unvisited(u) = 0;
neighbors = find(G(u, :));
for v = neighbors
if unvisited(v) && dist(v) > dist(u) + G(u,v)
dist(v) = dist(u) + G(u,v);
path(v) = u;
end
end
end
end
% 示例
G = Inf(5, 5);
G(1,2) = 7; G(1,3) = 9; G(1,6) = 14;
G(2,1) = 7; G(2,3) = 10; G(2,4) = 15;
G(3,1) = 9; G(3,2) = 10; G(3,4) = 11; G(3,6) = 2;
G(4,2) = 15; G(4,3) = 11; G(4,5) = 6;
G(5,4) = 6; G(5,6) = 9;
G(6,1) = 14; G(6,3) = 2; G(6,5) = 9;
[dist, path] = Dijkstra(G, 1);
```
4. 最小生成树算法(Prim)
```matlab
function [T, cost] = Prim(G)
n = size(G, 1);
T = zeros(n, n);
visited = false(1, n);
visited(1) = true;
for i = 1:n-1
min_edge = Inf;
for j = find(visited)
neighbors = find(G(j, :) & ~visited);
for k = neighbors
if G(j,k) < min_edge
min_edge = G(j,k);
u = j;
v = k;
end
end
end
T(u,v) = min_edge;
T(v,u) = min_edge;
visited(v) = true;
end
cost = sum(T(:));
end
% 示例
G = [Inf 2 3 Inf Inf;
2 Inf 5 1 Inf;
3 5 Inf 4 6;
Inf 1 4 Inf 3;
Inf Inf 6 3 Inf];
[T, cost] = Prim(G);
```
5. 最短路径算法(Floyd)
```matlab
function dist = Floyd(G)
n = size(G, 1);
dist = G;
for k = 1:n
for i = 1:n
for j = 1:n
if dist(i,k) + dist(k,j) < dist(i,j)
dist(i,j) = dist(i,k) + dist(k,j);
end
end
end
end
end
% 示例
G = [0 5 Inf Inf 9 Inf;
5 0 2 Inf 7 Inf;
Inf 2 0 3 6 4;
Inf Inf 3 0 Inf Inf;
9 7 6 Inf 0 8;
Inf Inf 4 Inf 8 0];
dist = Floyd(G);
```