图遍历与搜索：BFS/DFS在图分析中的应用、社群种子扩展、路径分析
图遍历，说白了就是怎么把一张图「走一遍」。
我刚开始做团伙欺诈识别时，总觉得图算法很玄乎。后来发现，其实核心就两个：广度优先搜索（BFS）和深度优先搜索（DFS）。你想想看，这俩不就是我们查案子的两种思路嘛——是先把所有线索摊开看，还是顺着一条线挖到底？
BFS与DFS：两种遍历哲学
BFS，一层一层往外扩。就像警察查案，先查所有直接联系人，再查这些人的联系人。我习惯用队列实现，先进先出。
DFS，一条路走到黑。更像侦探追线索，顺着一个人深挖到底，挖不动了再回头。用栈实现，后进先出。
核心区别：BFS找「最短路径」，DFS找「是否存在路径」。做社群发现时，我一般先用BFS看团伙规模，再用DFS查具体关系链。
# 伪代码示例：BFS遍历图
from collections import deque
def bfs(graph, start_node):
visited = set()
queue = deque([start_node])
visited.add(start_node)
while queue:
node = queue.popleft()
print(f"访问节点: {node}")
for neighbor in graph[node]:
if neighbor not in visited:
visited.add(neighbor)
queue.append(neighbor)
return visited我的经验：在反欺诈场景下，BFS的队列长度要设上限。我曾经遇到过一个大团伙，BFS直接爆了内存——因为图太大了。后来我加了max_queue_size参数，超过阈值就切到DFS。
社群种子扩展：从点到面的艺术
做团伙识别，第一步是找「种子」。种子可能是已知的欺诈账号、异常设备，或者被举报的号码。
有了种子，怎么扩展？说白了就是BFS的变种——种子扩展算法。
- 一阶扩展：找种子的直接邻居（转账、同设备、同IP）
- 二阶扩展：找邻居的邻居，注意控制深度
- 剪枝策略：不是所有邻居都要。我一般设个阈值——比如转账金额超过1000元才纳入，或者同设备登录超过3次才考虑
避坑指南：我曾经做过一个项目，种子扩展没加剪枝，结果从100个种子扩展出50万个节点。整个图分析跑了一晚上没出结果。后来加了「度阈值」和「边权重阈值」，才把规模控制在合理范围。
路径分析：找到团伙的「骨架」
路径分析，就是看两个节点之间怎么连通的。在反欺诈里，这招特别有用——比如查两个看似无关的账号，是不是通过某个中间人串联起来的。
我常用的路径分析方法：
- 最短路径：BFS天然适合，复杂度O(V+E)
- 所有路径：DFS回溯，适合小图（节点数<1000）
- 关键路径：找必经节点，也就是「桥接点」
# DFS找所有路径（带深度限制）
def find_all_paths(graph, start, end, max_depth=5):
paths = []
def dfs(current, target, path, depth):
if depth > max_depth:
return
if current == target:
paths.append(path[:])
return
for neighbor in graph[current]:
if neighbor not in path:
path.append(neighbor)
dfs(neighbor, target, path, depth+1)
path.pop()
dfs(start, end, [start], 0)
return paths实战技巧：路径分析时，我习惯把「路径长度」和「路径上的节点类型」结合起来看。比如，一条路径上如果出现3个以上「新注册账号」，那基本可以判定是团伙作案。
知识体系：图遍历与搜索的核心逻辑
下面这张图，是我自己总结的。你看一遍，基本就明白这章在讲什么了。
实战中的选择策略
到底用BFS还是DFS？我一般这么判断：
| 场景 | 推荐算法 | 原因 |
|---|---|---|
| 找最短转账路径 | BFS | 天然保证最短，复杂度可控 |
| 查深层关系链 | DFS | 能挖到深层节点，适合查幕后黑手 |
| 社群种子扩展 | BFS + 剪枝 | 一层层扩，方便控制规模和精度 |
| 环路检测 | DFS | 回溯时容易发现重复访问 |
| 全图连通分量 | BFS/DFS均可 | 看个人习惯，我偏好BFS |
注意：图遍历不是万能的。如果图有上亿节点，BFS和DFS都扛不住。这时候得用采样或者分布式框架。我踩过这个坑——用单机BFS跑千万级图，跑了3天没出结果。
嗯，图遍历这块，说白了就是「怎么走」的问题。BFS稳，DFS狠。做反欺诈，两个都得会，还得知道什么时候用哪个。