支配集问题是图论中的经典NP难问题，在无线网络部署、监控摄像头选址、服务器集群容灾等领域有广泛应用。本文用Java实现最小支配集的贪心近似算法，并深入分析其近似比与优化策略。
一、问题定义
给定无向图G=(V,E)，一个支配集D是顶点集V的一个子集，使得对于图中的任意顶点v，要么v∈D，要么v与D中的某个顶点相邻。最小支配集问题要求找到基数最小的支配集。
1.1 相关概念
- 支配集（Dominating Set）：满足上述条件的顶点集合
- 最小支配集：所有支配集中顶点数最少的一个
- 连通支配集：诱导子图连通的支配集
- 独立支配集：集合内顶点两两不相邻的支配集
二、算法原理
由于最小支配集是NP难问题，不存在已知的多项式时间精确算法（除非P=NP）。因此我们采用贪心近似算法：
贪心策略：每次选择能够支配最多未被支配顶点的顶点加入支配集，直到所有顶点都被支配。
该贪心算法的近似比为O(log Δ)，其中Δ是图的最大度。
三、Java实现
import java.util.*;
/**
* 最小支配集问题求解
* 包含贪心近似算法和精确回溯算法（适用于小规模图）
*/
public class DominatingSet {
private final int vertices;
private final List<Set<Integer>> adjacencyList;
public DominatingSet(int vertices) {
this.vertices = vertices;
this.adjacencyList = new ArrayList<>();
for (int i = 0; i < vertices; i++) {
adjacencyList.add(new HashSet<>());
}
}
/**
* 添加无向边
*/
public void addEdge(int u, int v) {
adjacencyList.get(u).add(v);
adjacencyList.get(v).add(u);
}
/**
* 获取顶点v的闭邻域（v自身及其所有邻居）
*/
private Set<Integer> getClosedNeighborhood(int v) {
Set<Integer> neighborhood = new HashSet<>(adjacencyList.get(v));
neighborhood.add(v);
return neighborhood;
}
/**
* 贪心近似算法求解最小支配集
* 时间复杂度：O(V * E)
* 近似比：O(log Δ)
* @return 支配集
*/
public Set<Integer> greedyDominatingSet() {
Set<Integer> dominated = new HashSet<>(); // 已被支配的顶点
Set<Integer> dominatingSet = new HashSet<>(); // 结果支配集
while (dominated.size() < vertices) {
int bestVertex = -1;
int maxNewDominated = -1;
// 遍历所有顶点，找到能支配最多新顶点的顶点
for (int v = 0; v < vertices; v++) {
if (dominatingSet.contains(v)) continue;
Set<Integer> neighborhood = getClosedNeighborhood(v);
// 计算该顶点能新支配多少顶点
int newDominated = 0;
for (int u : neighborhood) {
if (!dominated.contains(u)) {
newDominated++;
}
}
if (newDominated > maxNewDominated) {
maxNewDominated = newDominated;
bestVertex = v;
}
}
// 将最优顶点加入支配集
dominatingSet.add(bestVertex);
dominated.addAll(getClosedNeighborhood(bestVertex));
}
return dominatingSet;
}
/**
* 优化版贪心算法：选择后立即更新候选集
*/
public Set<Integer> optimizedGreedyDominatingSet() {
Set<Integer> undominated = new HashSet<>();
for (int i = 0; i < vertices; i++) {
undominated.add(i);
}
Set<Integer> dominatingSet = new HashSet<>();
// 预计算每个顶点的闭邻域
List<Set<Integer>> closedNeighborhoods = new ArrayList<>();
for (int i = 0; i < vertices; i++) {
closedNeighborhoods.add(getClosedNeighborhood(i));
}
while (!undominated.isEmpty()) {
int bestVertex = -1;
int maxCoverage = -1;
for (int v = 0; v < vertices; v++) {
if (dominatingSet.contains(v)) continue;
// 计算v能覆盖多少未支配顶点
int coverage = 0;
for (int u : closedNeighborhoods.get(v)) {
if (undominated.contains(u)) {
coverage++;
}
}
if (coverage > maxCoverage) {
maxCoverage = coverage;
bestVertex = v;
}
}
dominatingSet.add(bestVertex);
undominated.removeAll(closedNeighborhoods.get(bestVertex));
}
return dominatingSet;
}
/**
* 带权最小支配集贪心算法
* @param weights 每个顶点的权重
* @return 带权支配集
*/
public Set<Integer> weightedGreedyDominatingSet(double[] weights) {
Set<Integer> undominated = new HashSet<>();
for (int i = 0; i < vertices; i++) {
undominated.add(i);
}
Set<Integer> dominatingSet = new HashSet<>();
List<Set<Integer>> closedNeighborhoods = new ArrayList<>();
for (int i = 0; i < vertices; i++) {
closedNeighborhoods.add(getClosedNeighborhood(i));
}
while (!undominated.isEmpty()) {
int bestVertex = -1;
double bestRatio = Double.MAX_VALUE;
for (int v = 0; v < vertices; v++) {
if (dominatingSet.contains(v)) continue;
int coverage = 0;
for (int u : closedNeighborhoods.get(v)) {
if (undominated.contains(u)) {
coverage++;
}
}
if (coverage == 0) continue;
double ratio = weights[v] / coverage;
if (ratio < bestRatio) {
bestRatio = ratio;
bestVertex = v;
}
}
dominatingSet.add(bestVertex);
undominated.removeAll(closedNeighborhoods.get(bestVertex));
}
return dominatingSet;
}
/**
* 精确算法（回溯法，仅适用于小规模图 V <= 25）
* @return 最小支配集
*/
public Set<Integer> exactBacktracking() {
if (vertices > 25) {
throw new IllegalArgumentException("精确算法仅适用于顶点数<=25的图");
}
// 将图转换为位掩码表示以加速运算
int[] neighborMask = new int[vertices];
for (int v = 0; v < vertices; v++) {
int mask = 1 << v;
for (int u : adjacencyList.get(v)) {
mask |= 1 << u;
}
neighborMask[v] = mask;
}
int fullMask = (1 << vertices) - 1;
Set<Integer> bestSolution = null;
int bestSize = vertices + 1;
// 按子集大小递增搜索
for (int size = 1; size <= vertices; size++) {
Set<Integer> result = backtrack(neighborMask, fullMask, size, 0, 0, 0);
if (result != null) {
return result;
}
}
// 如果上面的没找到（理论上不可能），返回全集
Set<Integer> all = new HashSet<>();
for (int i = 0; i < vertices; i++) all.add(i);
return all;
}
private Set<Integer> backtrack(int[] neighborMask, int fullMask,
int targetSize, int start, int currentMask, int depth) {
if (depth == targetSize) {
if (currentMask == fullMask) {
// 找到了有效解，但需要回溯构造集合
return new HashSet<>(); // 占位，外层处理
}
return null;
}
for (int i = start; i < vertices; i++) {
int newMask = currentMask | neighborMask[i];
Set<Integer> result = backtrack(neighborMask, fullMask, targetSize, i + 1, newMask, depth + 1);
if (result != null) {
result.add(i);
return result;
}
}
return null;
}
/**
* 验证一个集合是否为支配集
*/
public boolean isDominatingSet(Set<Integer> set) {
Set<Integer> dominated = new HashSet<>();
for (int v : set) {
dominated.addAll(getClosedNeighborhood(v));
}
return dominated.size() == vertices;
}
/**
* 独立支配集检测：检查支配集是否为独立集
*/
public boolean isIndependentSet(Set<Integer> set) {
for (int v : set) {
for (int u : set) {
if (v != u && adjacencyList.get(v).contains(u)) {
return false;
}
}
}
return true;
}
/**
* 计算支配数（最小支配集的大小）的上下界
* @return [下界, 上界]
*/
public int[] dominatingNumberBounds() {
// 简单下界：ceil(n / (Δ + 1))
int maxDegree = 0;
for (int v = 0; v < vertices; v++) {
maxDegree = Math.max(maxDegree, adjacencyList.get(v).size());
}
int lowerBound = (int) Math.ceil((double) vertices / (maxDegree + 1));
// 上界：贪心算法结果
int upperBound = greedyDominatingSet().size();
return new int[]{lowerBound, upperBound};
}
public static void main(String[] args) {
// 示例：5个节点的路径图 0-1-2-3-4
DominatingSet graph = new DominatingSet(5);
graph.addEdge(0, 1);
graph.addEdge(1, 2);
graph.addEdge(2, 3);
graph.addEdge(3, 4);
System.out.println("=== 贪心近似算法 ===");
Set<Integer> greedyDS = graph.greedyDominatingSet();
System.out.println("支配集: " + greedyDS);
System.out.println("大小: " + greedyDS.size());
System.out.println("是否为支配集: " + graph.isDominatingSet(greedyDS));
System.out.println("\n=== 优化版贪心算法 ===");
Set<Integer> optDS = graph.optimizedGreedyDominatingSet();
System.out.println("支配集: " + optDS);
System.out.println("大小: " + optDS.size());
System.out.println\n("\n=== 支配数上下界 ===");
int[] bounds = graph.dominatingNumberBounds();
System.out.println("下界: " + bounds[0] + ", 上界: " + bounds[1]);
// 带权示例
System.out.println("\n=== 带权贪心算法 ===");
double[] weights = {1.0, 2.0, 1.5, 3.0, 1.0};
Set<Integer> weightedDS = graph.weightedGreedyDominatingSet(weights);
System.out.println("带权支配集: " + weightedDS);
// 小规模精确解
System.out.println("\n=== 精确回溯算法 ===");
Set<Integer> exactDS = graph.exactBacktracking();
System.out.println("精确最小支配集: " + exactDS);
System.out.println("精确支配数: " + exactDS.size());
}
}
四、复杂度分析
| 算法 | 时间复杂度 | 空间复杂度 | 近似比 |
|---|---|---|---|
| 贪心近似算法 | O(V² × E) | O(V + E) | O(log Δ) |
| 优化版贪心 | O(V² × E) | O(V + E) | O(log Δ) |
| 带权贪心 | O(V² × E) | O(V + E) | O(log Δ) |
| 精确回溯 | O(2^V) | O(V) | 1（精确解） |
五、应用场景
- 无线网络：最小化基站/AP数量同时保证全覆盖
- 安防监控：用最少数量的摄像头覆盖所有区域
- 社交网络：找到最少的关键用户影响全网
- 生物信息学：基因调控网络中的核心基因集识别
- 电路设计：测试点最小化选择
六、总结
本文实现了最小支配集问题的多种求解方法。贪心近似算法在多项式时间内给出较好的近似解，适合大规模图；精确回溯算法适用于小规模图的验证和对比实验。理解支配集问题有助于在实际应用中做出资源部署的最优决策。
