深度优先搜索算法matlab
时间: 2023-09-06 15:12:51 浏览: 43
深度优先搜索算法(DFS)是一种基于栈的搜索算法,用于遍历或搜索树或图的所有节点。在Matlab中实现DFS,可以使用递归或循环方式实现。
以下是一个基于递归方式实现DFS的Matlab代码示例:
```matlab
function DFS(graph, start_node, visited)
% graph: 图的邻接矩阵表示
% start_node: 起始节点
% visited: 标记节点是否已访问的数组
% 标记当前节点为已访问
visited(start_node) = true;
fprintf('%d ', start_node);
% 遍历相邻节点
for i = 1:length(graph)
if graph(start_node, i) == 1 && ~visited(i)
DFS(graph, i, visited);
end
end
end
```
调用以上函数时,需要传入图的邻接矩阵表示、起始节点和一个数组用于标记节点是否已访问。例如,对于下面的图:
```
1 -- 2 -- 3
| |
4---------5
```
邻接矩阵表示为:
```
0 1 1 1 0
1 0 1 0 1
1 1 0 0 1
1 0 0 0 1
0 1 1 1 0
```
可以使用以下代码调用DFS函数:
```matlab
graph = [0 1 1 1 0; 1 0 1 0 1; 1 1 0 0 1; 1 0 0 0 1; 0 1 1 1 0];
visited = false(1, length(graph));
DFS(graph, 1, visited);
```
输出结果为:
```
1 2 3 5 4
```