Python实现不邻接植花：基于贪心策略的图着色算法
本文详解如何使用Python解决“不邻接植花”问题。通过构建无向图的邻接表，利用贪心策略遍历每个节点，结合Python集合的差集运算快速排除相邻花园已选的花色，确保任意相连花园花色不同。文章提供两种实现思路，重点解析利用集合操作简化逻辑的方法，并包含完整代码示例与复杂度分析。
问题描述与约束条件
假设有 N 个花园，编号从 1 到 N。我们的任务是在每个花园中种植四种花中的一种。
输入数据 paths[i] = [x, y] 表示花园 x 与花园 y 之间存在一条双向路径。
关键约束条件是：没有任何一个花园连接的路径数量超过 3 条（即每个节点的度数不超过 3）。
目标是确定每个花园种植的花种，使得通过路径直接相连的任意两个花园，其种植的花种必须互不相同。
最终结果需以数组形式返回，记为 answer。其中 answer[i] 代表第 (i+1) 号花园种植的花种编号，花种编号为 1、2、3 或 4。题目保证存在满足条件的解。
示例 1：
输入：N = 3, paths = [[1,2],[2,3],[3,1]]
输出：[1,2,3]
示例 2：
输入：N = 4, paths = [[1,2],[3,4]]
输出：[1,2,1,2]
示例 3：
输入：N = 4, paths = [[1,2],[2,3],[3,4],[4,1],[1,3],[2,4]]
输出：[1,2,3,4]
提示：
数据范围约束如下： 1 <= N <= 10000 0 <= paths.size <= 20000
根据题意，不存在任何花园拥有 4 条或更多连接路径。 题目保证必定存在合法的种植方案。
Python基础工具准备
知识准备
在 Python 中，可以使用列表（list）模拟队列行为，并通过 append 方法添加元素。
可以使用字典（dict）来存储每个花园的相邻节点信息，例如定义 nei = {}。
在集合（set）操作中，可以使用 for 循环进行遍历。
例如，通过 {res[j] for j in G[i]} 可以快速获取邻居节点的花色集合。
了解集合的 pop 函数用法。
flowers = {1,2,3,4} # 集合之间可以直接进行相减操作 flowers.pop() # 注意：集合不支持通过索引获取特定元素的操作 print(flowers)
输出结果示例：{2,3,4}。需要注意的是，集合中的 pop 操作是从左侧（即哈希表内部顺序）移除并返回一个元素，并非按数值大小排序后的顺序。
掌握集合的相减运算。
flowers = {1,2,3,4} h = {0} flowers-h
输出结果：{1,2,3,4}。因为集合 h 中的元素 0 不在 flowers 中，所以相减后 flowers 保持不变。
Python代码实现方案
我的题解
题解1
class Solution:
# 整体思路采用BFS方法,还需考虑不连通图的问题,然后着手结果唯一
def gardenNoAdj(self, N: int, paths: List[List[int]]) -> List[int]:
#构建一个answer数组
answer = [0 for _ in range(N)]
#构建所有节点
all_nodes = []
[all_nodes.append(i) for i in range(1,N+1)]
#构建visted列表
visted = dict.fromkeys(all_nodes, 0)
#初始化nei字典元素为空列表
nei = [[] for _ in range(N)]
# 构建无向邻接表，无邻居则不构建
for path in paths:
nei[path[0]-1].append(path[1])
nei[path[1]-1].append(path[0])
#遍历每一个点，每个点保证自己邻接点不是和自己相同就行
answer[0] = 1
for node in range(1,N+1): #遍历所有节点
visted[node] = 1
fix = set()
if(answer[node-1]==0): #如果为0,说明不是连通图
answer[node-1] = 1
flowers=[1,2,3,4]
nei[node-1] = sorted(nei[node-1]) #排序邻居节点
flowers.pop(answer[node-1]-1) #弹出父节点的flowers
for sinode in nei[node-1]: #遍历邻居
if(visted[sinode] == 0): #如果邻居未被访问过
answer[sinode-1] = flowers[0] #使用1,弹出1
flowers.pop(0)
else: #如果邻居被访问过
if(answer[sinode-1]==answer[node-1]):
answer[node-1] = flowers[0]
flowers.pop(0)
fix.add(answer[sinode-1])
if not fix:
continue
else:
flowers=[1,2,3,4]
for a_val in list(fix):
flowers.remove(a_val)
answer[node-1] = flowers[0]
return answer
简化方法：利用集合的快速特性解决问题。
class Solution:
def gardenNoAdj(self, N: int, paths: List[List[int]]) -> List[int]:
#构建一个answer数组
answer = [0]*N
#初始化nei字典元素为空列表
nei = [[] for _ in range(N)]
# 构建无向邻接表，无邻居则不构建
for path in paths:
nei[path[0]-1].append(path[1])
nei[path[1]-1].append(path[0])
for node in range(1,N+1): #遍历所有节点
flowers={1,2,3,4}
#临时存储邻居含有的花类型
a = set()
for sinode in nei[node-1]: #遍历邻居
a.add(answer[sinode-1])
flowers = flowers - a
answer[node-1] = flowers.pop()
return answer以上就是本文的全部内容，希望对大家的学习有所帮助，也希望大家多多支持本站。
免责声明：本文内容仅供参考，不代表本站观点。转载或引用请注明出处。
