python - 使用有向图与无向图的可见集
问题描述
我一直在加深对 LeetCode 上无向图与无向图问题算法的理解。我意识到的关键区别在于像841 Keys and Rooms这样的问题,因为这是定向的,我需要将“0”节点添加到所见集。特别是早期的这条线:
seen_rooms.add(0)
另一方面,对于547. Number of Provinces,因为该图是无向的,我从不需要“早期”添加它。我可以稍后在我的循环中添加它
问题 547:
class Solution():
def findCircleNum(self, A):
#Finds your neighboring cities
seen_cities = set()
def find_cities(cur_city):
nei_cities = A[cur_city]
#First iter (0) nei city
#cur_city = 0
#find_cities (0) go through neighbors of 0
#Don't need to add b/c this is going through it each time so when 1 -> 2 we would have had 1 <- 2 as well
# seen_cities.add(cur_city)
for nei_city, can_go in enumerate(nei_cities):
if can_go == 1 and nei_city not in seen_cities:
seen_cities.add(nei_city)
find_cities(nei_city)
#Go a DFS on all neighboring cities
provinces = 0
for city in range(len(A)):
#We haven't visited the city
if city not in seen_cities:
# seen_cities.add(city)
find_cities(city)
#After the above DFS I would have found all neighboring cities and increase it's province by 1
#Then go onto the next one's
provinces += 1
return provinces
问题 841
class Solution:
def canVisitAllRooms(self, rooms: List[List[int]]) -> bool:
#canvisitallrooms
#pos means you can visit such rooms
#This one is directed so u needa add it ahead of time
total_rooms = []
#When adding to the stack we needa add to seen as well
stack = [0]
seen_rooms = set()
seen_rooms.add(0)
#We never necessairly mentioned room 0 so we need to add room 0 since it STARTS there as well compared to another prob like 547
#[[1],[2],[3],[]]
while stack:
cur_room = stack.pop()
nei_rooms = rooms[cur_room]
for nei_room in nei_rooms:
if nei_room not in seen_rooms:
seen_rooms.add(nei_room)
stack.append(nei_room)
return len(seen_rooms) == len(rooms)
对于无向图可以这样做的原因,即不必像我上面所说的那样将位置添加到早期看到的位置,是因为它是无向的,我们将再次访问这样的路径并将其添加到看到的设置阻止我们再次看到它?而在像钥匙和房间这样的有向图中,我们不会潜在地再次“访问”房间 0 吗?
解决方案
访问集的原因本质上是避免循环,这在有向图和无向图中都是一个问题。无向图只是有向图的一种特殊情况,其中从 到 的每条边都有从A
到的对B
边,因此您可以有循环。在“省”中,邻接矩阵由每个节点的自循环定义。B
A
为什么有时您会提前初始化访问集,有时会延迟?它与定向无关;它主要是一个实现细节,与您检查终端状态的位置有关。例如,在“钥匙和房间”上,以下两种解决方案都有效。只要在探索之前测试了先前的访问,并且在推送邻居之前没有意外标记为已访问,它几乎是一样的。
def canVisitAllRooms(self, rooms: List[List[int]]) -> bool:
visited = set([0]) # <--
stack = [0]
while stack:
for key in rooms[stack.pop()]:
if key not in visited:
visited.add(key)
stack.append(key)
return len(visited) == len(rooms)
def canVisitAllRooms(self, rooms: List[List[int]]) -> bool:
visited = set()
stack = [0]
while stack:
i = stack.pop()
visited.add(i) # <--
for key in rooms[i]:
if key not in visited:
stack.append(key)
return len(visited) == len(rooms)
在“省”上情况相同——只要您确保对所有内容进行一次探索,您就可以移动检查并设置插入。
例如,我下面的解决方案(我没有查看您的代码就编写了该解决方案)执行访问检查并在递归调用开始时标记一次访问的根节点。您的版本进行了两次检查,一次在主循环中迭代所有节点,第二次在邻居循环内。
如果你真的想要,你可以更进一步,在递归调用之前在调用者中“准备好”访问的集合,但这不是一种特别优雅的方法,因为它将更多的递归逻辑传播到两个地方。
def findCircleNum(self, adj_mat: List[List[int]]) -> int:
visited = set()
def explore(i):
if i not in visited:
visited.add(i)
for j, x in enumerate(adj_mat[i]):
if x:
explore(j)
return True
return len([i for i, _ in enumerate(adj_mat) if explore(i)])
推荐阅读
- amazon-web-services - 将 ETL 作业用于 aws 胶水时,如何控制 RDS 的摄取率?
- google-apps-script - 实施附加组件 doPost 和 doGet 触发器
- python - 你如何使用 Python xpath 从网页获取信息?
- google-bigquery - 主键同时具有整数和字符串的左连接
- javascript - 移除
使用javascript从数组中标记
- spring-boot - Spring Boot LDAP 模板查询
- sql - 为表中的控件插入创建约束
- r - 执行 kproto 后的数据帧计算
- typescript - 带有 Typescript 的功能性 Vue 组件 - 访问方法
- unity3d - 将视频从 Unity 的相机目标纹理流式传输到 RTSP