图论术语

树:连通的无圈图

树的性质:

• 任意两个不同顶点之间存在唯一的路
• 删除任意一条边都不连通
• 顶点数=边数+1
• 添加任意一条边都会得到唯一的一个圈

生成树/支撑树:若图$G$的生成子图$T$是树，则称$T$为$G$的生成树或支撑树。

[定理]连通图的生成树一定存在。

证:若连通图$G$无圈，则$G$为本身的生成树。若$G$有圈，任取其一圈，删除其中一条边。易知，$G‘$仍旧连通，且圈数-1.重复该步骤，直到得到$G$无圈的连通生成子图，即一个生成树。

最小生成树:赋权图$G$的边权和最小的生成树

模型简介

已知赋权无向图$G=(V,E,W)$,其中$V$包含n个顶点。求$G$的最小生成树。

Kruskal(克鲁斯卡尔)算法

算法思想：每次加一条权值最小的边，并确保不形成圈

算法步骤

• 选取$e_1\in E$,使得$e_1$为权值最小的边
• 若$e_1,e_2,\cdot \cdot \cdot ,e_i$已经选好，则从 E − { e 1 , e 2 , ⋅ ⋅ ⋅ , e i } E-\{e_1,e_2,···,e_i\} E−{e1​,e2​,⋅⋅⋅,ei​}中选取$e_{i+1}$ ,使得 { e 1 , e 2 , ⋅ ⋅ ⋅ , e i , e i + 1 } \{e_1,e_2,···,e_i,e_{i+1}\} {e1​,e2​,⋅⋅⋅,ei​,ei+1​}中无圈，且$e_{i+1}$是 E − { e 1 , e 2 , ⋅ ⋅ ⋅ , e i } E-\{e_1,e_2,···,e_i\} E−{e1​,e2​,⋅⋅⋅,ei​}中权值最小的边
• 直至选得$e_{n-1}$为止

Matlab代码

% Kruskal.m

function [resultgraph, minw] = Kruskal(G)
    % Kruskal算法求最小生成树

    % 初始化参数
    W = full(G.adjacency("weighted"));
    n = length(W);
    W(W == 0) = inf;
    minw = 0;
    resultgraph = graph();
    i = 1;

    while i < n
        % 寻找最小权值边
        w_min = min(W, [], "all");
        [index_x, index_y] = find(W == w_min, 1);
        % 添加最小权值边
        resultgraph = resultgraph.addedge(index_x, index_y, w_min);
        % 判断添加该边后图是否有圈
        if hascycles(resultgraph)
            % 有圈则删除该边，并标记pass
            resultgraph = resultgraph.rmedge(index_x, index_y);
            W(index_x, index_y) = inf;
            W(index_y, index_x) = inf;
        else
            % 无圈则保持,并标记pass
            W(index_x, index_y) = inf;
            W(index_y, index_x) = inf;
            minw = minw + w_min;
            i = i + 1;
        end

    end

end

示例:

clear,clc

% 创建图
E = [1 2 2; 1 3 8; 1 4 1;
    2 3 6; 2 5 1; 3 4 7;
    3 5 5; 3 6 1; 3 7 2;
    4 7 9; 5 6 3; 5 8 2;
    5 9 9; 6 7 4; 6 9 6;
    7 9 3; 7 10 1; 8 9 7;
    8 11 9; 9 10 1; 9 11 2;
    10 11 4];

G = graph(E(:, 1), E(:, 2), E(:, 3));

% Kruskal算法求解最小生成树
[min_tree, min_w] = Kruskal(G);

% 绘图并加粗最小生成树
p = plot(G, "EdgeLabel", G.Edges.Weight, 'EdgeLabelColor', 'green');
highlight(p, min_tree, "EdgeColor", "red", "LineWidth", 4);

Python代码

