良好的图遍历算法

Question

抽象问题：我有一个大约有25万个节点的图，平均每个节点的连接数大约是10。查找一个节点的连接需要很长时间（假设是10秒）。把一个节点保存到数据库也差不多要10秒。我可以很快检查一个节点是否已经在数据库里。允许同时处理多个请求，但一次不能超过10个长时间的请求，那么我该如何遍历这个图，以最快的速度获得最大的覆盖率。

具体问题：我正在抓取一个网站的用户页面。为了发现新用户，我从已经知道的用户那里获取好友列表。我已经导入了大约10%的图，但我总是陷入循环中，或者因为记住太多节点而占用过多内存。

我目前的实现：

def run() :
    import_pool = ThreadPool(10)
    user_pool = ThreadPool(1)
    do_user("arcaneCoder", import_pool, user_pool)

def do_user(user, import_pool, user_pool) :
    id = user
    alias = models.Alias.get(id)

    # if its been updates in the last 7 days
    if alias and alias.modified + datetime.timedelta(days=7) > datetime.datetime.now() :
        sys.stderr.write("Skipping: %s\n" % user)
    else :
        sys.stderr.write("Importing: %s\n" % user)
        while import_pool.num_jobs() > 20 :
            print "Too many queued jobs, sleeping"
            time.sleep(15)

        import_pool.add_job(alias_view.import_id, [id], lambda rv : sys.stderr.write("Done Importing %s\n" % user))

    sys.stderr.write("Crawling: %s\n" % user)
    users = crawl(id, 5)
    if len(users) >= 2 :
        for user in random.sample(users, 2) :
            if (user_pool.num_jobs() < 100) :
                user_pool.add_job(do_user, [user, import_pool, user_pool])

def crawl(id, limit=50) :
    '''returns the first 'limit' friends of a user'''
    *not relevant*

当前实现的问题：

• 总是卡在我已经导入的圈子里，浪费时间，而导入的线程处于空闲状态。
• 会根据指出的问题继续添加。

所以，欢迎提出一些小的改进建议，也欢迎完全重写的方案。谢谢！

Answer 1

我真的搞不懂为什么往数据库里添加一个节点要花10秒钟。这听起来像是个问题。你在用什么数据库？有没有什么特别的限制？

在现代系统中，内存非常充足，我建议你使用一个简单的缓存。你可以创建一个快速的用户信息缓存，这样就能避免重复工作。当你遇到一个已经存在的节点时，就停止处理。这样可以避免在小圈子里无限循环。

如果你需要在一段时间后重新处理已有的节点，可以使用一个叫做last_visit_number的全局值。如果节点有这个数字，那么这次抓取就是遇到它的那一次。如果你想自动重新访问任何节点，只需在开始抓取之前把last_visit_number加一。

根据你的描述，我不太明白你是怎么卡住的。

编辑 ------ 我刚注意到你有一个具体的问题。为了加快获取新数据的速度，我建议你记录每个用户在你的数据中被链接的次数（无论是已导入的还是未导入的）。在选择要抓取的用户时，我会优先选择链接次数少的用户。我会特别选择链接次数最少的用户，或者在链接次数最少的用户中随机选择。

Jacob

Answer 2

从头开始构建图形并没有特别的算法可以帮助你优化。无论如何，你至少需要访问每个节点一次。你可以选择先深入某个方向（深度优先）或者先广泛探索（广度优先），这对速度来说其实没什么影响。Theran 在下面的评论中提到，广度优先搜索因为先探索离起点近的节点，可能会让你更快得到一个有用的图形，虽然这是否重要就看你自己的需求了。他还提到，深度优先搜索的最简洁版本是用递归实现的，但这可能会给你带来一些问题。不过，递归并不是必须的；如果你愿意，也可以把未完全探索的节点放到一个栈里，然后线性处理它们。

如果你对新节点做一个简单的存在性检查（如果用哈希表查找的话是O(1)），那么循环（也就是图中节点互相连接形成的环）就不会是问题。循环只有在你没有存储完整图形时才需要担心。你可以优化在图中搜索的过程，但构建图的步骤总是需要线性时间。

我同意其他人的看法，图的大小不应该是个问题。25万个节点其实并不算大！

关于并发执行的问题，图是由所有线程更新的，所以它需要是一个同步的数据结构。由于这是Python，你可以利用Queue模块来存储那些还需要线程处理的新链接。

Answer 3

为了记住你已经访问过的用户的ID，你需要一个长度为250,000的整数映射表。这并不是“太多了”。只需维护这样一个映射表，并且只遍历那些通向尚未发现的用户的边，在找到这样的边时将它们添加到映射表中。

从我看来，你已经接近实现广度优先搜索（BFS）了。可以去谷歌查一下这个算法的详细信息。当然，也不要忘记互斥锁——你会需要它们的。