无向图 Undirected Graph
133. Clone Graph
第一种方法是两步走，用BFS，第一步先copy所有的点，新老映射关系存在一个map里面，第二步是copy所有边，每次拿点出来就直接从map里面拿就行，因为我们copy的新点都是新建过的，不需要再建了，再建肯定不对了。
注意这是无向图，需要一个set来判断是否访问过，不然就死循环了。
参考了下论坛讨论之后，不太同意大多数解法，因为假设所有点的 label 唯一不是很适合 generalize 这个算法。用 HashMap<> 实现 Node - Node mapping 比较靠谱。
public class Solution {
public UndirectedGraphNode cloneGraph(UndirectedGraphNode node) {
if (node == null) return null;
List<UndirectedGraphNode> graph = getNodes(node);
Map<UndirectedGraphNode, UndirectedGraphNode> map = new HashMap<>();
for (UndirectedGraphNode n : graph) {
map.put(n, new UndirectedGraphNode(n.label));
}
for (UndirectedGraphNode n : graph) {
UndirectedGraphNode newNode = map.get(n);
for (UndirectedGraphNode neighbor : n.neighbors) {
UndirectedGraphNode newNeighbor = map.get(neighbor);
newNode.neighbors.add(newNeighbor);
}
}
return map.get(node);
}
private List<UndirectedGraphNode> getNodes(UndirectedGraphNode node) {
Queue<UndirectedGraphNode> queue = new LinkedList<>();
Set<UndirectedGraphNode> set = new HashSet<>();
queue.offer(node);
set.add(node);
while (!queue.isEmpty()) {
UndirectedGraphNode head = queue.poll();
for (UndirectedGraphNode neighbor : head.neighbors) {
if (!set.contains(neighbor)) {
queue.offer(neighbor);
set.add(neighbor);
}
}
}
return new ArrayList<UndirectedGraphNode>(set);
}
}
7/17更新：重新写这个的代码和之前完全不同，不理解我以前为啥非要用set，一个map多简单就做完了。
啊我想起来了，是因为九章算法的答案是上面这么写的，解法有点蠢。
public class Solution {
public UndirectedGraphNode cloneGraph(UndirectedGraphNode node) {
if (node == null) return null;
Map<UndirectedGraphNode, UndirectedGraphNode> map = new HashMap<>();
Queue<UndirectedGraphNode> queue = new LinkedList<>();
queue.offer(node);
while (!queue.isEmpty()) {
UndirectedGraphNode tmp = queue.poll();
if (!map.containsKey(tmp)) {
UndirectedGraphNode newNode = new UndirectedGraphNode(tmp.label);
map.put(tmp, newNode);
for (UndirectedGraphNode curt : tmp.neighbors) {
queue.offer(curt);
}
}
}
for (Map.Entry<UndirectedGraphNode, UndirectedGraphNode> entry : map.entrySet()) {
UndirectedGraphNode old = entry.getKey();
UndirectedGraphNode nee = entry.getValue();
List<UndirectedGraphNode> list = old.neighbors;
for (UndirectedGraphNode tmp : list) {
nee.neighbors.add(map.get(tmp));
}
}
return map.get(node);
}
}
310. Minimum Height Trees
dietpepsi 添加的题目。
在这个 graph 里，我们要找的，其实也是一层一层剥开最外围 nodes 之后，最里面的点。
因此，即使是 undirected graph，degree 也是非常重要的信息，只不过对于 undirected graph 来讲:
degree = "in"-degree + "out"-degree 而已，当然这个也是我们自己定义的，想怎么定义都是可以的，就看最后是否能通过BFS做出来就行。
这个题和 course schedule 的BFS解法相差无几，只不过我们层层剥开之后，每一层都可能是最后要返回的答案，所以每一层都要新建list保存下来，下一层再覆盖。
public class Solution {
public List<Integer> findMinHeightTrees(int n, int[][] edges) {
List<Integer> result = new ArrayList<>();
if (edges == null || edges.length == 0) {
result.add(0);
return result;
}
int[] degree = new int[n];
Map<Integer, List<Integer>> map = new HashMap<>();
for (int[] num : edges) {
int node1 = num[0];
int node2 = num[1];
addNode(map, node1, node2);
addNode(map, node2, node1);
degree[node1]++;
degree[node2]++;
}
Queue<Integer> queue = new LinkedList<>();
for (int i = 0; i < n; ++i) {
if (degree[i] <= 1) queue.offer(i);
}
while (!queue.isEmpty()) {
int size = queue.size();
result = new ArrayList<>();
for (int i = 0; i < size; ++i) {
int cur = queue.poll();
result.add(cur);
for (int j = 0; j < map.get(cur).size(); ++j) {
int next = map.get(cur).get(j);
degree[next]--;
if (degree[next] == 1) queue.offer(next);
}
}
}
return result;
}
private void addNode(Map<Integer, List<Integer>> map, int node1, int node2) {
if (map.containsKey(node1)) {
List<Integer> list = map.get(node1);
list.add(node2);
map.put(node1, list);
} else {
List<Integer> list = new ArrayList<>();
list.add(node2);
map.put(node1, list);
}
}
}
261. Graph Valid Tree
这道题也不难，和 course schedule 的区别只在有向和无向之间。
对于有向图，我们不能随便挑一个起始点，必须从头开始，不然前面就遍历不到了，同样是找环的操作，无向图就可以从任意点开始。
public class Solution {
public boolean validTree(int n, int[][] edges) {
int[] state = new int[n];
Map<Integer, List<Integer>> map = new HashMap<>();
for (int[] num : edges){
int node1 = num[0];
int node2 = num[1];
addNode(map, node1, node2);
addNode(map, node2, node1);
}
Queue<Integer> queue = new LinkedList<>();
queue.offer(0);
state[0] = 1;
int count = 0;
while (!queue.isEmpty()) {
int cur = queue.poll();
count++;
if (map.containsKey(cur)) {
for (int i = 0; i < map.get(cur).size(); ++i) {
int next = map.get(cur).get(i);
if (state[next] == 1) return false;
if (state[next] == 0) {
state[next] = 1;
queue.offer(next);
}
}
}
state[cur] = 2;
}
return count == n;
}
private void addNode(Map<Integer, List<Integer>> map, int node1, int node2) {
if (map.containsKey(node1)) {
List<Integer> list = map.get(node1);
list.add(node2);
map.put(node1, list);
} else {
List<Integer> list = new ArrayList<>();
list.add(node2);
map.put(node1, list);
}
}
}
07/18更新：试图用今天的方法做，但是不行，无向图不能用这种方法做，这种方法只适合有向图，因为有向图没有环的时候，无向图是认为有环的。
public class Solution {
public boolean validTree(int n, int[][] edges) {
int[] degree = new int[n];
Set<Integer> set = new HashSet<>();
for (int i = 0; i < edges.length; ++i) {
degree[edges[i][0]]++;
}
Queue<Integer> queue = new LinkedList<>();
for (int i = 0; i < degree.length; ++i) {
if (degree[i] == 0) {
queue.offer(i);
set.add(i);
}
}
while (!queue.isEmpty()) {
int node = queue.poll();
for (int i = 0; i < edges.length; ++i) {
if (edges[i][1] == node && !set.contains(edges[i][0])) {
degree[edges[i][0]]--;
if (degree[edges[i][0]] == 0) {
queue.offer(edges[i][0]);
set.add(edges[i][0]);
}
}
}
}
for (int i = 0; i < degree.length; ++i) {
if (degree[i] != 0) return false;
}
return true;
}
}