算法面试——图：克隆图、课程表、岛屿数量

图的题目通常考察 DFS/BFS 两种遍历方式。一、克隆图publicNodecloneGraph(Nodenode){if(nodenull)returnnull;MapNode,NodevisitednewHashMap();returndfs(node,visited);}privateNodedfs(Nodenode,MapNode,Nodevisited){if(visited.containsKey(node))returnvisited.get(node);NodeclonenewNode(node.val);visited.put(node,clone);for(Nodeneighbor:node.neighbors)clone.neighbors.add(dfs(neighbor,visited));returnclone;}二、课程表拓扑排序publicbooleancanFinish(intn,int[][]prerequisites){ListInteger[]adjnewList[n];int[]inDegreenewint[n];for(inti0;in;i)adj[i]newArrayList();for(int[]p:prerequisites){adj[p[1]].add(p[0]);inDegree[p[0]];}QueueIntegerqnewLinkedList();for(inti0;in;i)if(inDegree[i]0)q.offer(i);intcount0;while(!q.isEmpty()){intuq.poll();count;for(intv:adj[u])if(--inDegree[v]0)q.offer(v);}returncountn;}三、岛屿数量publicintnumIslands(char[][]grid){intcount0;for(inti0;igrid.length;i)for(intj0;jgrid[0].length;j)if(grid[i][j]1){dfs(grid,i,j);count;}returncount;}privatevoiddfs(char[][]g,intr,intc){if(r0||c0||rg.length||cg[0].length||g[r][c]!1)return;g[r][c]0;dfs(g,r-1,c);dfs(g,r1,c);dfs(g,r,c-1);dfs(g,r,c1);} 觉得有用的话点赞 关注【张老师技术栈】吧每周更新 Java/Python 实战干货不让你白来。