Leetcode: Graph Valid Tree && Summary: Detect cycle in directed graph and undirected graph

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.

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.

This problem can be solved by using union find, reference this blog:https://segmentfault.com/a/1190000003791051

复杂度

时间 O(N^M) 空间 O(1)

思路

判断输入的边是否能构成一个树,我们需要确定两件事:

  1. 这些边是否构成环路,如果有环则不能构成树
  2. 这些边是否能将所有节点连通,如果有不能连通的节点则不能构成树

因为不需要知道具体的树长什么样子,只要知道连通的关系,所以Union Find(并查集)相比深度优先搜索是更好的方法。我们定义一个并查集的数据结构,并提供标准的四个接口:

  • union 将两个节点放入一个集合中
  • find 找到该节点所属的集合编号
  • areConnected 判断两个节点是否是一个集合
  • count 返回该并查集中有多少个独立的集合

具体并查集的原理,参见这篇文章。简单来讲,就是先构建一个数组,节点0到节点n-1,刚开始都各自独立的属于自己的集合。这时集合的编号是节点号。然后,每次union操作时,我们把整个并查集中,所有和第一个节点所属集合号相同的节点的集合号,都改成第二个节点的集合号。这样就将一个集合的节点归属到同一个集合号下了。我们遍历一遍输入,把所有边加入我们的并查集中,加的同时判断是否有环路。最后如果并查集中只有一个集合,则说明可以构建树。

注意

因为要判断是否会产生环路,union方法要返回一个boolean,如果两个节点本来就在一个集合中,就返回假,说明有环路

 1 public class Solution {
 2     public boolean validTree(int n, int[][] edges) {
 3         unionfind uf = new unionfind(n);
 4         for (int i=0; i<edges.length; i++) {
 5             if (uf.areConnected(edges[i][0], edges[i][1])) return false;
 6             else {
 7                 uf.union(edges[i][0], edges[i][1]);
 8             }
 9         }
10         return uf.count()==1;
11     }
12
13     public class unionfind {
14         int[] ids;  //union id for each node
15         int cnt; //the number of independent union
16
17         public unionfind(int size) {
18             this.ids = new int[size];
19             for (int i=0; i<size; i++) {
20                 ids[i] = i;
21             }
22             this.cnt = size;
23         }
24
25         public boolean union(int i, int j) {
26             int src = find(i);
27             int dst = find(j);
28             if (src != dst) {
29                 for (int k=0; k<ids.length; k++) {
30                     if (ids[k] == src) {
31                         ids[k] = dst;
32                     }
33                 }
34                 cnt--;
35                 return true;
36             }
37             return false;
38         }
39
40         public int find(int i) {
41             return ids[i];
42         }
43
44         public boolean areConnected(int i, int j) {
45             return find(i)==find(j);
46         }
47
48         public int count() {
49             return cnt;
50         }
51     }
52 }

Summary:

Dectect cycle in directed graph:

Detect cycle in a directed graph is using a DFS. Depth First Traversal can be used to detect cycle in a Graph. DFS for a connected graph produces a tree. There is a cycle in a graph only if there is a back edge present in the graph. A back edge is an edge that is from a node to itself (selfloop) or one of its ancestor in the tree produced by DFS. In the following graph, there are 3 back edges, marked with cross sign. We can observe that these 3 back edges indicate 3 cycles present in the graph.

To detect a back edge, we can keep track of vertices currently in recursion stack of function for DFS traversal. If we reach a vertex that is already in the recursion stack, then there is a cycle in the tree. The edge that connects current vertex to the vertex in the recursion stack is back edge. We have used recStack[] array to keep track of vertices in the recursion stack.

Detect cycle in undirected graph:

method 1: Union Find  The time complexity of the union-find algorithm is O(ELogV).

method 2: DFS + parent node  Like directed graphs, we can use DFSto detect cycle in an undirected graph in O(V+E) time. We do a DFS traversal of the given graph. For every visited vertex ‘v’, if there is an adjacent ‘u’ such that u is already visited and u is not parent of v, then there is a cycle in graph. If we don’t find such an adjacent for any vertex, we say that there is no cycle. The assumption of this approach is that there are no parallel edges between any two vertices.

时间: 12-23

Leetcode: Graph Valid Tree && Summary: Detect cycle in directed graph and undirected graph的相关文章

[LeetCode#261] Graph Valid Tree

Problem: 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]], r

LeetCode Graph Valid Tree

原题链接在这里:https://leetcode.com/problems/graph-valid-tree/ 题目: 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

Graph Valid Tree -- LeetCode

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 tru

Detect Cycle In Directed/Undirected Graph

Detect Cycle in a Directed Graph https://www.geeksforgeeks.org/detect-cycle-in-a-graph/ 有向图里的环必须是 a->b b->c c->a 类似这种的环(包括自环). 这学期刚上过算法,dfs遍历图会得到dfs tree(如果不是连通图就是forest),并提到了back edge的概念.如果dfs遍历图的时候,有back edge产生,那就说明一定有环. 写起来就按照标准的dfs写,需要一个visit

[Swift]LeetCode261.图验证树 $ Graph Valid Tree

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 tru

Graph Valid Tree

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. Notice You can assume that no duplicate edges will appear in edges. Since all edg

[LintCode] Graph Valid Tree

http://www.lintcode.com/en/problem/graph-valid-tree/ DFS 解法: public class Solution { /** * @param n an integer * @param edges a list of undirected edges * @return true if it's a valid tree, or false */ public boolean validTree(int n, int[][] edges) {

leetcode 261-Graph Valid Tree(medium)(BFS, DFS, Union find)

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. 这道题主要就是判断1.是否有环路 2. 是否是连通图 可以用DFS, BFS 和 Union find,union find最合适. 对于DFS和BFS,首先都是建立

261. Graph Valid Tree

也是卡了好多天的题目 主要就是介绍了union-find的算法,用于检查Undirected graph有没有环 http://www.geeksforgeeks.org/union-find/ 1 public boolean validTree(int n, int[][] edges) { 2 int[] parent = new int[n]; 3 Arrays.fill(parent, -1); 4 for(int i = 0; i < edges.length ; i++) { 5