Leetcode List: https://leetcode.com/list/x1wy4de7

In computer science, graphs are used to represent networks of communication, data organization, computational devices, the flow of computation, etc. For instance, the link structure of a website can be represented by a directed graph, in which the vertices represent web pages and directed edges represent links from one page to another.

1. Union Find:

   Union–find data structure or disjoint-set data structure or merge–find set, is a data structure that stores a collection of disjoint (non-overlapping) sets. Equivalently, it stores a partition of a set into disjoint subsets. It provides operations for adding new sets, merging sets (replacing them by their union), and finding a representative member of a set. Helps to find the number of connected components, and can help to find MST.

   • Identify if problems talk about finding groups or components.

   Notes:

   1. We can use vector to hold the set of nodes or unordered_map<int, int> if we don't know the amount of nodes.
   2. If the parent[id] == id, we know that id is the root node.
   3. The data structure using two methods Union() - union to nodes/components, and Find() - find the root node.

2. Depth First Search

   It is an algorithm for traversing or searching tree or graph data structures. The algorithm starts at the root node (selecting some arbitrary node as the root node in the case of a graph) and explores as far as possible along each branch before backtracking.

   • DFS using examples

   Notes:

   1. Algorithm usually uses recursion implementation.
   2. We mark the node as visited and will keep exploring its neighbors if there are not yet explored.
   3. DFS can be useful to find connected components. We can iterate through the nodes and call dfs() to find all nodes which belongs to component.
   4. We can use unordered_map<int, vector> to represent the graph.

3. Breadth First Search

   Breadth-first search (BFS) is an algorithm for searching a tree data structure for a node that satisfies a given property. It starts at the tree root and explores all nodes at the present depth prior to moving on to the nodes at the next depth level. Extra memory, usually a queue, is needed to keep track of the child nodes that were encountered but not yet explored.

   • BFS using examples

   Notes:

   1. Algorithm uses queue for implementation.
   2. It checks whether a vertex has been explored before enqueueing the vertex.
   3. We can track if the node was already explored by modifying the original matrix.
   4. BFS algorithm can be instructed with additional array dist which can help totrack the parent node of the next node. This will help to reconstruct the pathby looping backward from end node.

4. Graph coloring/Bipartition

   • Bipartite graph examples:

5. Topological Sort:

   Is a linear ordering of its vertices such that for every directed edge uv from vertex u to vertex v, u comes before v in the ordering.

   • Check if its directed acyclic graph and we have to arrange the elements in an order in which we need to select the most independent node at first. Number of in-node 0

   Notes:

   1. We will have the indegree array to count, which nods should be visited first.

   2. We will have a queue to push the nodes that don't have any dependencies.

Graph Standard Algorithms

SSSP Algorithms

• Now we will be using the problem https://leetcode.com/problems/network-delay-time/ to revise standard SSSP graph algorithms.

MST Algorithms

A minimum spanning tree (MST) is 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.

• Now we will be using the problem https://leetcode.com/problems/min-cost-to-connect-all-points/ to revise MST Algorithms.

Notes:

1. One of the implementation of MST algorithm use Union Find algorithm (Kruskal's Algorithm).

2. We need to sort elements by the weight before appying the algorithm, or we can use min priority_queue.

Disjoint Set Union: