python – 从集合中查找断开连接的图形的算法

内容导读

互联网集市收集整理的这篇技术教程文章主要介绍了python – 从集合中查找断开连接的图形的算法，小编现在分享给大家，供广大互联网技能从业者学习和参考。文章包含1732字，纯文字阅读大概需要3分钟。

内容图文

目标：
想要从大量集合中有效地查找所有断开连接的图形

例如,
我有一个如下的数据文件：

A, B, C
C, D, E
A, F, Z
G, J
...

每个条目代表一组元素.
第一个条目A,B,C = {A,B,C}
这也表明A和B,A和C,B和C之间存在边缘.

我最初提出的算法如下

1.parse all the entries into a list:
[
{A,B,C}
{C,D,E}
...
]
2.start with the first element/set of the list can called start_entry, {A,B,C} in this case
3.traverse other element in the list and do the following:
     if the intersection of the element and start_entry is not empty
          start_entry = start_entry union with the element
          remove element from the list
4.with the updated start_entry, traverse the list again until there is not new update

上面的算法应该返回连接图的顶点列表.然而,由于数据集大小,我遇到了运行时问题.有大约100000个条目.
所以我只是想知道是否有人知道有更有效的方法来查找连接图.

数据结构也可以改成(如果这更容易)
A,B
公元前
E,F
…
每个条目代表图形的边缘.

解决方法:

这看起来像是使用disjoint set data structure的理想情况.

这使您可以在几乎线性的时间内连接在一起.

示例Python代码

from collections import defaultdict

data=["A","B","C"],["C","D","E"],["F","G"]

# Prepare mapping from data element to index
S = {}
for a in data:
    for x in a:
        if x not in S:
            S[x] = len(S)

N = len(S)
rank=[0]*N
parent=range(N)

def Find(x):
    """Find representative of connected component"""
    if  parent[x] != x:
        parent[x] = Find(parent[x])
    return parent[x]

def Union(x,y):
    """Merge sets containing elements x and y"""
    x = Find(x)
    y = Find(y)
    if x == y:
        return
    if rank[x]<rank[y]:
        parent[x] = y
    elif rank[x]>rank[y]:
        parent[y] = x
    else:
        parent[y] = x
        rank[x] += 1

# Merge all sets
for a in data:
    x = a[0]
    for y in a[1:]:
        Union(S[x],S[y])

# Report disconnected graphs
V=defaultdict(list)
for x in S:
    V[Find(S[x])].append(x)

print V.values()

版画

[['A', 'C', 'B', 'E', 'D'], ['G', 'F']]

内容总结

以上是互联网集市为您收集整理的python – 从集合中查找断开连接的图形的算法全部内容，希望文章能够帮你解决python – 从集合中查找断开连接的图形的算法所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错，欢迎将互联网集市网站推荐给程序员好友。

内容备注

版权声明：本文内容由互联网用户自发贡献，该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 gblab@vip.qq.com 举报，一经查实，本站将立刻删除。

内容手机端

---