使用贪心算法寻找矩阵最小支配集

### 使用贪心算法求解矩阵最小支配集

#### 实现方法概述

最小支配集问题属于组合优化领域的一个经典难题，旨在寻找图中尽可能少数量的顶点使得这些顶点能覆盖所有的其他顶点。对于给定的无向图G=(V,E)，其中V表示节点集合而E代表边的集合，如果存在子集D⊆V满足任意v∈V-D至少有一个邻居u∈D，则称D为G的一个支配集[^1]。

采用贪心策略来构建这样的支配集意味着每次迭代过程中选取当前未被覆盖且拥有最多未标记相邻节点的那个节点加入到支配集中直到所有节点都被处理完毕为止。这种方法虽然无法保证得到全局最优解但在很多情况下可以获得接近最佳的结果并且计算效率较高[^2]。

#### Python代码示例

下面提供了一个简单的Python函数用于演示上述过程：

def greedy_min_dominating_set(graph):
    # 初始化变量
    vertices = set(range(len(graph)))  # 所有顶点列表
    dominating_set = []                 # 当前已选入支配集内的顶点
    
    while vertices:
        max_degree_vertex = None         # 记录本轮选出的最大度数顶点
        max_neighbors_count = -float('inf')  # 初始设为负无穷大
        
        for v in list(vertices):          # 遍历剩余待处理顶点
            neighbors = {i for i, val in enumerate(graph[v]) if val != 0 and i not in dominating_set}
            
            if len(neighbors) > max_neighbors_count:
                max_degree_vertex = v      # 更新最大度数顶点及其邻居数目
                max_neighbors_count = len(neighbors)

        if max_degree_vertex is None:     # 如果找不到新的顶点了就结束循环
            break
            
        dominating_set.append(max_degree_vertex)  # 将该顶点添加至支配集内
        vertices -= ({max_degree_vertex} | {n for n in range(len(graph)) if graph[max_degree_vertex][n]})  # 移除已被覆盖的顶点

    return dominating_set                  # 返回最终获得的支配集


# 测试数据：邻接矩阵形式表示的一张简单无向图
test_graph_matrix = [
    [0, 1, 0, 0],
    [1, 0, 1, 1],
    [0, 1, 0, 0],
    [0, 1, 0, 0]]

print(greedy_min_dominating_set(test_graph_matrix))

此段程序通过不断挑选具有最高连接性的新成员扩充支配集直至完成整个图的遍历操作。注意这里的`graph`参数应当是以二维列表的形式传入，每个元素对应着两个顶点间是否存在直接连通关系（通常用1/0或True/False表示）。