Graph Theory and it's Algorithms

Understand recursion as a function that calls itself until a base case is reached, transferring control, with driver code and recursive calls that backtrack, contrasting with iterative solutions.

Trace the recursive calls from main to phi, identify the base case at zero, and observe backtracking to the final value of six.

Learn to write recursive functions with a clear procedure, using factorial as a core example to identify the base case and recursive case, and trace calls step by step.

Learn how to convert iterative solutions to recursive ones by mapping loops to function calls, defining base and initial cases, and printing numbers from one to N.

Explore how to represent graphs using adjacency lists in Python, compare with adjacency matrices, and build dictionary-based adjacency lists for directed and undirected graphs.

Explore how adjacency matrix representation encodes weighted and unweighted graphs, including directed and undirected cases, by filling a matrix with weights and zeros for no self-loops.

Learn to implement graphs in Python using an adjacency list representation, build a graph class with objects, add edges for an undirected unweighted graph while printing it to study algorithms.

Learn depth-first search, a graph traversal algorithm that starts from any node and travels as deep as possible using a stack and a visited map, printing nodes as you backtrack.

Implement and trace a depth-first search in Python using an adjacency-list graph, with a recursive DFS function, a visited set, and backtracking.

Trace the dfs recursion on a graph using an adjacency list and a visited set, observing how nodes are printed in depth-first order from 1 to 4.

Explore the breadth first search algorithm (BFS) using a queue to visit a node's neighbors level by level, contrasting it with DFS in a practical example.

Implement a breadth-first search on a simple graph using a queue, a visited set, and an adjacency list to visit and print each node in first-in, first-out order.

Explore topological sort in directed acyclic graphs using DFS, recognizing prereq relationships where parents appear before children, and diagnosing cycles that prevent a valid order.

Master topological sort with a dfs-based approach: traverse from a node, backtrack to push vertices onto a stack, then pop to obtain the correct order for the given graph.

Code the topological sort by augmenting the dfs recursion to push nodes onto a self.stack during backtracking, then reverse the stack to obtain the last-in, first-out order.

Use depth-first search to visit all nodes and accumulate their values to compute the sum of all nodes in a graph.

Learn how to find the maximum node value in a graph using depth-first search, initializing a max variable and updating it as you visit each node.

Learn how to compute the minimum of all graph nodes by swapping max with min, initializing at infinity, and updating with comparisons to avoid zero as the minimum.

Explore single source shortest path problems on weighted graphs by selecting a source vertex and finding the shortest paths from that source to every other node, using Dijkstra's algorithm.

Compute the single-source shortest paths using Dijkstra's algorithm, starting with zero for the source and infinity for others, then iteratively relax edges to update minimal distances across a graph.

Explore how Dijkstra's algorithm updates the distance from the source to each vertex, comparing current distances with paths through neighbors and updating to the shortest total weight.

Apply Dijkstra's algorithm to a weighted graph by initializing distances, setting the source to zero, and iteratively relaxing neighbors to update shortest paths with a greedy minimum-distance step.

Demonstrates coding implementation of the Djikstra's algorithm to find the shortest paths from a source in a weighted graph using an adjacency matrix and Python lists.

Explore the Bellman-Ford algorithm for shortest paths, handling negative weights where Dijkstra's fails by repeatedly relaxing edges for v minus one times, updating distances from a chosen source.

Watch a dry run of the Bellman-Ford algorithm on a directed weighted graph with negative weights, showing iterative relaxation and distance updates.

Bellman-Ford algorithm using a list of edge tuples (u, v, w), relax edges V-1 times, and print the resulting shortest distances from the source.

Explains spanning trees and minimum cost spanning trees in graphs, clarifies vertices and edges, cycles, and demonstrates selecting the minimum-cost spanning tree using two algorithms.

Prim's algorithm uses a greedy approach to build the minimum spanning tree from a graph by repeatedly selecting the lightest edge connected to the growing set of vertices.