寻找最长聚类的算法。（理想情况下是Python，可能是Matlab）

Question

我在用一种叫做“键渗流理论”的方法进行实验，有效地，你有一些n×n的格子网格，然后（随机地）以概率p保留或删除一条边。下面是一个例子：

这是我的密码：

对于这个奇妙的社区，我有两个问题：

1. 如何使插入的网格显示在所有整数值上，到目前为止，它仅显示为5的倍数。（细灰线）
2. 我希望有一个算法可以提供所谓的“最长簇”，簇是一个边的连通图（粗黑线），例如在左上角，我们有6个簇（倒f形），2个簇（小箭头），4个簇（正方形）和3个簇（倒L）最长的集群就是最长的集群

非常感谢您的帮助。如果我提出了这个问题，请让我知道，或如果任何澄清是必要的

def graph_contruction(n,p):
for i in range(0,n):
    for t in range(0,n):
        if coin(p):
            plt.hlines(i,t,t+1)
        if coin(p):
            plt.vlines(i,t,t+1)
plt.title('A '+str(n)+ ' by ' +str(n) + ' grid with probability ' +str(p))
plt.show()

Answer 1

您的第一个问题可以通过启用小刻度来简单地解决：

plt.figure(figsize=(8,8))
plt.minorticks_on()
plt.grid(True, which="both")
graph_contruction(25, 0.5)

Answer 2

让您了解如何思考问题2）：

步骤1）构建一个函数，用于检查每个点的关联点并返回这些点的集合。对于（0,0）来说，这算不了什么。但是对于（0,1）这个函数将返回{（0,1），（1,0），（1,1），（2,0）}-a.k.a一组与轴点（0,1）相关的点

步骤2）在步骤1中构建函数后，迭代所有点以获得每个点的一组关联点

步骤3）现在，如果集合中有一个公共点，则可以将它们连接起来。见下文：

set_1 = {(1,0), (1,1), (2,0)}

set_2 = {(1,2), (1,1), (2,1), (1,0)}

if any(x in set_1 for x in set_2):
    set_1.update(set_2) 

因此，我只是试图勾勒出你的想法，而不是给你确切的代码。您可能希望使用理解来保持集合比较的pythonic

如果你真的很挣扎，我可以找到我的代码，在那里我实现了类似的东西。我今天找过了，但没找到。如果你真的放弃了，它会解决这个问题，但这是一个有趣的挑战，所以试一试