求遍历全图的最少步数：类疾病传播式节点扩散算法问询

你的问题属于图论中的**广播时间（Broadcast Time）**问题：给定无向图和初始节点，每一轮所有已感染节点可选择一个未感染邻居进行感染，求感染所有节点所需的最少轮数。

现有贪心算法的缺陷 #

你当前的策略（优先用低度数已感染节点感染高度数未感染邻居）存在两个核心问题：

• 局部最优不等于全局最优：比如测试用例3中，算法过早消耗低度数节点的感染能力去覆盖高度数节点，但实际上留部分高度数节点到后续轮次感染，能覆盖更多分支节点；
• 度数更新逻辑不合理：你直接用原始度数减已感染邻居数作为power，但节点的有效传播能力应该是剩余未感染邻居数，原始度数高的节点可能已无未感染邻居，但排序逻辑仍优先处理低度数节点，浪费传播机会。

推荐算法方案 #

1. 精确解法（适合小型图，如测试用例3的15节点图） #

状态掩码+BFS

用二进制掩码表示已感染节点集合（15节点对应15位二进制，某一位为1表示该节点已感染），通过BFS遍历所有可能的感染状态：每一轮从当前状态出发，枚举所有合法的感染组合（每个已感染节点选一个未感染邻居），寻找从初始状态（仅初始节点为1）到全1状态的最短路径，路径长度即为最少步数。

• 优势：保证得到最优解；
• 劣势：节点数超过20时，状态空间会爆炸（2^20≈1e6），无法处理大图。

动态规划

基于状态掩码的DP，dp[mask]表示达到mask状态所需的最少步数，转移逻辑与BFS一致，本质是BFS的另一种实现形式。

2. 启发式优化算法（适合中型图） #

若节点数较多，精确解法不可行，可采用以下启发式策略：

改进贪心策略

将贪心逻辑调整为：

• 每一轮计算每个未感染节点的潜在传播收益：即该节点的未感染邻居总数（感染此节点后，下一轮能新增的传播能力）；
• 优先选择收益最高的节点进行感染，同时保证每个已感染节点最多使用一次感染机会。

模拟退火/遗传算法

通过随机搜索+局部优化的方式寻找近似最优解，适合节点数在50-200的图。

3. 特殊图结构的专用算法 #

如果你的图有特殊结构，可使用针对性算法：

• 树结构的广播时间可通过动态规划在O(n)时间内求解；
• 二分图的广播时间有近似比为2的贪心算法。

现有代码优化方案 #

针对测试用例3，这里给出改进后的贪心实现，可得到5步的最优解：

import networkx as nx
import matplotlib.pyplot as plt

def compute_broadcast_time(graph, start):
    n = len(graph.nodes)
    infected = set([start])
    steps = 0
    order = [[start]]
    
    while len(infected) < n:
        steps += 1
        new_infected = set()
        # 为每个未感染节点收集可感染它的已感染节点，以及对应的收益
        candidate_map = {}
        for node in infected:
            neighbors = set(graph.neighbors(node)) - infected
            for neighbor in neighbors:
                # 收益：该邻居的未感染邻居数量（决定下一轮的传播潜力）
                benefit = len(set(graph.neighbors(neighbor)) - infected - new_infected)
                if neighbor not in candidate_map:
                    candidate_map[neighbor] = []
                candidate_map[neighbor].append((benefit, node))
        
        # 按收益从高到低排序候选节点，优先选择能带来最大传播潜力的节点
        sorted_candidates = sorted(candidate_map.items(), key=lambda x: max(b for b, _ in x[1]), reverse=True)
        used_sources = set()
        for neighbor, options in sorted_candidates:
            if neighbor in new_infected:
                continue
            # 选择能感染该节点的最优已感染节点
            _, source = max(options, key=lambda x: x[0])
            if source not in used_sources:
                used_sources.add(source)
                new_infected.add(neighbor)
        
        infected.update(new_infected)
        order.append(list(new_infected))
    
    return steps, order

# 测试用例3
vertices = [
    [1, [2, 3, 5, 8, 12]],
    [2, [1, 3, 4]],
    [3, [1, 2, 4]],
    [4, [2, 3]],
    [5, [1, 6, 7]],
    [6, [5, 7]],
    [7, [5, 6]],
    [8, [1, 9, 10]],
    [9, [8, 10, 11]],
    [10, [8, 9]],
    [11, [9]],
    [12, [1, 13]],
    [13, [12, 14, 15]],
    [14, [13, 15]],
    [15, [13, 14]]
]

# 创建NetworkX图
G = nx.Graph()
for node, neighbors in vertices:
    G.add_node(node)
    for neighbor in neighbors:
        G.add_edge(node, neighbor)

# 计算广播时间
steps, order = compute_broadcast_time(G, 1)
print(f"最少步数：{steps}")
print(f"传播顺序：{order}")

# 可视化传播过程
pos = nx.spring_layout(G)
node_colors = ["red"] * len(G.nodes)
plt.figure(figsize=(10, 8))
for step_nodes in order:
    for node in step_nodes:
        node_colors[node-1] = "green"
    nx.draw(G, pos, with_labels=True, font_weight="bold", node_color=node_colors)
    plt.pause(0.5)
    plt.clf()
plt.show()

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