如何在Memgraph中基于空手道俱乐部社交网络数据集用Python运行BFS算法？

一、环境准备 #

• 确保Memgraph服务已启动（Docker或本地安装均可）
• 安装Python驱动mgclient：

  pip install mgclient
  

二、导入空手道俱乐部数据集 #

空手道俱乐部数据集包含34个成员节点和78条社交关系边，可通过以下Cypher语句导入：

// 创建所有成员节点
UNWIND range(1, 34) AS id
CREATE (:Person {id: id});

// 创建社交关系
CREATE
  (1)-[:FRIENDS_WITH]->(2), (1)-[:FRIENDS_WITH]->(3), (1)-[:FRIENDS_WITH]->(4), (1)-[:FRIENDS_WITH]->(5),
  (1)-[:FRIENDS_WITH]->(6), (1)-[:FRIENDS_WITH]->(7), (1)-[:FRIENDS_WITH]->(8), (1)-[:FRIENDS_WITH]->(9),
  (1)-[:FRIENDS_WITH]->(11), (1)-[:FRIENDS_WITH]->(12), (1)-[:FRIENDS_WITH]->(13), (1)-[:FRIENDS_WITH]->(14),
  (1)-[:FRIENDS_WITH]->(18), (1)-[:FRIENDS_WITH]->(20), (1)-[:FRIENDS_WITH]->(22), (2)-[:FRIENDS_WITH]->(3),
  (2)-[:FRIENDS_WITH]->(4), (2)-[:FRIENDS_WITH]->(8), (2)-[:FRIENDS_WITH]->(14), (2)-[:FRIENDS_WITH]->(18),
  (2)-[:FRIENDS_WITH]->(20), (2)-[:FRIENDS_WITH]->(22), (2)-[:FRIENDS_WITH]->(31), (3)-[:FRIENDS_WITH]->(4),
  (3)-[:FRIENDS_WITH]->(8), (3)-[:FRIENDS_WITH]->(9), (3)-[:FRIENDS_WITH]->(10), (3)-[:FRIENDS_WITH]->(14),
  (3)-[:FRIENDS_WITH]->(28), (3)-[:FRIENDS_WITH]->(29), (3)-[:FRIENDS_WITH]->(33), (4)-[:FRIENDS_WITH]->(8),
  (4)-[:FRIENDS_WITH]->(13), (4)-[:FRIENDS_WITH]->(14), (5)-[:FRIENDS_WITH]->(7), (5)-[:FRIENDS_WITH]->(11),
  (6)-[:FRIENDS_WITH]->(7), (6)-[:FRIENDS_WITH]->(11), (6)-[:FRIENDS_WITH]->(17), (7)-[:FRIENDS_WITH]->(17),
  (8)-[:FRIENDS_WITH]->(9), (8)-[:FRIENDS_WITH]->(10), (8)-[:FRIENDS_WITH]->(14), (9)-[:FRIENDS_WITH]->(10),
  (9)-[:FRIENDS_WITH]->(14), (9)-[:FRIENDS_WITH]->(34), (10)-[:FRIENDS_WITH]->(34), (14)-[:FRIENDS_WITH]->(34),
  (15)-[:FRIENDS_WITH]->(16), (15)-[:FRIENDS_WITH]->(19), (15)-[:FRIENDS_WITH]->(20), (15)-[:FRIENDS_WITH]->(21),
  (15)-[:FRIENDS_WITH]->(23), (15)-[:FRIENDS_WITH]->(24), (15)-[:FRIENDS_WITH]->(30), (15)-[:FRIENDS_WITH]->(31),
  (15)-[:FRIENDS_WITH]->(32), (15)-[:FRIENDS_WITH]->(33), (15)-[:FRIENDS_WITH]->(34), (16)-[:FRIENDS_WITH]->(19),
  (16)-[:FRIENDS_WITH]->(20), (16)-[:FRIENDS_WITH]->(24), (16)-[:FRIENDS_WITH]->(27), (16)-[:FRIENDS_WITH]->(30),
  (16)-[:FRIENDS_WITH]->(32), (16)-[:FRIENDS_WITH]->(33), (17)-[:FRIENDS_WITH]->(34), (18)-[:FRIENDS_WITH]->(34),
  (19)-[:FRIENDS_WITH]->(20), (19)-[:FRIENDS_WITH]->(21), (19)-[:FRIENDS_WITH]->(23), (19)-[:FRIENDS_WITH]->(24),
  (19)-[:FRIENDS_WITH]->(27), (19)-[:FRIENDS_WITH]->(28), (19)-[:FRIENDS_WITH]->(29), (19)-[:FRIENDS_WITH]->(33),
  (20)-[:FRIENDS_WITH]->(24), (20)-[:FRIENDS_WITH]->(34), (21)-[:FRIENDS_WITH]->(23), (21)-[:FRIENDS_WITH]->(24),
  (21)-[:FRIENDS_WITH]->(27), (21)-[:FRIENDS_WITH]->(28), (21)-[:FRIENDS_WITH]->(29), (22)-[:FRIENDS_WITH]->(34),
  (23)-[:FRIENDS_WITH]->(24), (23)-[:FRIENDS_WITH]->(27), (23)-[:FRIENDS_WITH]->(28), (23)-[:FRIENDS_WITH]->(29),
  (24)-[:FRIENDS_WITH]->(27), (24)-[:FRIENDS_WITH]->(34), (25)-[:FRIENDS_WITH]->(26), (25)-[:FRIENDS_WITH]->(28),
  (25)-[:FRIENDS_WITH]->(29), (25)-[:FRIENDS_WITH]->(33), (26)-[:FRIENDS_WITH]->(28), (26)-[:FRIENDS_WITH]->(29),
  (26)-[:FRIENDS_WITH]->(33), (27)-[:FRIENDS_WITH]->(34), (28)-[:FRIENDS_WITH]->(29), (28)-[:FRIENDS_WITH]->(33),
  (28)-[:FRIENDS_WITH]->(34), (29)-[:FRIENDS_WITH]->(33), (29)-[:FRIENDS_WITH]->(34), (30)-[:FRIENDS_WITH]->(32),
  (30)-[:FRIENDS_WITH]->(33), (31)-[:FRIENDS_WITH]->(33), (31)-[:FRIENDS_WITH]->(34), (32)-[:FRIENDS_WITH]->(33),
  (32)-[:FRIENDS_WITH]->(34), (33)-[:FRIENDS_WITH]->(34);

