颜色交替的最短路径【LC1129】
在一个有向图中，节点分别标记为 0, 1, ..., n-1。图中每条边为红色或者蓝色，且存在自环或平行边。
red_edges 中的每一个 [i, j] 对表示从节点 i 到节点 j 的红色有向边。类似地，blue_edges 中的每一个 [i, j] 对表示从节点 i 到节点 j 的蓝色有向边。
返回长度为 n 的数组 answer，其中 answer[X] 是从节点 0 到节点 X 的红色边和蓝色边交替出现的最短路径的长度。如果不存在这样的路径，那么 answer[x] = -1。
我补！
BFS
- 思路
。首先将所有的边按颜色分类存储至动态数组中，redList存储所有的红边，blueList存储所有的红边
。然后定义变量
- 使用队列存储当前搜索到的节点，redQueue存储当前边为红色的节点，blueQueue存储当前边为蓝色的节点，那么下一条边与当前边相反
- 使用布尔数组vis记录当前节点的颜色为蓝色或者红色时，是否访问过
- 使用变量step记录当前的距离
- 使用数组res记录起点至每个节点的最短距离，初始化为-1
。搜索过程为，初始时将0放入两个队列中，表示前一条边为蓝色或者红色【虚拟边】。然后进行BFS搜索，每次从队列中取出一个节点，如果当前节点的结果为更新，那么将当前节点的答案更新为step。然后，遍历以当前节点为起点颜色相反的边的终点，如果该节点位访问过，那么放入相应队列，继续搜索
。实现
class Solution { public int[] shortestAlternatingPaths(int n, int[][] redEdges, int[][] blueEdges) { int[] res = new int[n]; Arrays.fill(res, -1); List<Integer>[] redList = new List[n]; List<Integer>[] blueList = new List[n]; for (int i = 0; i < n; i++){ redList[i] = new ArrayList<Integer>(); blueList[i] = new ArrayList<Integer>(); } for (int[] red :redEdges){ int u = red[0], v = red[1]; redList[u].add(v); } for (int[] blue : blueEdges){ int u = blue[0], v = blue[1]; blueList[u].add(v); } Deque<Integer> redQueue = new LinkedList<>(); Deque<Integer> blueQueue = new LinkedList<>(); redQueue.add(0); blueQueue.add(0); int step = 0; boolean[][] vis = new boolean[n][2]; // 0 红色 1 蓝色 while (!redQueue.isEmpty() || !blueQueue.isEmpty()){ int s1 = redQueue.size(), s2 = blueQueue.size(); // 当前边为红边，找蓝边 for (int i = 0; i < s1; i++){ int u = redQueue.pollFirst(); vis[u][0] = true; if (res[u] == -1) res[u] = step; for (int v : blueList[u]){ if (!vis[v][1]){ blueQueue.addLast(v); } } } // 当前边为蓝边，找红边 for (int i = 0; i < s2; i++){ int u = blueQueue.pollFirst(); vis[u][1] = true; if (res[u] == -1) res[u] = step; for (int v : redList[u]){ if (!vis[v][0]){ redQueue.addLast(v); } } } step++; } return res; } }
。复杂度分析
- 时间复杂度：O ( n + m )
- 空间复杂度：O ( n + m )
- 优化：红色用0表示，蓝色用1表示，使用二维数组记录所有信息，入队时标识颜色
class Solution { public int[] shortestAlternatingPaths(int n, int[][] redEdges, int[][] blueEdges) { List<Integer>[][] g = new List[2][n]; for (var f : g) { Arrays.setAll(f, k -> new ArrayList<>()); } for (var e : redEdges) { g[0][e[0]].add(e[1]); } for (var e : blueEdges) { g[1][e[0]].add(e[1]); } Deque<int[]> q = new ArrayDeque<>(); q.offer(new int[] {0, 0}); q.offer(new int[] {0, 1}); boolean[][] vis = new boolean[n][2]; int[] ans = new int[n]; Arrays.fill(ans, -1); int d = 0; while (!q.isEmpty()) { for (int k = q.size(); k > 0; --k) { var p = q.poll(); int i = p[0], c = p[1]; if (ans[i] == -1) { ans[i] = d; } vis[i][c] = true; c ^= 1; for (int j : g[c][i]) { if (!vis[j][c]) { q.offer(new int[] {j, c}); } } } ++d; } return ans; } } 作者：ylb 链接：https://leetcode.cn/problems/shortest-path-with-alternating-colors/solutions/2087881/python3javacgo-yi-ti-yi-jie-bfsqing-xi-t-ag0i/ 来源：力扣（LeetCode） 著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。
