访问所有节点的最短路径

/*
 * Problem Statement:
 * Given an undirected connected graph with n nodes labeled from 0 to n - 1, 
 * represented as an array graph where graph[i] is a list of all nodes connected to node i.
 * Return the length of the shortest path that visits every node. You may start and stop at any node.
 *
 * Approach:
 * 1. Use Java Stream API along with BFS to explore all possible paths.
 * 2. Maintain a queue to store the current node, visited nodes, and distance.
 * 3. Use a bitmask to keep track of visited nodes.
 * 4. Continue BFS until all nodes have been visited.
 */
import java.util.*;
import java.util.stream.IntStream;

public class ShortestPathStream {
    public int shortestPathLength(int[][] graph) {
        int n = graph.length;
        int target = (1 << n) - 1; // bitmask representing all nodes visited
        Queue<int[]> queue = new LinkedList<>();
        boolean[][] visited = new boolean[n][target + 1];
        // Initialize the queue with all nodes
        IntStream.range(0, n).forEach(i -> {
            queue.offer(new int[]{i, 1 << i, 0});
            visited[i][1 << i] = true;
        });
        // BFS
        while (!queue.isEmpty()) {
            int[] current = queue.poll();
            int node = current[0];
            int mask = current[1];
            int dist = current[2];
            // If all nodes are visited, return the distance
            if (mask == target) return dist;
            // Explore all neighbors
            Arrays.stream(graph[node]).forEach(neighbor -> {
                int nextMask = mask | (1 << neighbor);
                if (!visited[neighbor][nextMask]) {
                    queue.offer(new int[]{neighbor, nextMask, dist + 1});
                    visited[neighbor][nextMask] = true;
                }
            });
        }
        return -1; // should never reach here
    }
}