1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
function findConnectedComponents(graph) {
  // Set to keep track of visited vertices
  const visited = new Set();
  
  // Array to store all connected components
  const components = [];
  
  // For each vertex in the graph
  for (const vertex in graph) {
    // If this vertex has not been visited yet
    if (!visited.has(vertex)) {
      // Find all vertices in the same component as this vertex
      const component = [];
      dfs(graph, vertex, visited, component);
      
      // Add this component to the list of components
      components.push(component);
    }
  }
  
  return components;
}
 
function dfs(graph, vertex, visited, component) {
  // Mark the vertex as visited
  visited.add(vertex);
  
  // Add the vertex to the current component
  component.push(vertex);
  
  // Visit all neighbors
  for (const neighbor of graph[vertex]) {
    if (!visited.has(neighbor)) {
      dfs(graph, neighbor, visited, component);
    }
  }
}
 
// Example usage:
const undirectedGraph = {
  'A': ['B', 'C'],
  'B': ['A', 'D', 'E'],
  'C': ['A', 'F'],
  'D': ['B'],
  'E': ['B'],
  'F': ['C'],
  'G': ['H'],
  'H': ['G'],
  'I': []
};
 
const components = findConnectedComponents(undirectedGraph);
console.log(components);
// Output: [['A', 'B', 'D', 'E', 'C', 'F'], ['G', 'H'], ['I']]

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
function findPath(graph, start, end) {
  // Set to keep track of visited vertices
  const visited = new Set();
  
  // Array to store the path
  const path = [];
  
  // Find a path from start to end
  const pathExists = dfs(graph, start, end, visited, path);
  
  // If a path exists, return it; otherwise, return an empty array
  return pathExists ? path : [];
}
 
function dfs(graph, current, end, visited, path) {
  // Mark the current vertex as visited
  visited.add(current);
  
  // Add the current vertex to the path
  path.push(current);
  
  // If we've reached the end, we've found a path
  if (current === end) {
    return true;
  }
  
  // Visit all neighbors
  for (const neighbor of graph[current]) {
    if (!visited.has(neighbor)) {
      // If a path is found through this neighbor, return true
      if (dfs(graph, neighbor, end, visited, path)) {
        return true;
      }
    }
  }
  
  // If no path is found through this vertex, remove it from the path
  path.pop();
  
  // No path found
  return false;
}
 
// Example usage:
const graph = {
  'A': ['B', 'C'],
  'B': ['A', 'D', 'E'],
  'C': ['A', 'F'],
  'D': ['B'],
  'E': ['B', 'F'],
  'F': ['C', 'E']
};
 
const path = findPath(graph, 'A', 'F');
console.log(path); // Output: ['A', 'C', 'F']

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
function numIslands(grid) {
  if (!grid || grid.length === 0) {
    return 0;
  }
  
  const rows = grid.length;
  const cols = grid[0].length;
  let count = 0;
  
  // Function to check if a cell is valid and is land
  function isValid(row, col) {
    return row >= 0 && row < rows && col >= 0 && col < cols && grid[row][col] === '1';
  }
  
  // DFS to mark all connected land cells as visited
  function dfs(row, col) {
    // Mark the current cell as visited by changing '1' to '0'
    grid[row][col] = '0';
    
    // Check all four directions: up, right, down, left
    const directions = [[-1, 0], [0, 1], [1, 0], [0, -1]];
    
    for (const [dr, dc] of directions) {
      const newRow = row + dr;
      const newCol = col + dc;
      
      if (isValid(newRow, newCol)) {
        dfs(newRow, newCol);
      }
    }
  }
  
  // Iterate through each cell in the grid
  for (let i = 0; i < rows; i++) {
    for (let j = 0; j < cols; j++) {
      // If we find a land cell, start DFS and increment count
      if (grid[i][j] === '1') {
        count++;
        dfs(i, j);
      }
    }
  }
  
  return count;
}
 
// Example usage:
const grid = [
  ['1', '1', '0', '0', '0'],
  ['1', '1', '0', '0', '0'],
  ['0', '0', '1', '0', '0'],
  ['0', '0', '0', '1', '1']
];
 
const islands = numIslands(grid);
console.log(islands); // Output: 3