可在Memgraph Lab查询编辑器中执行，或通过Python连接后执行该语句。

三、Python实现BFS的两种方式 #

方式1：利用Memgraph内置BFS（推荐） #

Memgraph的Cypher支持[*bfs]语法直接执行广度优先搜索，效率更高：

import mgclient

def run_builtin_bfs(start_node_id):
    # 连接Memgraph（默认端口7687，无密码）
    conn = mgclient.connect(host='127.0.0.1', port=7687)
    cursor = conn.cursor()

    # 执行内置BFS查询，遍历所有可达节点
    query = f"""
        MATCH path = (start:Person {{id: {start_node_id}}})-[*bfs]->(node:Person)
        RETURN node.id AS node_id, nodes(path) AS path_nodes
        ORDER BY length(path)
    """
    cursor.execute(query)

    # 输出结果
    print(f"从节点{start_node_id}出发的BFS遍历结果：")
    for row in cursor.fetchall():
        node_id = row[0]
        path_nodes = [n['id'] for n in row[1]]
        print(f"节点{node_id}，路径：{' -> '.join(map(str, path_nodes))}")

    # 关闭连接
    cursor.close()
    conn.close()

# 从节点1（俱乐部教练）出发执行BFS
run_builtin_bfs(1)

方式2：手动实现BFS逻辑 #

若需更灵活的控制逻辑，可手动维护队列逐次查询邻居：

import mgclient
from collections import deque

def run_manual_bfs(start_node_id):
    conn = mgclient.connect(host='127.0.0.1', port=7687)
    cursor = conn.cursor()

    visited = set()
    queue = deque()
    # 队列元素：(当前节点ID, 路径列表)
    queue.append((start_node_id, [start_node_id]))
    visited.add(start_node_id)

    print(f"从节点{start_node_id}出发的手动BFS遍历结果：")
    while queue:
        current_id, path = queue.popleft()
        print(f"节点{current_id}，路径：{' -> '.join(map(str, path))}")

        # 查询当前节点的所有邻居
        query = f"""
            MATCH (current:Person {{id: {current_id}}})-[:FRIENDS_WITH]->(neighbor:Person)
            RETURN neighbor.id AS neighbor_id
        """
        cursor.execute(query)
        neighbors = [row[0] for row in cursor.fetchall()]

        for neighbor_id in neighbors:
            if neighbor_id not in visited:
                visited.add(neighbor_id)
                queue.append((neighbor_id, path + [neighbor_id]))

    cursor.close()
    conn.close()

# 执行手动BFS
run_manual_bfs(1)

四、运行说明 #

• 确保Memgraph服务处于运行状态，默认端口为7687
• 运行Python代码前需先完成数据集导入
• 内置BFS方式效率更高，手动方式适合定制遍历逻辑

内容的提问来源于stack exchange，提问作者MPesi