107. 最小网络(Minimal network)

下面这个无向网络包含有7个顶点和12条边，总的权重是243：

这个网络也可以用矩阵的形式表示如下：

然而，我们其实可以优化这个网络，移除其中的一些边，同时仍然保证每个顶点之间都是连通的。其中权重节省的最多的网络如下图所示：

它的总权重是93，相比原来的网络节省了\(243-93=150\)个权重。

在这个6K的文本文件network.txt中存放了一个包含有40个顶点的网络的邻接矩阵。移除其中冗余的边，同时仍然保证每个顶点之间都是连通的，求能够节省的最大权重。

分析：熟悉图论的同学可以很快发现题目实际就是要求给定网络的最小生成树。所谓最小生成树是指在一个连通的加权无向图中，能够连接图中的所有顶点且边的权重之和最小的树。最小生成树在实际生活中有比较多的应用，比如当我们要在不同的位置之间架设电线时，我们希望连接所有的位置，同时使得架设的线路长度或者花费最小，这实际就是一个最小生成树问题。

求解最小生成树问题，已经有很多成熟的算法，常用的包括普里姆算法、克鲁斯克尔算法等等，他们都是典型的贪心算法，在实现原理上也比较相似。关于这些算法的详细的介绍，大家可以参阅相应的维基页面，里面有非常详细的介绍。因为\(networkx\)库已经用克鲁斯克尔算法实现了求解最小生成树的函数，所以我就不再重新造轮子了，直接调用了相应函数来求解这个问题。

在代码实现时，首先我们需要把题目用文本文件给出的邻接矩阵转化一个图，我这里先把文件文件中的数字转化成了一个二维列表，再将其转化成\(numpy\)二维数组，最后使用\(networkx\)库把它转化为一个图。转化成图之后，我们只需要调用求解最小生成树的函数，就能求解出最小生成树的各条边以及对应的权重，我们用原来的图的权重之和减去最小生成树的权重之和，就得到最大可以节约的权重，即为题目所求。

# time cost = 5.9 ms ± 75.7 µs

import numpy as np
import networkx as nx

def convert_matrix_to_graph():
    with open('data/pe107.txt') as f:
        network = []
        for line in f.readlines():
            line = line.replace('-','0').strip()
            network.append([int(x) for x in line.split(',')])
        g = nx.from_numpy_array(np.array(network))
        return g

def main():
    g = convert_matrix_to_graph()
    mst = nx.minimum_spanning_tree(g)
    g_weights = g.size(weight='weight')
    mst_weights = t.size(weight='weight')
    return g_weights-mst_weights