数据结构六度空间理论代码

六度空间理论是指通过最短路径将任意两个人联系起来，最多只需要6次传递信息。在数据结构中，可以使用图来表示人与人之间的关系，然后使用最短路径算法（如Dijkstra算法）来求解最短路径。

以下是使用Python实现六度空间理论的代码示例：

# 图的邻接表表示
graph = {
    'Alice': ['Bob', 'Claire', 'David'],
    'Bob': ['Alice', 'Elle', 'Fred'],
    'Claire': ['Alice', 'David', 'George'],
    'David': ['Alice', 'Claire', 'George'],
    'Elle': ['Bob'],
    'Fred': ['Bob'],
    'George': ['Claire', 'David']
}

# Dijkstra算法求解最短路径
def dijkstra(graph, start, end):
    # 初始化距离和前驱节点
    distances = {vertex: float('inf') for vertex in graph}
    distances[start] = 0
    predecessors = {vertex: None for vertex in graph}

    # 用set存储未处理的节点
    unvisited_nodes = set(graph)

    while unvisited_nodes:
        # 选取距离最短的节点
        current_node = min(unvisited_nodes, key=lambda node: distances[node])

        # 如果已经到达终点，结束搜索
        if current_node == end:
            break

        # 更新当前节点的邻居节点的距离和前驱节点
        for neighbor in graph[current_node]:
            new_distance = distances[current_node] + 1
            if new_distance < distances[neighbor]:
                distances[neighbor] = new_distance
                predecessors[neighbor] = current_node

        # 将当前节点标记为已处理
        unvisited_nodes.remove(current_node)

    # 没有找到最短路径
    if distances[end] == float('inf'):
        return None

    # 构造最短路径
    path = []
    current_node = end
    while current_node != start:
        path.insert(0, current_node)
        current_node = predecessors[current_node]
    path.insert(0, start)
    return path

# 测试代码
start = 'Alice'
end = 'George'
path = dijkstra(graph, start, end)
if path:
    print(f"The shortest path from {start} to {end} is: {' -> '.join(path)}")
else:
    print(f"No path from {start} to {end} exists")

输出结果为：

The shortest path from Alice to George is: Alice -> David -> George