Duyệt đồ thị (BFS/DFS)

from collections import deque
 
def bfs(graph, start):
    visited = set([start])
    queue = deque([start])
    result = []
    
    while queue:
        node = queue.popleft()
        result.append(node)
        
        for neighbor in graph.get(node, []):
            if neighbor not in visited:
                visited.add(neighbor)
                queue.append(neighbor)
    
    return result

fun bfs(graph: Map<Int, List<Int>>, start: Int): List<Int> {
    val visited = mutableSetOf(start)
    val queue = ArrayDeque<Int>()
    queue.addLast(start)
    val result = mutableListOf<Int>()
    
    while (queue.isNotEmpty()) {
        val node = queue.removeFirst()
        result.add(node)
        
        for (neighbor in graph[node] ?: emptyList()) {
            if (neighbor !in visited) {
                visited.add(neighbor)
                queue.addLast(neighbor)
            }
        }
    }
    return result
}

List<int> bfs(Map<int, List<int>> graph, int start) {
  Set<int> visited = {start};
  Queue<int> queue = Queue()..add(start);
  List<int> result = [];
  
  while (queue.isNotEmpty) {
    int node = queue.removeFirst();
    result.add(node);
    
    for (int neighbor in graph[node] ?? []) {
      if (!visited.contains(neighbor)) {
        visited.add(neighbor);
        queue.add(neighbor);
      }
    }
  }
  return result;
}

func bfs(_ graph: [Int: [Int]], _ start: Int) -> [Int] {
    var visited = Set([start])
    var queue = [start]
    var result = [Int]()
    
    while !queue.isEmpty {
        let node = queue.removeFirst()
        result.append(node)
        
        for neighbor in graph[node] ?? [] {
            if !visited.contains(neighbor) {
                visited.insert(neighbor)
                queue.append(neighbor)
            }
        }
    }
    return result
}

List<Integer> bfs(Map<Integer, List<Integer>> graph, int start) {
    Set<Integer> visited = new HashSet<>();
    Queue<Integer> queue = new LinkedList<>();
    List<Integer> result = new ArrayList<>();
    
    visited.add(start);
    queue.offer(start);
    
    while (!queue.isEmpty()) {
        int node = queue.poll();
        result.add(node);
        
        for (int neighbor : graph.getOrDefault(node, List.of())) {
            if (!visited.contains(neighbor)) {
                visited.add(neighbor);
                queue.offer(neighbor);
            }
        }
    }
    return result;
}

def dfs(graph, start, visited=None):
    if visited is None:
        visited = set()
    
    visited.add(start)
    result = [start]
    
    for neighbor in graph.get(start, []):
        if neighbor not in visited:
            result.extend(dfs(graph, neighbor, visited))
    
    return result

fun dfs(graph: Map<Int, List<Int>>, start: Int, visited: MutableSet<Int> = mutableSetOf()): List<Int> {
    visited.add(start)
    val result = mutableListOf(start)
    
    for (neighbor in graph[start] ?: emptyList()) {
        if (neighbor !in visited) {
            result.addAll(dfs(graph, neighbor, visited))
        }
    }
    return result
}

List<int> dfs(Map<int, List<int>> graph, int start, [Set<int>? visited]) {
  visited ??= {};
  visited.add(start);
  List<int> result = [start];
  
  for (int neighbor in graph[start] ?? []) {
    if (!visited.contains(neighbor)) {
      result.addAll(dfs(graph, neighbor, visited));
    }
  }
  return result;
}

func dfs(_ graph: [Int: [Int]], _ start: Int, _ visited: inout Set<Int>) -> [Int] {
    visited.insert(start)
    var result = [start]
    
    for neighbor in graph[start] ?? [] {
        if !visited.contains(neighbor) {
            result.append(contentsOf: dfs(graph, neighbor, &visited))
        }
    }
    return result
}

List<Integer> dfs(Map<Integer, List<Integer>> graph, int start, Set<Integer> visited) {
    visited.add(start);
    List<Integer> result = new ArrayList<>();
    result.add(start);
    
    for (int neighbor : graph.getOrDefault(start, List.of())) {
        if (!visited.contains(neighbor)) {
            result.addAll(dfs(graph, neighbor, visited));
        }
    }
    return result;
}

def num_islands(grid):
    if not grid:
        return 0
    
    rows, cols = len(grid), len(grid[0])
    count = 0
    
    def dfs(r, c):
        if r < 0 or r >= rows or c < 0 or c >= cols or grid[r][c] == '0':
            return
        grid[r][c] = '0'
        dfs(r + 1, c)
        dfs(r - 1, c)
        dfs(r, c + 1)
        dfs(r, c - 1)
    
    for r in range(rows):
        for c in range(cols):
            if grid[r][c] == '1':
                count += 1
                dfs(r, c)
    
    return count

fun numIslands(grid: Array<CharArray>): Int {
    if (grid.isEmpty()) return 0
    val rows = grid.size
    val cols = grid[0].size
    var count = 0
    
    fun dfs(r: Int, c: Int) {
        if (r !in 0 until rows || c !in 0 until cols || grid[r][c] == '0') return
        grid[r][c] = '0'
        dfs(r + 1, c); dfs(r - 1, c); dfs(r, c + 1); dfs(r, c - 1)
    }
    
    for (r in 0 until rows) {
        for (c in 0 until cols) {
            if (grid[r][c] == '1') { count++; dfs(r, c) }
        }
    }
    return count
}

int numIslands(List<List<String>> grid) {
  if (grid.isEmpty) return 0;
  int rows = grid.length, cols = grid[0].length;
  int count = 0;
  
  void dfs(int r, int c) {
    if (r < 0 || r >= rows || c < 0 || c >= cols || grid[r][c] == '0') return;
    grid[r][c] = '0';
    dfs(r + 1, c); dfs(r - 1, c); dfs(r, c + 1); dfs(r, c - 1);
  }
  
  for (int r = 0; r < rows; r++) {
    for (int c = 0; c < cols; c++) {
      if (grid[r][c] == '1') { count++; dfs(r, c); }
    }
  }
  return count;
}

func numIslands(_ grid: inout [[Character]]) -> Int {
    if grid.isEmpty { return 0 }
    let rows = grid.count, cols = grid[0].count
    var count = 0
    
    func dfs(_ r: Int, _ c: Int) {
        guard r >= 0, r < rows, c >= 0, c < cols, grid[r][c] == "1" else { return }
        grid[r][c] = "0"
        dfs(r + 1, c); dfs(r - 1, c); dfs(r, c + 1); dfs(r, c - 1)
    }
    
    for r in 0..<rows {
        for c in 0..<cols {
            if grid[r][c] == "1" { count += 1; dfs(r, c) }
        }
    }
    return count
}

int numIslands(char[][] grid) {
    if (grid.length == 0) return 0;
    int rows = grid.length, cols = grid[0].length;
    int count = 0;
    
    for (int r = 0; r < rows; r++) {
        for (int c = 0; c < cols; c++) {
            if (grid[r][c] == '1') { count++; dfs(grid, r, c); }
        }
    }
    return count;
}
 
void dfs(char[][] grid, int r, int c) {
    if (r < 0 || r >= grid.length || c < 0 || c >= grid[0].length || grid[r][c] == '0') return;
    grid[r][c] = '0';
    dfs(grid, r + 1, c); dfs(grid, r - 1, c); dfs(grid, r, c + 1); dfs(grid, r, c - 1);
}