独立集（Independent Set）是图论里非常经典的一个问题：给定一个无向图，从中挑出一批顶点，使得任意两个被选中的顶点之间都没有边相连，这批顶点就构成一个独立集。这个问题在冲突调度、频段分配、社交网络分析等场景都有直接应用。本文使用Node.js从零实现独立集的求解，包括数据结构设计、判断校验、贪心求解极大独立集以及用回溯法搜索最大独立集。
一、图的数据结构与独立集定义
在动手写算法之前，先把图的结构确定下来。无向图最常用的存储方式是邻接表，也就是为每个顶点维护一个邻居列表。在Node.js中，可以用Map配合Set来实现，Set的哈希查找是常数级别的，后面判断两个顶点是否相邻时非常高效。
class Graph {
constructor() {
this.adj = new Map(); // 邻接表：顶点 -> 邻居集合
}
addVertex(v) {
if (!this.adj.has(v)) {
this.adj.set(v, new Set());
}
}
addEdge(u, v) {
this.addVertex(u);
this.addVertex(v);
this.adj.get(u).add(v);
this.adj.get(v).add(u); // 无向图，边要加两次
}
vertices() {
return [...this.adj.keys()];
}
hasEdge(u, v) {
return this.adj.has(u) && this.adj.get(u).has(v);
}
}有了图结构，先解决最基础的问题：给定一个顶点集合，判断它是不是独立集。校验逻辑很直接，遍历集合中的每一对顶点，只要发现任意一对之间存在边，就立即返回false。双重循环的写法虽然朴素，但思路清晰，对于集合规模不大的情况完全够用。
function isIndependentSet(graph, vertices) {
const n = vertices.length;
for (let i = 0; i < n; i++) {
for (let j = i + 1; j < n; j++) {
if (graph.hasEdge(vertices[i], vertices[j])) {
return false; // 发现一条边，说明集合内两顶点相邻，不独立
}
}
}
return true;
}这里需要区分两个容易混淆的概念：极大独立集和最大独立集。极大独立集指的是不能再向里面添加任何顶点同时保持独立性的集合，一个图通常有很多个极大独立集；最大独立集则是所有独立集中规模最大的那一个，其顶点数量称为图的独立数。求最大独立集是NP难问题，目前没有多项式时间的精确算法，所以实用的策略通常是：小规模数据用回溯精确求解，大规模数据用贪心近似。
二、贪心算法求极大独立集
贪心算法的思路很好理解：每次从图中挑选一个顶点加入结果集，然后把它以及它的所有邻居从候选中移除，重复这个过程直到候选集为空。这样得到的集合一定是一个极大独立集，因为剩下的任何顶点都必然与已选顶点相邻，无法再加入。贪心的优势是速度极快，整体复杂度大约是O(V+E)，缺点是不保证结果最优。
function greedyMaximalIndependentSet(graph) {
const result = [];
const excluded = new Set(); // 已被覆盖的顶点（已选或已选的邻居）
for (const v of graph.vertices()) {
if (excluded.has(v)) continue;
result.push(v); // 选中当前顶点
for (const nb of graph.adj.get(v)) {
excluded.add(nb); // 排除其所有邻居
}
}
return result;
}不同的遍历顺序会得到不同大小的极大独立集。一个常见的改进策略是按度数从低到高处理顶点，度数低的顶点邻居少，选中它之后牺牲掉的候选顶点也少，通常能换来更大的独立集。改进后的代码只需要在排序上多做一点工作。
function greedyByDegree(graph) {
const excluded = new Set();
const result = [];
// 按度数升序排列，优先处理邻居少的顶点
const order = graph.vertices().sort(
(a, b) => graph.adj.get(a).size - graph.adj.get(b).size
);
for (const v of order) {
if (excluded.has(v)) continue;
result.push(v);
for (const nb of graph.adj.get(v)) {
excluded.add(nb);
}
}
return result;
}需要提醒的是，无论怎么调整贪心策略，都无法从理论上保证逼近最优解。对于随机图，按度数排序的贪心表现通常不错，但在一些精心构造的图上，贪心结果与真正的最大独立集可能差距明显。如果对结果规模有严格要求，就得考虑下面的精确搜索方法。
三、回溯法求最大独立集
精确求解最大独立集的经典手段是回溯搜索。维护一个当前正在构建的候选集，逐个尝试每个顶点：如果某顶点与候选集中的顶点都不相邻，就可以选择它并递归处理后续顶点，也可以直接跳过它。所有分支走完后，记录下遇到的最大候选集即可。为了剪枝，还可以在剩余顶点数加上当前集合大小都无法超过已知最优时提前返回。
function maximumIndependentSet(graph) {
const vs = graph.vertices();
let best = [];
function backtrack(start, current) {
// 剪枝：即使剩余全部加入也无法超越当前最优
if (current.length + (vs.length - start) <= best.length) return;
if (start === vs.length) {
if (current.length > best.length) best = [...current];
return;
}
const v = vs[start];
// 检查v与当前集合中的顶点是否都不相邻
const compatible = current.every(u => !graph.hasEdge(u, v));
if (compatible) {
current.push(v);
backtrack(start + 1, current); // 选择v
current.pop();
}
backtrack(start + 1, current); // 跳过v
}
backtrack(0, []);
return best;
}回溯法的时间复杂度在最坏情况下是指数级的，随着顶点数增加，运行时间会迅速膨胀。经验上，几十个顶点的稀疏图还能接受，上百个顶点就可能跑不动了。除了上面用到的简单剪枝，还有更高级的分支限界策略，比如结合图着色上界来估计剩余顶点能贡献的最大数量，可以显著减少搜索空间，感兴趣的读者可以在此基础上继续扩展。
最后写一段测试代码验证整体流程，构造一个小图，分别检查独立集校验、贪心结果和精确解，确认逻辑正确后再放到实际项目中使用。
const g = new Graph(); [[1,2],[1,3],[2,4],[3,4],[4,5]].forEach(([u,v]) => g.addEdge(u, v)); console.log(isIndependentSet(g, [1, 5])); // true，1和5之间没有边 console.log(greedyMaximalIndependentSet(g)); // 贪心得到的极大独立集 console.log(maximumIndependentSet(g)); // 精确的最大独立集
总结一下，Node.js实现独立集并不复杂：邻接表负责存图，双循环校验负责判断，贪心算法快速拿到可用的极大独立集，回溯法在数据规模可控时给出精确答案。实际工程中，先估算图的规模再选择策略，通常是最稳妥的做法。