Leetcode – Graph valid tree solution based on Union find set

Tags: , , ,

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 true.

Given n = 5 and edges = [[0, 1], [1, 2], [2, 3], [1, 3], [1, 4]], return false.

Hint:

Given n = 5 and edges = [[0, 1], [1, 2], [3, 4]], what should your return? Is this case a valid 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.

Analysis

To check whether a graph is a tree, we should determine:

  1. whether there is a cycle, if there is cycle, it is not a tree.
  2. whether the nodes are connected. If it is not connected, it is not tree. 

A great data structure for checking whether a set of nodes are connected is the union find set (UFS). 

The data structure of union find set provides three operations:

union: merge two nodes into one set
find: get the set id of a node
count: get the number of disjoint set. 

The basic idea of UFS is to use an array to store all the nodes. Initially, each node belongs to a single set.  We have node.parent == node. 

Given an edge (ni, nj),  we know ni, nj should be merged, so we use the union operation. In this case, we set ni.parent as nj.

When we do the union, we also consider the height of the tree. We can append the tree with longer path to the tree with shorter path, such that the tree tends to be balanced.  Another technique is called path compression: each node will points to its parent directly. 

To check whether two nodes belong to the same set, we use the find operation. We check whether:

find(ni) == find(nj)

Java Implementation: