图算法是程序员面试和真实工程里最重要的领域之一 —— 社交网络、推荐系统、地图导航、依赖管理、调度系统全靠它。这篇文章把 BFS、DFS、Dijkstra、A*、拓扑排序、最小生成树、并查集等核心图算法一次讲透。
图的表示
// 邻接表(稀疏图,最常用)
const graph = {
'A': ['B', 'C'],
'B': ['A', 'D'],
'C': ['A', 'D', 'E'],
...
};
// 邻接矩阵(稠密图)
const matrix = [
// A B C D
[0, 1, 1, 0], // A
[1, 0, 0, 1], // B
[1, 0, 0, 1], // C
[0, 1, 1, 0], // D
];
// 带权图
const weighted = {
'A': [['B', 5], ['C', 3]],
'B': [['A', 5], ['D', 2]],
...
};BFS(广度优先搜索)
从起点开始,一层层向外扩展。用队列实现。适合"最短路径(无权)"、"层级遍历"。
function bfs(graph, start) {
const visited = new Set([start]);
const queue = [start];
while (queue.length) {
const node = queue.shift();
console.log(node);
for (const neighbor of graph[node]) {
if (!visited.has(neighbor)) {
visited.add(neighbor);
queue.push(neighbor);
}
}
}
}
// 最短路径(无权图)
function shortestPath(graph, start, end) {
const queue = [[start, 0]];
const visited = new Set([start]);
while (queue.length) {
const [node, dist] = queue.shift();
if (node === end) return dist;
for (const neighbor of graph[node]) {
if (!visited.has(neighbor)) {
visited.add(neighbor);
queue.push([neighbor, dist + 1]);
}
}
}
return -1;
}BFS 的层级特性让它适合"找最近的"问题。社交网络"共同好友"、棋盘游戏的"最少步数"都是 BFS。
DFS(深度优先搜索)
从起点出发,沿一条路走到底再回溯。用递归 / 栈实现。适合"路径搜索"、"连通分量"、"拓扑排序"。
function dfs(graph, node, visited = new Set()) {
if (visited.has(node)) return;
visited.add(node);
console.log(node);
for (const neighbor of graph[node]) {
dfs(graph, neighbor, visited);
}
}
// 找所有连通分量
function countComponents(graph) {
const visited = new Set();
let count = 0;
for (const node in graph) {
if (!visited.has(node)) {
dfs(graph, node, visited);
count++;
}
}
return count;
}Dijkstra:加权最短路径
从源点到所有点的最短路径(边权非负)。用优先队列实现。
function dijkstra(graph, start) {
const dist = {};
for (const node in graph) dist[node] = Infinity;
dist[start] = 0;
const pq = [[0, start]]; // [距离, 节点]
while (pq.length) {
pq.sort((a, b) => a[0] - b[0]); // 实际应用 MinHeap
const [d, node] = pq.shift();
if (d > dist[node]) continue;
for (const [neighbor, weight] of graph[node]) {
const newDist = d + weight;
if (newDist < dist[neighbor]) {
dist[neighbor] = newDist;
pq.push([newDist, neighbor]);
}
}
}
return dist;
}Dijkstra 应用:地图导航、网络路由(OSPF 协议)、机器人路径规划。不能处理负权边(需要 Bellman-Ford 或 SPFA)。
A*:启发式最短路径
Dijkstra 朝所有方向扩展,慢。A* 加"启发函数"(估计当前点到终点的距离),优先朝目标方向扩展。游戏寻路标配。
function astar(start, end, neighborsFn, heuristicFn) {
const gScore = { [start]: 0 };
const fScore = { [start]: heuristicFn(start, end) };
const openSet = [[fScore[start], start]];
while (openSet.length) {
openSet.sort((a, b) => a[0] - b[0]);
const [_, current] = openSet.shift();
if (current === end) return reconstructPath(...);
for (const [neighbor, weight] of neighborsFn(current)) {
const tentativeG = gScore[current] + weight;
if (tentativeG < (gScore[neighbor] ?? Infinity)) {
gScore[neighbor] = tentativeG;
fScore[neighbor] = tentativeG + heuristicFn(neighbor, end);
openSet.push([fScore[neighbor], neighbor]);
}
}
}
return null;
}
// 启发函数(网格地图):曼哈顿距离
function manhattan(a, b) {
return Math.abs(a.x - b.x) + Math.abs(a.y - b.y);
}启发函数选得好,A* 比 Dijkstra 快几个数量级。但启发要满足"不超过实际距离"(admissible)才保证最优。
拓扑排序
有向无环图(DAG)的线性序列,每条边"从前向后"。应用:
- 编译依赖(头文件先编译完才能编译用它的)。
- 课程先修关系(高数 → 微积分 → 数学分析)。
- 任务调度(任务 A 完成才能开始 B)。
- Webpack / Vite 依赖图。
// Kahn 算法:基于入度
function topoSort(graph) {
const inDegree = {};
for (const node in graph) inDegree[node] = 0;
for (const node in graph) for (const next of graph[node]) inDegree[next]++;
const queue = Object.keys(inDegree).filter(n => inDegree[n] === 0);
const result = [];
while (queue.length) {
const node = queue.shift();
result.push(node);
for (const next of graph[node]) {
if (--inDegree[next] === 0) queue.push(next);
}
}
if (result.length !== Object.keys(graph).length) {
throw new Error('图有环');
}
return result;
}最小生成树:Kruskal / Prim
带权无向图,选 n-1 条边让所有点连通且总权最小。应用:网络布线、电网设计、聚类算法。
Kruskal(基于边)
function kruskal(n, edges) {
edges.sort((a, b) => a[2] - b[2]); // 按权重升序
const uf = new UnionFind(n);
const mst = [];
let totalWeight = 0;
for (const [u, v, w] of edges) {
if (uf.union(u, v)) {
mst.push([u, v, w]);
totalWeight += w;
if (mst.length === n - 1) break;
}
}
return { mst, totalWeight };
}Prim(基于点)
从任一点开始,每次加权重最小的"连接外部"的边。和 Dijkstra 结构类似。
图的连通性
有向图强连通分量(Tarjan / Kosaraju)
强连通:任意两点都互相可达。社交网络分析、网页重要性算法(PageRank 的基础)。
桥与割点
桥:删了让图不连通的边;割点:删了让图不连通的点。应用:网络可靠性分析、单点故障检测。
实战:依赖管理
// npm / pip 装包时的依赖图分析
function resolveDeps(packages) {
const graph = {};
for (const pkg of packages) {
graph[pkg.name] = pkg.dependencies;
}
// 检测循环依赖
function detectCycle(node, visiting = new Set(), visited = new Set()) {
if (visiting.has(node)) throw new Error(`circular: ${node}`);
if (visited.has(node)) return;
visiting.add(node);
for (const dep of graph[node] || []) {
detectCycle(dep, visiting, visited);
}
visiting.delete(node);
visited.add(node);
}
for (const name in graph) detectCycle(name);
// 拓扑排序得到安装顺序
return topoSort(graph);
}实战:社交推荐"二度好友"
function friendsOfFriends(user, graph, depth = 2) {
const visited = new Set([user]);
const result = new Map(); // 二度好友 -> 共同好友数
const queue = [[user, 0]];
while (queue.length) {
const [node, d] = queue.shift();
if (d > depth) continue;
for (const friend of graph[node]) {
if (visited.has(friend)) continue;
if (d === 1) {
// friend 是 user 的二度好友,node 是中介
result.set(friend, (result.get(friend) ?? 0) + 1);
}
queue.push([friend, d + 1]);
}
visited.add(node);
}
// 按共同好友数排序
return [...result.entries()].sort((a, b) => b[1] - a[1]);
}大图算法
真实社交图、Web 图有数十亿节点,内存装不下。需要专门系统:
- Apache Spark GraphX:分布式图计算。
- Neo4j:图数据库,Cypher 查询语言。
- Pregel / Giraph:Google 提出的图计算模型,"think like a vertex"。
- NebulaGraph:开源分布式图数据库,支持千亿点边规模。
写在最后
图算法是计算机科学的"百搭工具"。看似抽象,但任何"实体之间有关系"的场景都可以建模成图,然后用图算法解决。社交、推荐、地图、调度、依赖分析、生物网络 —— 全都靠它。掌握图算法,你解决问题的"武器库"会扩大一个数量级。
一图看懂
BFS 层次遍历一图看懂:
—— 别看了 · 2026声明：本站所有文章，如无特殊说明或标注，均为本站原创发布。任何个人或组织，在未征得本站同意时，禁止复制、盗用、采集、发布本站内容到任何网站、书籍等各类媒体平台。如若本站内容侵犯了原著者的合法权益，可联系我们进行处理 邮箱1846861578@qq.com。
