算法图解python,python常见算法库

假设我们在水管工程公司或互联网光纤公司工作，我们需要使用最少的电线（或者管道）连接图表中的所有城市。我们如何做到这一点？

无向图和它的最小生成树

代码

# nx.minimum_spanning_tree(g) returns a instance of type graph nx.draw_networkx(nx.minimum_spanning_tree(g))

使用最小生成树算法铺设电线

应用

• 最小生成树在网络设计中有着最直接的应用，包括计算机网络，电信网络，运输网络，供水网络和电网。（最小生成树最初就是为此发明的）
• 最小生成树可用于求解旅行商问题的近似解
• 聚类——首先构造最小生成树，然后使用类间距离和类内距离来设定阈值，从而破坏最小生成树中的某些连边，最终完成聚类的目的
• 图像分割——首先在图形上构建最小生成树，其中像素是节点，像素之间的距离基于某种相似性度量（例如颜色，强度等），然后进行图的分割。

Pagerank 是为谷歌提供长期支持的页面排序算法。根据输入和输出链接的数量和质量，该算法对每个页面进行打分。

代码

在本节中，我们将使用 Facebook 数据。首先，利用 Facebook 用户之间的连接，我们使用以下方法创建图：

# reading the dataset fb = nx.read_edgelist('../input/facebook-combined.txt', create_using = nx.Graph(), nodetype = int)

将图进行可视化：

pos = nx.spring_layout(fb) import warnings warnings.filterwarnings('ignore') plt.style.use('fivethirtyeight') plt.rcParams['figure.figsize'] = (20, 15) plt.axis('off') nx.draw_networkx(fb, pos, with_labels = False, node_size = 35) plt.show()