Python中最有效的图数据结构是什么？

73 投票

7 回答

31896 浏览

提问于 2025-04-10 23:35

我需要在Python中处理一个很大的图，节点数量大约有1000万。每个节点或边的数据都很简单，比如说只有少量的字符串。那么，怎样做才能在内存和速度上最有效呢？

用字典的字典（dict of dicts）会更灵活，也更容易实现，但我直觉上觉得用列表的列表（list of lists）会更快。使用列表的话，我还需要把数据和结构分开存储，而字典则可以让我做到类似这样的事情：

graph[I][J]["Property"]="value"

你有什么建议吗？

是的，我应该更清楚地说明我所说的效率。在这种情况下，我指的是随机访问数据的效率。

把数据加载到内存里并不是个大问题。这一过程只需要做一次。真正耗时的是访问节点，以便提取信息和测量我感兴趣的指标。

我之前没有考虑把每个节点做成一个类（因为所有节点的属性都是一样的），但这似乎会增加额外的开销？我希望有人能分享一下他们在类似情况下的直接经验。毕竟，图是计算机科学中最常见的抽象之一。

性能优化内存管理图数据结构随机访问数据存储计算机科学节点处理类设计

7 个回答

正如之前提到的，NetworkX非常不错，另外一个选择是igraph。这两个模块几乎都有你可能需要的大部分（如果不是全部的话）分析工具，而且这两个库通常都被用在大型网络中。

回答于 2025-04-10 由 Python大师

分享举报

虽然这个问题现在已经有点旧了，但我觉得有必要提一下我自己用的一个Python模块，叫做graph-tool，它专门用来处理图形数据。这个模块非常高效，因为它的数据结构和算法是用C++写的，并且使用了模板元编程，结合了Boost图形库。所以它的性能（无论是内存使用还是运行速度）都能和纯C++的库相媲美，甚至在很多情况下比普通的Python代码要快得多，而且使用起来也很简单。我自己经常用它来处理非常大的图形数据。

回答于 2025-04-10 由 Python大师

分享举报

我强烈建议你看看 NetworkX。这是一个经过多次考验的工具，很多研究人员在需要分析网络数据时，都会首先选择它。我在笔记本上处理过有数十万个边的图形，完全没有问题。它功能丰富，而且非常容易上手。你会发现自己更多地关注实际问题，而不是底层实现的细节。

这是一个关于 Erdős-Rényi 随机图生成和分析的例子


"""
Create an G{n,m} random graph with n nodes and m edges
and report some properties.

This graph is sometimes called the Erd##[m~Qs-Rényi graph
but is different from G{n,p} or binomial_graph which is also
sometimes called the Erd##[m~Qs-Rényi graph.
"""
__author__ = """Aric Hagberg (hagberg@lanl.gov)"""
__credits__ = """"""
#    Copyright (C) 2004-2006 by 
#    Aric Hagberg 
#    Dan Schult 
#    Pieter Swart 
#    Distributed under the terms of the GNU Lesser General Public License
#    http://www.gnu.org/copyleft/lesser.html

from networkx import *
import sys

n=10 # 10 nodes
m=20 # 20 edges

G=gnm_random_graph(n,m)

# some properties
print "node degree clustering"
for v in nodes(G):
    print v,degree(G,v),clustering(G,v)

# print the adjacency list to terminal 
write_adjlist(G,sys.stdout)

可视化也很简单：

在这里输入图片描述

回答于 2025-04-10 由 Python大师

分享举报

Python中最有效的图数据结构是什么？

7 个回答

撰写回答