完整算法目录

最后更新: 2026-07-07 | 已实现: ~95 算法 / 772 tests

状态图例

标记	含义
✅	已实现（完整实现 + 测试）
⬜	未实现（计划中）
📝	研究前沿

---

核心算法 (已实现)

1. 图遍历 — 5/8

#	算法	状态	复杂度	模块
1	广度优先搜索 (BFS)	✅	O(V+E)	traversal/bfs
2	深度优先搜索 (DFS)	✅	O(V+E)	traversal/dfs
3	双向 BFS	✅	O(b^(d/2))	traversal/bidirectional_bfs
4	拓扑排序 (Kahn)	✅	O(V+E)	traversal/topological_sort
5	环检测	✅	O(V+E)	traversal/cycle_detection

2. 最短路径 — 8/11

#	算法	状态	复杂度
6	Dijkstra	✅	O((V+E)logV)
7	Bellman-Ford	✅	O(VE)
8	Floyd-Warshall	✅	O(V³)
9	A* 搜索	✅	O(b^d)
10	Johnson 算法	✅	O(V²logV+VE)
11	SPFA	✅	O(kE) avg
12	双向 Dijkstra	✅	O((V+E)logV)
13	Yen’s K 短路	✅	O(KV(E+VlogV))

3. 最小生成树 — 2/4

#	算法	状态	复杂度
14	Kruskal	✅	O(ElogE)
15	Prim	✅	O((V+E)logV)

4. 网络流 — 6/8

#	算法	状态	复杂度
16	Edmonds-Karp	✅	O(VE²)
17	Dinic	✅	O(V²E)
18	最小费用最大流	✅	O(F·E·V)
19	Push-Relabel (HLPP)	✅	O(V²√E)
20	容量缩放	✅	O(E²logU)
21	Stoer-Wagner 最小割	✅	O(VE+V²logV)

5. 图匹配 — 4/6

#	算法	状态	复杂度
22	匈牙利算法	✅	O(VE)
23	Hopcroft-Karp	✅	O(E√V)
24	Edmonds (Blossom)	✅	O(V³)
25	Kuhn-Munkres (KM)	✅	O(V³)

6. 连通性 — 4/6

#	算法	状态	复杂度
26	连通分量 (CC)	✅	O(V+E)
27	Tarjan SCC	✅	O(V+E)
28	Kosaraju SCC	✅	O(V+E)
29	双连通分量 (BCC)	✅	O(V+E)

7. 图着色 — 5/7

#	算法	状态	复杂度
30	贪心着色	✅	O(V+E)
31	Welsh-Powell	✅	O(V²)
32	DSATUR	✅	O(V³)
33	精确着色	✅	O(exp)
34	边着色	✅	O(VE)

8. 团与独立集 — 3/4

#	算法	状态	复杂度
35	Bron-Kerbosch 最大团	✅	O(3^(V/3))
36	最大独立集	✅	O(3^(V/3))
37	最小顶点覆盖	✅	O(3^(V/3))

9. 欧拉图与哈密顿图 — 5/6

#	算法	状态	复杂度
38	Hierholzer 欧拉回路	✅	O(E)
39	欧拉路径	✅	O(E)
40	欧拉图判定	✅	O(V+E)
41	哈密顿回路回溯	✅	O(V!)
42	TSP 最近邻	✅	O(V²)
43	TSP Held-Karp	✅	O(V²·2^V)

---

网络分析 (已实现)

10. 中心性分析 — 5/12

#	算法	状态	复杂度
44	度中心性	✅	O(V)
45	介数中心性 (Brandes)	✅	O(VE)
46	接近中心性	✅	O(V(V+E))
47	特征向量中心性	✅	O(V+E)
48	PageRank	✅	O(V+E)

11. 社区检测 — 4/10

#	算法	状态	复杂度
49	Louvain	✅	O(N log N)
50	标签传播 (LPA)	✅	O(kE)
51	Leiden	✅	O(N log N)
52	谱聚类	✅	O(V³)

12. 链接预测 — 5/12

#	算法	状态	复杂度
53	共同邻居	✅	O(deg(u)+deg(v))
54	Jaccard 系数	✅	O(deg(u)+deg(v))
55	Adamic-Adar	✅	O(deg(u)+deg(v))
56	优先连接 (PA)	✅	O(1)
57	资源分配 (RA)	✅	O(deg(u)+deg(v))

---

图结构分析 (已实现)

13. 割点与桥 — 2/5

#	算法	状态	复杂度
58	Tarjan 割点	✅	O(V+E)
59	Tarjan 桥	✅	O(V+E)

14. 稠密子图 — 2/9

#	算法	状态	复杂度
60	K-Core 分解	✅	O(V+E)
61	K-Truss 分解	✅	O(V+E)
62	三角计数	✅	O(V·deg)
63	传递性/聚类系数	✅	O(V·deg²)

15. 图算子 — 9/10

#	操作	状态	复杂度
64	补图	✅	O(V²)
65	反转	✅	O(V+E)
66	交/并/差	✅	O(V+E)
67	笛卡尔积	✅	O(V·V’)
68	张量积	✅	O(V·V’)
69	字典序积	✅	O(V·V’)
70	线图 (Line Graph)	✅	O(V+E)
71	收缩	✅	O(V+E)
72	幂图	✅	O(V²)

16. 特殊图识别 — 4/13

#	算法	状态	复杂度
73	弦图判定	✅	O(V+E)
74	完全图判定	✅	O(V²)
75	二部图判定	✅	O(V+E)
76	正则图判定	✅	O(V+E)

17. 图生成器 — 16 种

#	生成器	状态
77-92	随机图 (Erdős-Rényi / Barabási-Albert / Watts-Strogatz / 网格 / 完全 / 二分 / 树等)	✅

18. I/O 与统计

#	功能	状态
93	DOT 序列化	✅
94	JSON 序列化	✅
95	图统计工具	✅

---

更多信息

• 完整分类覆盖 32 个算法类别，总计约 230+ 算法（含已实现、计划和前沿追踪）
• 各算法详情请参考对应 算法教程 页面
• 设计文档请见 参考文档