Graph Valid Tree

Depth-First Search-Python

You have a graph of n nodes labeled from 0 to n - 1. You are given an integer n and a list of edges where edges[i] = [ai, bi] indicates that there is an undirected edge between nodes ai and bi in the graph.

Return true if the edges of the given graph make up a valid tree, and false otherwise.

Constraints:

• 1 <= 2000 <= n
• 0 <= edges.length <= 5000
• edges[i].length == 2
• 0 <= ai, bi < n
• ai != bi
• There are no self-loops or repeated edges.

Intuition:

Recall that a graph, G, is a tree iff the following two conditions are met:

1. G is fully connected. In other words, for every pair of nodes in G, there is a path between them.
2. G contains no cycles. In other words, there is exactly one path between each pair of nodes in G.

Depth-first search is a classic graph-traversal algorithm that can be used to check for both of these conditions:

1. G is fully connected if, and only if, we started…