![[leetcode] 题型整理之图论](https://image.shishitao.com:8440/aHR0cHM6Ly9ia3FzaW1nLmlrYWZhbi5jb20vdXBsb2FkL2NoYXRncHQtcy5wbmc%2FIQ%3D%3D.png?!?w=700&webp=1 "[leetcode] 题型整理之图论")
图论的常见题目有两类，一类是求两点间最短距离，另一类是拓扑排序，两种写起来都很烦。
求最短路径：
127. Word Ladder
Given two words (beginWord and endWord), and a dictionary's word list, find the length of shortest transformation sequence from beginWord to endWord, such that:
- Only one letter can be changed at a time
- Each intermediate word must exist in the word list
For example,
Given:
beginWord = "hit"
endWord = "cog"
wordList = ["hot","dot","dog","lot","log"]
As one shortest transformation is "hit" -> "hot" -> "dot" -> "dog" -> "cog",
return its length 5.
Note:
- Return 0 if there is no such transformation sequence.
- All words have the same length.
All words contain only lowercase alphabetic characters.
从起点开始向外更新，因为每条路径的权值都不是负数，所以先更新的总比后更新的小。
已经被更新过的之后就不用考虑了
133. Clone Graph
Clone an undirected graph. Each node in the graph contains a label and a list of its neighbors.
Nodes are labeled uniquely.
We use # as a separator for each node, and , as a separator for node label and each neighbor of the node.
As an example, consider the serialized graph {0,1,2#1,2#2,2}.
The graph has a total of three nodes, and therefore contains three parts as separated by #.
- First node is labeled as
0. Connect node0to both nodes1and2. - Second node is labeled as
1. Connect node1to node2. - Third node is labeled as
2. Connect node2to node2(itself), thus forming a self-cycle.
Visually, the graph looks like the following:
1
/ \
/ \
0 --- 2
/ \
\_/
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.
For example:
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.
Hint:
- Given
n = 5andedges = [[0, 1], [1, 2], [3, 4]], what should your return? Is this case a valid tree? - According to the definition of tree on Wikipedia: “a tree is an undirected graph in which any two vertices are connected by exactly one path. In other words, any connected graph without simple cycles is a tree.”
Note: 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 class Solution {
public boolean validTree(int n, int[][] edges) {
List<HashSet<Integer>> sets = new ArrayList<HashSet<Integer>>();
for (int i = 0; i < n; i++) {
sets.add(new HashSet<Integer>());
}
boolean[] isVisited = new boolean[n];
Arrays.fill(isVisited, false);
for (int[] edge : edges) {
int v1 = edge[0];
int v2 = edge[1];
sets.get(v1).add(v2);
sets.get(v2).add(v1);
}
boolean result = dfs(sets, isVisited, 0, -1);
if (!result) {
return false;
}
for (int i = 0; i < n; i++) {
if (!isVisited[i]) {
return false;
}
}
return true;
}
private boolean dfs(List<HashSet<Integer>> sets, boolean[] isVisited, int now, int prev) {
boolean isV = isVisited[now];
if (isV) {
return false;
}
isVisited[now] = true;
for (Integer x : sets.get(now)) {
if (x != prev && !dfs(sets, isVisited, x, now)) {
return false;
}
}
return true;
}
}
310. Minimum Height Trees
For a undirected graph with tree characteristics, we can choose any node as the root. The result graph is then a rooted tree. Among all possible rooted trees, those with minimum height are called minimum height trees (MHTs). Given such a graph, write a function to find all the MHTs and return a list of their root labels.
Format
The graph contains n nodes which are labeled from 0 to n - 1. You will be given the number n and a list of undirected edges (each edge is a pair of labels).
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.
Example 1:
Given n = 4, edges = [[1, 0], [1, 2], [1, 3]]
0
|
1
/ \
2 3
return [1]
Example 2:
Given n = 6, edges = [[0, 3], [1, 3], [2, 3], [4, 3], [5, 4]]
0 1 2
\ | /
3
|
4
|
5
return [3, 4]
Hint:
- How many MHTs can a graph have at most?
Note:
(1) According to the definition of tree on Wikipedia: “a tree is an undirected graph in which any two vertices are connected by exactly one path. In other words, any connected graph without simple cycles is a tree.”
(2) The height of a rooted tree is the number of edges on the longest downward path between the root and a leaf.
Credits:
Special thanks to @dietpepsi for adding this problem and creating all test cases.
public class Solution {
public List<Integer> findMinHeightTrees(int n, int[][] edges) {
List<List<Integer>> graph = new ArrayList<List<Integer>>(n);
if (n < 3 || edges.length == 0) {
List<Integer> result = new ArrayList<Integer>();
if (n == 0) {
return result;
} else {
for (int i = 0; i < n; i++) {
result.add(i);
}
return result;
}
}
for (int i = 0; i < n; i++) {
List<Integer> list = new LinkedList<Integer>();
graph.add(list);
}
for (int[] edge : edges) {
int v1 = edge[0];
int v2 = edge[1];
graph.get(v1).add(v2);
graph.get(v2).add(v1);
}
int count = n;
List<Integer> toRemove = new ArrayList<Integer>();
for (int i = 0; i < n; i++) {
List<Integer> list = graph.get(i);
if (list.size() == 1) {
toRemove.add(i);
}
}
while (!toRemove.isEmpty() && count > 1) {
List<Integer> tmpRemove = new ArrayList<Integer>();
for (Integer leave : toRemove) {
List<Integer> list0 = graph.get(leave);
int parent = list0.get(0);
list0.clear();
List<Integer> list = graph.get(parent);
list.remove(leave);
if (list.size() == 1) {
tmpRemove.add(parent);
}
}
count -= toRemove.size();
toRemove = tmpRemove;
if (count <= 2) {
break;
}
}
List<Integer> result = new ArrayList<Integer>();
result.addAll(toRemove);
return result;
}
}