Continue reading “Disjoint Set – Union & Find”In computer science, a

Source: https://en.wikipedia.org/wiki/Disjoint-set_data_structuredisjoint-set data structure… is a data structure that stores a collection of disjoint (non-overlapping) sets. … It provides operations for adding new sets, merging sets (replacing them by their union), and finding a representative member of a set.

## Minimum Spanning Tree – Prim

Continue reading “Minimum Spanning Tree – Prim”A

Source: https://en.wikipedia.org/wiki/Minimum_spanning_treeminimum spanning tree(MST) orminimum weight spanning treeis a subset of the edges of a connected, edge-weighted undirected graph that connects all the vertices together, without any cycles and with the minimum possible total edge weight.

## Graph Algorithm: Topological Sort

When we are scheduling jobs or tasks, they may have dependencies, i.e., before we finish task a, we have to finish b first. In this case, given a set of tasks and their dependencies, how shall we arrange our schedules? There comes another graph algorithm: Topological Sort.

Continue reading “Graph Algorithm: Topological Sort”## Intro to Graph Algorithms – BFS & DFS

Graphs are a pervasive data structure in computer science, and algorithms for working with them are fundamental to the field.

Cormen, Thomas H., et al.Introduction to algorithms. MIT press, 2009.

Given a graph defined as G=(V,E) which is a set of vertices and edges, we’d be curious about how to represent it and how to search it systematically so as to visit the vertices following the edges. This blog will briefly introduce two ways of representations of a graph, and then will dive deep into two graph search algorithms: **Breadth-First-Search (BFS)** and **Depth-First-Search (DFS)**.