python - 将已见集用于有向图与无向图

Question

我一直在加深对 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)
    

对于无向图可以这样做的原因，即不必像我上面所说的那样在早期将位置添加到可见的位置，是因为它是无向的，我们将再次访问这样的路径并且可以将它添加到已见集以防止我们再次看到它？而在像 key 和房间这样的有向图中，我们不会每次都“访问”房间 0 吗？

Answer 1

访问集的原因本质上是cycle回避，这在有向图中和无向图中都是一个问题。无向图只是有向图的一种特殊情况，其中从 A 到 B 的每条边都有从 B 到 A< 的相反边，所以你可以有循环。在“provinces”中，邻接矩阵定义了每个节点的自循环。

为什么有时会提前初始化访问集，有时会晚一些？它与定向无关。它主要是与检查终端状态的位置有关的实现细节。例如，对于“ key 和房间”，以下两种解决方案均有效。只要在探索之前测试了先前的访问，并且在推送其邻居之前没有意外地标记为已访问，它几乎是一样的。

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)])