MATLAB实现深度优先搜索

在 MATLAB 中，可以使用递归函数实现深度优先搜索。假设我们有一个无向网络，其中点的编号为 1 到 n，边的权重保存在一个 n×n 的矩阵 W 中（如果两个点之间没有边，则 W(i,j)=0）。

具体实现步骤如下：

1. 首先，创建一个布尔型数组 visited，用于记录每个节点是否被访问过。代码如下：

visited = false(1,n);

2. 然后，定义一个递归函数 dfs，用于遍历所有与当前节点相邻的未访问节点。代码如下：

function dfs(node)
    visited(node) = true;
    % 对当前节点的所有相邻节点进行遍历
    for i = 1:n
        if W(node,i) ~= 0 && ~visited(i)
            % 如果相邻节点未被访问，则递归调用 dfs 函数
            dfs(i);
        end
    end
end

其中，node 表示当前节点的编号，W(node,i) 表示节点 node 和节点 i 之间的边权重。

3. 最后，调用 dfs 函数遍历所有未访问节点。代码如下：

for i = 1:n
    if ~visited(i)
        dfs(i);
    end
end

完整代码如下：

visited = false(1,n);

function dfs(node)
    visited(node) = true;
    % 对当前节点的所有相邻节点进行遍历
    for i = 1:n
        if W(node,i) ~= 0 && ~visited(i)
            % 如果相邻节点未被访问，则递归调用 dfs 函数
            dfs(i);
        end
    end
end

for i = 1:n
    if ~visited(i)
        dfs(i);
    end
end

需要注意的是，以上代码只能遍历整个连通块。如果需要遍历整个无向网络，需要在外层增加一个循环遍历所有连通块。