Graph | Learn for Master
• ### Leetcode – Graph valid tree solution based on Union find set

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],

• ### Shortest Path Problems

Given a weighted graph G Given a weighted graph G (V,E), =(V,E), and a source vertex s, find the minimum weighted path from s to every other vertex in G

Unweighted graph

If the graph is unweighted, we can solve this problem using Bread First Search.

Weighted Graph

For Weighted Graph, we solve this problem use Dijkstra’s algorithm.

shortest path between all pairs of vertices

Given G(V,E), find a shortest path between all pairs of vertices.

Solutions: (brute -force) Solve Single Source Shortest Path for each vertex as source.