6. Graph
这里收录的是真正的关于Graph data structure或者Graph Theory的题目.隐式图是一种算法/思想，不是真正关于Graph的，所以就收录在其它章节了BFS/DFS
Graph Valid Tree
这道题很好的考察了对Tree和Graph的区别的理解
还是BFS的思路更intuitive, 面试更好解释
Tree vs. Graph
树和图的区别在于是否有环
tree是parent-child relationship
Graph 是 neighbor-neighbor relation
如何判断是否是Graph: 图中存在环，同一个节点可能重复进入队列
class Solution {
/*
1.valid tree, N nodes can only have N - 1 edges
2.BFS to traversal all neighbors from a random node, check whether all nodes can be visited
3.need to build graph, Map<Integer, Set<Integer>> graph, key is node, value is set of neighbors
*/
public boolean validTree(int n, int[][] edges) {
if (edges == null || edges.length != n - 1) return false;
if (n == 1) return true;
Map<Integer, Set<Integer>> graph = buildGraph(edges);//key is node, value is set of neighbors
Set<Integer> visited = new HashSet<>();
Queue<Integer> queue = new LinkedList<>();
queue.offer(edges[0][0]);
while (!queue.isEmpty()) {
int node = queue.poll();
if (!visited.add(node)) continue;
for (int neighbor : graph.get(node)) {
queue.offer(neighbor);
}
}
return visited.size() == n;
}
private Map<Integer, Set<Integer>> buildGraph(int[][] edges) {
Map<Integer, Set<Integer>> graph = new HashMap<>();
for (int[] edge : edges) {
Set<Integer> neighbors = graph.getOrDefault(edge[0], new HashSet<>());
neighbors.add(edge[1]);
graph.put(edge[0], neighbors);
neighbors = graph.getOrDefault(edge[1], new HashSet<>());
neighbors.add(edge[0]);
graph.put(edge[1], neighbors);
}
return graph;
}
}Course Schedule
给定一堆课程和 prerequisisites, 判断是否能完成所有课程
判断DAG是否有环的经典题型
topo sort模板题
class Solution {
public boolean canFinish(int numCourses, int[][] prerequisites) {
Map<Integer, List<Integer>> courseToNeighbors = new HashMap<>();
Map<Integer, Integer> indegrees = new HashMap<>();
for (int i = 0; i < numCourses; i++) {
indegrees.put(i, 0);
courseToNeighbors.put(i, new ArrayList<>());
}
for (int[] pre : prerequisites) {
// build graph with neighbors
courseToNeighbors.get(pre[1]).add(pre[0]);
//get indegrees of each node
indegrees.put(pre[0], indegrees.get(pre[0]) + 1);
}
Queue<Integer> queue = new LinkedList<>();
int start = 0;
Set<Integer> visited = new HashSet<>();
while (start < numCourses) {
if (indegrees.get(start) == 0) {
queue.offer(start);
visited.add(start);
}
start++;
}
while (!queue.isEmpty()) {
int cur = queue.poll();
List<Integer> neighbors = courseToNeighbors.get(cur);
for (int neighbor : neighbors) {
indegrees.put(neighbor, indegrees.get(neighbor) - 1);
if (indegrees.get(neighbor) == 0 && !visited.contains(neighbor)) {
queue.offer(neighbor);
visited.add(neighbor);
}
}
}
return visited.size() == numCourses;
}
}这题除了用Set来记录visited node之外，还可以用list来记录visited node
这样如果需要返回任意一条路径的话就很方便
public boolean canFinish(int numCourses, int[][] prerequisites) {
Map<Integer, Integer> courseToIndegree = new HashMap<>();
Map<Integer, Set<Integer>> courseToNeighbors = new HashMap<>();
for (int i = 0; i < numCourses; i++) {
courseToIndegree.put(i, 0);
courseToNeighbors.put(i, new HashSet<Integer>());
}
for (int[] prerequisite : prerequisites) {
//get indegrees of each node
courseToIndegree.put(prerequisite[0], courseToIndegree.get(prerequisite[0]) + 1);
// build graph with neighbors
courseToNeighbors.get(prerequisite[1]).add(prerequisite[0]);
}
Queue<Integer> queue = new LinkedList<>();
for (Integer course: courseToIndegree.keySet()) {
if (courseToIndegree.get(course) == 0) {
queue.offer(course);
}
}
List<Integer> order = new ArrayList<>();
while (!queue.isEmpty()) {
Integer cur = queue.poll();
order.add(cur);
for (Integer neighbor : courseToNeighbors.get(cur)) {
courseToIndegree.put(neighbor, courseToIndegree.get(neighbor) - 1);
if (courseToIndegree.get(neighbor) == 0) {
queue.offer(neighbor);
}
}
}
return order.size() == numCourses;
}Course Schedule II
course schedule 的follow up, 要求返回任意一条路径的结果
用一个list来记录visited node
class Solution {
public int[] findOrder(int numCourses, int[][] prerequisites) {
Map<Integer, Integer> courseToIndegree = new HashMap<>();
Map<Integer, Set<Integer>> courseToNeighbors = new HashMap<>();
for (int i = 0; i < numCourses; i++) {
courseToIndegree.put(i, 0);
courseToNeighbors.put(i, new HashSet<Integer>());
}
for (int[] prerequisite : prerequisites) {
//get indegrees of each node
courseToIndegree.put(prerequisite[0], courseToIndegree.get(prerequisite[0]) + 1);
// build graph with neighbors
courseToNeighbors.get(prerequisite[1]).add(prerequisite[0]);
}
Queue<Integer> queue = new LinkedList<>();
for (Integer course: courseToIndegree.keySet()) {
if (courseToIndegree.get(course) == 0) {
queue.offer(course);
}
}
List<Integer> order = new ArrayList<>();
while (!queue.isEmpty()) {
Integer cur = queue.poll();
order.add(cur);
for (Integer neighbor : courseToNeighbors.get(cur)) {
courseToIndegree.put(neighbor, courseToIndegree.get(neighbor) - 1);
if (courseToIndegree.get(neighbor) == 0) {
queue.offer(neighbor);
}
}
}
int[] arr = {};
if (order.size() == numCourses) {
arr = convert(order);
}
return arr;
}
private int[] convert(List<Integer> list) {
int[] arr = new int[list.size()];
for (int i = 0; i < list.size(); i++) {
arr[i] = list.get(i);
}
return arr;
}
}Is Graph Bipartite?
graph coloring
BFS
public boolean isBipartite(int[][] graph) {
int[] groups = new int[graph.length];//groups[i] can be 0,1,2, 0 means not visited
for (int i = 0; i < graph.length; i++) {
//BFS to calculate which group node i should be
if (groups[i] != 0) continue;
Queue<Integer> queue = new LinkedList<>();
queue.offer(i);
groups[i] = 1;
while (!queue.isEmpty()) {
int cur = queue.poll();
int[] neighbors = graph[cur];
for (int neighbor : neighbors) {
if (groups[neighbor] == 0) {
queue.offer(neighbor);
groups[neighbor] = groups[cur] == 1 ? 2 : 1;
} else if (groups[neighbor] == groups[cur]) {
return false;
}
}
}
}
return true;
}Best Meeting point
Mahattan distance
Last updated
Was this helpful?