def Kruskal(G):
    """Kruskal算法求解最小生成树"""
    # 初始化参数
    W = nx.to_numpy_matrix(G)
    n, n = np.shape(W)
    W[W == 0] = np.inf
    minw = 0
    resultgraph = nx.Graph()
    i = 1

    while i < n:
        # 寻找最小权值边
        w_min = np.min(W)
        index_x, index_y = [
            np.where(W == w_min)[0][0],
            np.where(W == w_min)[1][0]
        ]
        # 添加最小权值边
        resultgraph.add_edge(index_x + 1,
                             index_y + 1,
                             weight=G.edges[index_x + 1,
                                            index_y + 1]['weight'])
        try:
            # 判断添加该边后图是否有圈
            nx.find_cycle(resultgraph)
        except:
            # 无圈则保持,并标记pass
            W[index_x, index_y] = np.inf
            W[index_y, index_x] = np.inf
            minw = minw + w_min
            i = i + 1
        else:
            # 有圈则删除该边，并标记pass
            resultgraph.remove_edge(index_x + 1, index_y + 1)
            W[index_x, index_y] = np.inf
            W[index_y, index_x] = np.inf

    return resultgraph, minw

示例:

# 导库
import networkx as nx
import numpy as np

# 输入边和权
edges = [(1, 2, 2), (1, 3, 8), (1, 4, 1), (2, 3, 6), (2, 5, 1), (3, 4, 7),
         (3, 5, 5), (3, 6, 1), (3, 7, 2), (4, 7, 9), (5, 6, 3), (5, 8, 2),
         (5, 9, 9), (6, 7, 4), (6, 9, 6), (7, 9, 3), (7, 10, 1), (8, 9, 7),
         (8, 11, 9), (9, 10, 1), (9, 11, 2), (10, 11, 4)]

# 创建空图并添加顶点和边权
G = nx.Graph()
G.add_weighted_edges_from(edges)

# 计算顶点位置
pos = nx.spring_layout(G)

# 绘制无权图
nx.draw(G, pos, with_labels=True, font_size=14)

# Kruskal算法求解最小生成树
min_tree,wmin = Kruskal(G)

# 绘制最小生成树
nx.draw_networkx_edges(G,pos,edgelist=min_tree.edges,edge_color="red",width=3)

# 追加绘制权
labels = nx.get_edge_attributes(G, 'weight')
edges = nx.draw_networkx_edge_labels(G,
                                     pos,
                                     edge_labels=labels,
                                     font_color="green")

Prim(普里姆)算法

算法思想:最小生成树中包含$G$的所有顶点。

记号说明:

记号	含义
$V_{added}$	已加入最小生成树的顶点
$E_{added}$	已加入最小生成树的边

算法步骤

V a d d e d = { v 1 } E a d d e d = ∅ w h i l e   V a d d e d ≠ V : 寻找最小权值边 p v 其中 p ∈ V a d d e d , v ∈ V − V a d d e d V a d d e d = V a d d e d + { v } E a d d e d = E a d d e d + { p v } V_{added}=\{v_1\} \\ E_{added}= \empty \\ \\ while\ V_{added}\neq V:\\ 寻找最小权值边pv\\其中p\in V_{added},v\in V-V_{added}\\ V_{added}=V_{added}+\{v\}\\ E_{added}=E_{added}+\{pv\}\\ Vadded​={v1​}Eadded​=∅while Vadded​=V:寻找最小权值边pv其中p∈Vadded​,v∈V−Vadded​Vadded​=Vadded​+{v}Eadded​=Eadded​+{pv}

Matlab代码

% Prim.m

