BiruLyu
5/27/2017 - 5:52 PM

## 261. Graph Valid Tree(BFS).java

``````class Solution {
private int find(int[] parents, int i) {
if (parents[i] == -1) {
return i;
}
return find(parents, parents[i]);
}
public boolean validTree(int n, int[][] edges) {
int[] parents = new int[n];
Arrays.fill(parents, -1);

for (int[] e : edges) {
int a = find(parents, e[0]);
int b = find(parents, e[1]);
if (a == b) return false;
//union
parents[a] = b;
}
return edges.length == n - 1;
}

}``````
``````public class Solution {
public boolean validTree(int n, int[][] edges) {

// initialize vertices
for (int i = 0; i < n; i++)

for (int i = 0; i < edges.length; i++) {
int u = edges[i][0], v = edges[i][1];
}

boolean[] visited = new boolean[n];

// make sure there's no cycle
return false;

// make sure all vertices are connected
for (int i = 0; i < n; i++) {
if (!visited[i])
return false;
}

return true;
}

// check if an undirected graph has cycle started from vertex u
boolean hasCycle(List<List<Integer>> adjList, int u, boolean[] visited, int parent) {
visited[u] = true;

for (int i = 0; i < adjList.get(u).size(); i++) {

if ((visited[v] && parent != v) || (!visited[v] && hasCycle(adjList, v, visited, u)))
return true;
}

return false;
}
}``````
``````/*
To tell whether a graph is a valid tree, we have to:

Make sure there is no cycle in the graph - this has to be a none-cyclic graph;
Make sure every node is reached - this has to be a connected graph;

*/

public class Solution {
public boolean validTree(int n, int[][] edges) {
for(int i = 0; i < n; i++){
}

for(int i = 0; i < edges.length; i++){
int start = edges[i][0];
int end = edges[i][1];
}

boolean[] explored = new boolean[n];

for(boolean i : explored){
if (!i){
return false;
}
}
return true;
}

public boolean hasCycle(List<List<Integer>> adjList, int root, boolean[] explored){

while(!frontier.isEmpty()){
int node = frontier.poll();
if( !explored[node]){
for(int i = 0; i < adjList.get(node).size(); i++){
}
}
} else {
return true;
}
explored[node] = true;
}
return false;
}
}``````