Graph Theory
Welcome to our Graph Theory tutorial page! Graph theory is a branch of mathematics that deals with the study of graphs and their properties. In computer science, graph theory is used to model and analyze problems related to networks, such as social networks, transportation networks, and communication networks. In below tutorials, we will cover the basic concepts of graph theory. We will start with an introduction to the basic definitions and terminologies used in graph theory and then move on to more advanced topics such as graph traversals, shortest paths, and network flow.
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.