function [resultgraph, minw] = Prim(G)
    % Prim算法求解最小生成树

    % 初始化参数
    W = full(G.adjacency("weighted"));
    n = length(W);
    W(W == 0) = inf;
    V = 1:n;
    V_added = [1];
    E_added = [];
    minw = 0;

    % 直至V和V_added相等
    while ~isequal(V, sort(V_added))
        tmp = W;
        V_not_added = setdiff(V, V_added);
        % 圈定p,v范围
        tmp(V_not_added, :) = inf;
        tmp(:, V_added) = inf;
        w_min = min(tmp, [], "all");
        minw = minw + w_min;
        [p, v] = find(tmp == w_min, 1);
        % pv边标记pass
        W(p, v) = inf;
        W(v, p) = inf;
        % 更新
        V_added = union(V_added, v);
        E_added = [E_added; p, v, w_min];
    end

    s = E_added(:, 1);
    t = E_added(:, 2);
    w = E_added(:, 3);
    resultgraph = graph(s, t, w);
end

示例:

clear,clc

% 创建图
E=[ 1 2 2;1 3 8;1 4 1;
    2 3 6;2 5 1;3 4 7;
    3 5 5;3 6 1;3 7 2;
    4 7 9;5 6 3;5 8 2;
    5 9 9;6 7 4;6 9 6;
    7 9 3;7 10 1;8 9 7;
    8 11 9;9 10 1;9 11 2;
    10 11 4];

G=graph(E(:,1),E(:,2),E(:,3));

% Prim算法求解最小生成树
[min_tree,min_w] = Prim(G)

% 绘图并加粗最小生成树
p=plot(G,"EdgeLabel",G.Edges.Weight,'EdgeLabelColor','green');
highlight(p,min_tree,"EdgeColor","red","LineWidth",4);

Python代码

def Prim(G):
    """Prim算法求解最小生成树"""
    # 初始化参数
    W = nx.to_numpy_matrix(G)
    n, n = np.shape(W)
    W[W == 0] = np.inf
    V = set(range(1, n + 1))
    V_added = set([1])
    E_added = []
    minw = 0

    # 直至V和V_added相等
    while V != V_added:
        tmp = W.copy()
        V_not_added = V - V_added
        # 圈定p,v范围
        index_x = [i - 1 for i in V_not_added]
        tmp[index_x, :] = np.inf
        index_y = [i - 1 for i in V_added]
        tmp[:, index_y] = np.inf
        w_min = np.min(tmp)
        minw = minw + w_min
        p, v = np.where(tmp == w_min)[0][0] + 1, np.where(
            tmp == w_min)[1][0] + 1
        # pv边标记pass
        W[p - 1, v - 1] = np.inf
        W[v - 1, p - 1] = np.inf
        # 更新
        V_added.add(v)
        E_added.append((p, v, w_min))

    resultgraph = nx.Graph()
    resultgraph.add_weighted_edges_from(E_added)
    return resultgraph, minw

示例:

# 导库
import networkx as nx
import numpy as np

# 输入边和权
edges = [(1, 2, 2), (1, 3, 8), (1, 4, 1), (2, 3, 6), (2, 5, 1), (3, 4, 7),
         (3, 5, 5), (3, 6, 1), (3, 7, 2), (4, 7, 9), (5, 6, 3), (5, 8, 2),
         (5, 9, 9), (6, 7, 4), (6, 9, 6), (7, 9, 3), (7, 10, 1), (8, 9, 7),
         (8, 11, 9), (9, 10, 1), (9, 11, 2), (10, 11, 4)]

# 创建空图并添加顶点和边权
G = nx.Graph()
G.add_weighted_edges_from(edges)

# 计算顶点位置
pos = nx.spring_layout(G)

# 绘制无权图
nx.draw(G, pos, with_labels=True, font_size=14)

# Prim算法求解最小生成树
min_tree,wmin = Prim(G)

# 绘制最小生成树
nx.draw_networkx_edges(G,pos,edgelist=min_tree.edges,edge_color="red",width=3)

# 追加绘制权
labels = nx.get_edge_attributes(G, 'weight')
edges = nx.draw_networkx_edge_labels(G,
                                     pos,
                                     edge_labels=labels,
                                     font_color="green")

库函数

Matlab版

[min_tree, parent] = minspantree(G) % parent返回对应下标顶点的父结点

Python版

min_tree = nx.minimum_spanning_tree(G)