package Graph;import java.util.ArrayDeque;import java.util.ArrayList;import java.util.Collections;import java.util.HashMap;import java.util.HashSet;import java.util.LinkedList;import java.util.List;import java.util.Map;import java.util.PriorityQueue;import java.util.Queue;import java.util.Set;public class GraphProblem { public static void main(String[] args) { // TODO Auto-generated method stub } /* * 207. Course Schedule * 2016-3-28 by jyuan * BFS:典型的拓扑排序。原理也很简单，在一个有向图中，每次找到一个没有前驱节点的节点（也就是入度为0的节点）， * 然后把它指向其他节点的边都去掉，重复这个过程（BFS），直到所有节点已被找到，或者没有符合条件的节点（如果图中有环存在）。。 * DFS的解法，也需要建立有向图，还是用二维数组来建立，和BFS不同的是，我们像现在需要一个一维数组visit来记录访问状态， * 大体思路是，先建立好有向图，然后从第一个门课开始，找其可构成哪门课，暂时将当前课程标记为已访问， * 然后对新得到的课程调用DFS递归，直到出现新的课程已经访问过了，则返回false，没有冲突的话返回true，然后把标记为已访问的课程改为未访问 * http://www.jyuan92.com/blog/leetcode-course-schedule/ */ public boolean canFinishWithBFS(int numCourses, int[][] prerequisites) { if (null == prerequisites || numCourses == 0 || prerequisites.length == 0) { return true; } int[] preCourses = new int[numCourses]; // store the in-degree # for (int[] prerequisite : prerequisites) { preCourses[prerequisite[0]]++; } Queue queue = new LinkedList (); for (int i = 0; i < preCourses.length; i++) { if (preCourses[i] == 0) { queue.add(i); } } int numOfPreCourse = 0; while (!queue.isEmpty()) { int top = queue.poll(); numOfPreCourse++; for (int[] prerequisite : prerequisites) { if (prerequisite[1] == top) { //Find all the neighbor preCourses[prerequisite[0]]--; if (preCourses[prerequisite[0]] == 0) { queue.add(prerequisite[0]); } } } } return numOfPreCourse == numCourses; } /* * 210 Course ScheduleII * 2016-3-28 by jyuan * http://www.jyuan92.com/blog/leetcode-course-schedule-ii/ */ public int[] findOrder(int numCourses, int[][] prerequisites) { int[] res = new int[numCourses];//区别1，多了一个装order的array int[] preCourses = new int[numCourses]; // store the in-degree # for (int[] prerequisite : prerequisites) { preCourses[prerequisite[0]]++; } Queue queue = new LinkedList (); for (int i = 0; i < preCourses.length; i++) { if (preCourses[i] == 0) { queue.add(i); } } int numOfPreCourse = 0; int i = 0;//区别2，多了一个i来遍历res while (!queue.isEmpty()) { int top = queue.poll(); res[i++] = top; numOfPreCourse++; for (int[] prerequisite : prerequisites) { if (prerequisite[1] == top) { preCourses[prerequisite[0]]--; if (preCourses[prerequisite[0]] == 0) { queue.add(prerequisite[0]); } } } }//最后再多一个判断，就是返回是否是需要return新的 if (numOfPreCourse == numCourses) { return res; } else { return new int[0]; } } /* * 下面给出207的DFS方法： * DFS的思路就简单一点，就是首先构造图的Map，每一个点包含一个list，表明这个点作为这个list * 每一门课程的前备课程以待后用。那么主体思路就是每一个点为起点做一次dfs，知道底端， * 如果没有问题就continue，如果有问题直接return false。 * 那么在主体部分，几个状态，如果为-1表示已经访问过肯定return false，如果为1表示这条路 * 已经是通路，已经验证完毕，所有连接这个点的直接return true。 */ public boolean canFinishWithDFS(int numCourses, int[][] prerequisites) { if (null == prerequisites || numCourses == 0 || prerequisites.length == 0) { return true; } int[] isVisited = new int[numCourses]; Map > map = new HashMap >(); for (int[] prerequisite : prerequisites) { if (!map.containsKey(prerequisite[1])) { map.put(prerequisite[1], new ArrayList ()); } map.get(prerequisite[1]).add(prerequisite[0]); } for (int i = 0; i < numCourses; i++) { if (!dfs(isVisited, map, i)) { return false; } } return true; } private boolean dfs(int[] isVisited, Map > map, int index) { if (isVisited[index] == -1) { return false; } if (isVisited[index] == 1) { return true; } isVisited[index] = -1;//假如最后一个点进来，先赋值-1，然后没有map的值，所以直接为1，以后所有遇到这个点的都是通路 if (map.containsKey(index)) { for (int value : map.get(index)) { if (!dfs(isVisited, map, value)) { return false; } } } isVisited[index] = 1; return true; } /* * 下面给出210的DFS方法： */ int i;//区别1全局变量i public int[] findOrderWithDFS(int numCourses, int[][] prerequisites) { i = numCourses - 1; int[] res = new int[numCourses]; int[] isVisited = new int[numCourses]; Map > map = new HashMap >(); for (int[] prerequisite : prerequisites) { if (!map.containsKey(prerequisite[1])) { map.put(prerequisite[1], new ArrayList ()); } map.get(prerequisite[1]).add(prerequisite[0]); } for (int i = 0; i < numCourses; i++) { if (!dfs(map, isVisited, res, i)) { return new int[0]; } } return res; } private boolean dfs(Map > map, int[] isVisited, int[] res, int index) { if (isVisited[index] == -1) { return false; } if (isVisited[index] == 1) { return true; } isVisited[index] = -1; if (map.containsKey(index)) { for (int value : map.get(index)) { if (!dfs(map, isVisited, res, value)) { return false; } } } res[i--] = index; isVisited[index] = 1; return true; } /* * 261.Graph Valid Tree * 2016-3-29 by Buttercola * 和上面的BFS方法一样，不过这里是无向图，所以需要两个点都要存对方 * 图要形成树必须有两个方面，一个是没有cycle另一个是没有孤立的点 * Given n nodes labeled from 0 to n - 1 and a list of undirected edges (each edge is a pair of nodes), * write a function to check whether these edges make up a valid tree. * Given n = 5 and edges = [[0, 1], [0, 2], [0, 3], [1, 4]], return true. * Given n = 5 and edges = [[0, 1], [1, 2], [2, 3], [1, 3], [1, 4]], return false. */ private boolean valid(int n, int[][] edges) { // build the graph using adjacent list List > graph = new ArrayList >(); for(int i = 0; i < n; i++) graph.add(new HashSet ()); for(int[] edge : edges) { graph.get(edge[0]).add(edge[1]); graph.get(edge[1]).add(edge[0]); } // no cycle boolean[] visited = new boolean[n]; Queue queue = new LinkedList (); queue.add(0); while(!queue.isEmpty()) { int node = queue.poll(); if(visited[node]) return false; visited[node] = true; for(int neighbor : graph.get(node)) { queue.offer(neighbor); graph.get(neighbor).remove((Integer)node); } } // fully connected for(boolean result : visited){ if(!result) return false; } return true; } /* * 310. Minimum Height Trees * 2016-3-29 by Mingyang * 同样的方法构建无向图 * 这里运用的一个层层剥丝的方式，一层一层的来，去掉不要的 */ public List findMinHeightTrees(int n, int[][] edges) { if (n == 1) return Collections.singletonList(0); List > adj = new ArrayList >(n); for (int i = 0; i < n; ++i) adj.add(new HashSet ()); for (int[] edge : edges) { adj.get(edge[0]).add(edge[1]); adj.get(edge[1]).add(edge[0]); } List leaves = new ArrayList (); for (int i = 0; i < n; ++i) if (adj.get(i).size() == 1) leaves.add(i); while (n > 2) { n -= leaves.size(); List newLeaves = new ArrayList (); for (int i : leaves) { int j = adj.get(i).iterator().next(); adj.get(j).remove(i); if (adj.get(j).size() == 1) newLeaves.add(j); } leaves = newLeaves; } return leaves; } /* * 332. Reconstruct Itinerary * 2016-3-14 by Mingyang * 这道题给我们一堆飞机票，让我们建立一个行程单，如果有多种方法，取其中字母顺序小的那种方法。 * 这道题的本质是有向图的遍历问题，那么LeetCode关于有向图的题只有两道Course Schedule和Course Schedule II， * 而那两道是关于有向图的顶点的遍历的，而本题是关于有向图的边的遍历。 * 每张机票都是有向图的一条边，我们需要找出一条经过所有边的路径，那么DFS不是我们的不二选择。 * 代码前半段都在准备工作。把所有的tickets全部装进一个map，string对应了一个priority queue * 后半段dfs中，找出第一个顺序的结果。最终输出是从最后一个开始，一个一个往前退的情况下addFirst加起来的 */ HashMap > map = new HashMap >(); LinkedList result = new LinkedList (); public List findItinerary(String[][] tickets) { for (String[] ticket : tickets) { if (!map.containsKey(ticket[0])) { PriorityQueue q = new PriorityQueue (); map.put(ticket[0], q); } map.get(ticket[0]).offer(ticket[1]); } dfs("JFK"); return result; } public void dfs(String s) { PriorityQueue q = map.get(s); while (q != null && !q.isEmpty()) { dfs(q.poll()); } result.addFirst(s); } /* * 323 Number of Connected Components in an Undirected Graph * 2016-4-2 by Mingyang * Given n nodes labeled from 0 to n - 1 and * a list of undirected edges (each edge is a pair of nodes), * write a function to find the number of connected components in an undirected graph. * You can assume that no duplicate edges will appear in edges. * Since all edges are undirected, [0, 1] is the same as [1, 0] and thus will not appear together in edges. */ public int countComponents(int n, int[][] edges) { if (n <= 1) { return n; } List > adjList = new ArrayList >(); for (int i = 0; i < n; i++) { adjList.add(new ArrayList ()); } for (int[] edge : edges) { adjList.get(edge[0]).add(edge[1]); adjList.get(edge[1]).add(edge[0]); } boolean[] visited = new boolean[n]; int count = 0; for (int i = 0; i < n; i++) { if (!visited[i]) { count++; dfs(visited, i, adjList); } } return count; } public void dfs(boolean[] visited, int index, List > adjList) { visited[index] = true; for (int i : adjList.get(index)) { if (!visited[i]) { dfs(visited, i, adjList); } } }}