Graph Theory
Learn how graphs model connections and help solve algorithmic problems. Explore graph traversals, shortest paths, spanning trees, and more through practical tutorials.
IntroductionGraphs can solve a plethora of interesting problems!Bellman Ford AlgorithmBellman Ford Algorithm computes shortest paths from a single source vertex to all of the other vertices in a weighted digraphBinary Search TreeA binary tree where left child is less than or equal to the parent, while the right child is greaterBinary TreeBinary Tree is a tree structure in which eacho node only contains at most two childrenBreadth First Search (BFS)In BFS, we explore all the closest nodes first before going one step further.Depth First Search (DFS)In DFS, we aim to finish one branch before looking at other branches.Dijkstra's AlgorithmDijkstra's Algorithm is used to find the shortest paths between nodes in a graph.Disjoint Set Union (DSU)Disjoint Set Union is a data structure that allows us to combine any two sets into one.Kahn's AlgorithmKahn's Algorithm is a classical algorithm in computer science that is used for topological sorting of directed acyclic graphs (DAGs)Kruskal's AlgorithmKruskal's algorithm is a greedy algorithm used to find the minimum spanning tree of a connected, undirected graph.Lowest Common Ancestor(LCA)Lowest common ancestor (LCA) of two nodes x and y is the deepest(lowest) node that has both x and y as descendantsMinimum Spanning TreeA minimum spanning tree is a subset of the edges of a connected undirected graph with the minimum possible total edge weight and it does not contain any cycles.Tarjan's AlgorithmTarjan's algorithm can be used to determine the Strongly Connected Components of a directed graph.Topological SortingTopological Sorting is a linear ordering of its vertices such that for every directed edge (u, v) from vertex u to vertex v, u comes before v in the ordering.