图论matlab代码整理

以下是一些常见的图论算法的 MATLAB 代码：

1. 深度优先搜索算法

function dfs(graph, start_node, visited)
    visited(start_node) = 1;
    fprintf('%d ', start_node);
    for i=1:size(graph,1)
        if graph(start_node,i) && ~visited(i)
            dfs(graph, i, visited);
        end
    end
end

2. 广度优先搜索算法

function bfs(graph, start_node)
    visited = zeros(size(graph,1),1);
    queue = [start_node];
    visited(start_node) = 1;
    while ~isempty(queue)
        node = queue(1);
        fprintf('%d ', node);
        queue = queue(2:end);
        for i=1:size(graph,1)
            if graph(node,i) && ~visited(i)
                visited(i) = 1;
                queue = [queue i];
            end
        end
    end
end

3. 最短路径算法（Dijkstra算法）

function [dist,path] = dijkstra(graph, start_node, end_node)
    dist = Inf(size(graph,1),1);
    path = zeros(size(graph,1),1);
    visited = zeros(size(graph,1),1);
    dist(start_node) = 0;
    for i=1:size(graph,1)
        min_dist = Inf;
        for j=1:size(graph,1)
            if ~visited(j) && dist(j) < min_dist
                min_dist = dist(j);
                current_node = j;
            end
        end
        visited(current_node) = 1;
        if min_dist == Inf
            break
        end
        for j=1:size(graph,1)
            if graph(current_node,j) && dist(current_node)+graph(current_node,j) < dist(j)
                dist(j) = dist(current_node)+graph(current_node,j);
                path(j) = current_node;
            end
        end
    end
    if dist(end_node) == Inf
        path = [];
    else
        path_list = end_node;
        while path(path_list) ~= 0
            path_list = [path(path_list) path_list];
        end
        path_list = [start_node path_list];
        path = fliplr(path_list);
    end
end

4. 最小生成树算法（Prim算法）

function [min_tree, min_cost] = prim(graph)
    num_nodes = size(graph,1);
    connected_nodes = ones(1,num_nodes);
    connected_nodes(1) = 0;
    min_tree = zeros(num_nodes);
    min_cost = 0;
    while sum(connected_nodes) < num_nodes
        min_edge = Inf;
        for i=1:num_nodes
            if connected_nodes(i) == 0
                continue
            end
            for j=1:num_nodes
                if connected_nodes(j) == 1 && graph(i,j) < min_edge
                    min_edge = graph(i,j);
                    node1 = i;
                    node2 = j;
                end
            end
        end
        connected_nodes(node2) = 0;
        min_tree(node1,node2) = min_edge;
        min_tree(node2,node1) = min_edge;
        min_cost = min_cost + min_edge;
    end
end

以上是一些图论算法的 MATLAB 代码，但这些算法并不是全部，如果需要实现其他算法，可以根据算法原理自行编写代码。