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

    [Read More...]
  • 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.  

    [Read More...]