关于我的 Leetcode 题目解答，代码前往 Github：https://github.com/chenxiangcyr/leetcode-answers
判断一个图是否有环
对于无向图
算法1：
我们知道对于环 1-2-3-4-1，每个节点的度都是2，基于此我们有如下算法（这是类似于有向图的拓扑排序）：
- 求出图中所有顶点的度
- 删除图中所有度 <=1 的顶点以及与该顶点相关的边，把与这些边相关的顶点的度减一
- 如果还有度<=1的顶点重复步骤2
- 最后如果还存在未被删除的顶点，则表示有环；否则没有环
时间复杂度为O(E+V)，其中E、V分别为图中边和顶点的数目。
算法2：
深度优先遍历该图，如果在遍历的过程中，发现某个节点有一条边指向已经访问过的节点，并且这个已访问过的节点不是当前节点的父节点（这里的父节点表示dfs遍历顺序中的父节点），则表示存在环。但是我们不能仅仅使用一个bool数组来标志节点是否访问过。
对每个节点分为三种状态，白、灰、黑。
开始时所有节点都是白色，当开始访问某个节点时该节点变为灰色，当该节点的所有邻接点都访问完，该节点颜色变为黑色。
那么我们的算法则为：如果遍历的过程中发现某个节点有一条边指向颜色为灰的节点，那么存在环。
对于有向图
算法3：
对于有向图的拓扑排序，kahn算法：
- 计算图中所有点的入度，把入度为0的点加入栈
- 如果栈非空：
- 取出栈顶顶点a，输出该顶点值，删除该顶点
- 从图中删除所有以a为起始点的边，如果删除的边的另一个顶点入度为0，则把它入栈
- 如果图中还存在顶点，则表示图中存在环；否则输出的顶点就是一个拓扑排序序列
算法4：
其实算法2可以原封不动的搬来就可以检测并且输出所有有向图中的环
LeeCode题目
LeetCode题目：684. Redundant Connection
In this problem, a tree is an undirected 无向图 graph that is connected and has no cycles.
The given input is a graph that started as a tree with N nodes (with distinct values 1, 2, ..., N), with one additional edge added. The added edge has two different vertices chosen from 1 to N, and was not an edge that already existed.
The resulting graph is given as a 2D-array of edges. Each element of edges is a pair [u, v] with u < v, that represents an undirected edge connecting nodes u and v.
Return an edge that can be removed so that the resulting graph is a tree of N nodes. If there are multiple answers, return the answer that occurs last in the given 2D-array. The answer edge [u, v] should be in the same format, with u < v.
Example 1:
Input: [[1,2], [1,3], [2,3]]
Output: [2,3]
Explanation: The given undirected graph will be like this:
Example 2:
Input: [[1,2], [2,3], [3,4], [1,4], [1,5]]
Output: [1,4]
Explanation: The given undirected graph will be like this:
Note:
- The size of the input 2D-array will be between 3 and 1000.
- Every integer represented in the 2D-array will be between 1 and N, where N is the size of the input array.
class Solution {
public int[] findRedundantConnection(int[][] edges) {
// 使用邻接表存储图的信息
Map<Integer, List<Integer>> graph = new HashMap<>();
// 遍历每一条边
for(int[] edge : edges) {
// Each element of edges is a pair [u, v] with u < v
int u = edge[0];
int v = edge[1];
// 深度优先遍历该图，判断u到v之间是否已经存在了一条路径
boolean hasPath = dfs(graph, u, v, new ArrayList<Integer>());
if(hasPath == true) {
return edge;
}
else {
// 将该边加入到邻接表中
if(!graph.containsKey(u)) {
graph.put(u, new ArrayList<Integer>());
}
graph.get(u).add(v);
if(!graph.containsKey(v)) {
graph.put(v, new ArrayList<Integer>());
}
graph.get(v).add(u);
}
}
return null;
}
// 深度优先遍历该图，判断start到end之间是否已经存在了一条路径
public boolean dfs(Map<Integer, List<Integer>> graph, int start, int end, List<Integer> visited) {
if(!graph.containsKey(start) || !graph.containsKey(end)) {
return false;
}
if(start == end) {
return true;
}
visited.add(start);
// 遍历start的所有相邻节点
for(int adj : graph.get(start)) {
if(!visited.contains(adj)) {
if(dfs(graph, adj, end, visited) == true) {
return true;
}
}
}
return false;
}
}
Note：上述算法的时间复杂度是O(n^2)，如果想实现O(n)复杂度，参见 Disjoint Set Union (DSU) 并查集及其应用。
引用：
判断一个图是否有环
