1. Python Programming examples on “Connected Components using BFS”
The section contains Python programs to check the connectivity of directed and undirected graphs using BFS, implement bfs in a graph, programs to find shortest and connected componenets using bfs. Breadth first search is an algorithm for traversing or searching tree. Breadth first search is the most popular and commonly used approach in a graphs. BFS starts at the tree root and explores all of the neighbor nodes at the present depth level and then move to the nodes at the next depth level. An undirected graph is a set of objects that are connected together, where all the edges are bidirectional.
2. Python Programming examples on “Connected Components using DFS”
The section contains Python programs to check the connectivity of directed and undirected graphs using DFS, implements dfs in a graph with and without using recursion. Performs topological sort using DFS and checks for cycles in graphs. Depth first search is an algorithm for traversing or searching tree or graph data structures. DFS algorithm starts at the root node and explores as far as possible along each branch before backtracking. DAG is a special directed graph. DAG is a finite directed graph with no directed cycles. It consists of many vertices and edges. Topological Sorting for a graph is not possible if the graph is not a DAG.
3. Python Programming examples on “Shortest Path”
Dijkstra’s Shortest Path Algorithm is used to find the shortest paths between nodes in a graph. Bellman Ford algorithm computes the shortest paths from a single source vertex to the other vertices in a weighted digraph. Floyd Warshall algorithm is an algorithm for finding the shortest paths in a weighted graph with positive or negative edge weights. Prim’s algorithm is a greedy algorithm which finds a minimum spanning tree for a weighted undirected graph. Kruskal’s algorithm is used to find a minimum spanning tree for a connected weighted graph. Johnson’s algorithm helps to find the shortest paths between all pairs of vertices in a sparse, edge weighted and directed graph. The Python programs in this section implements dijkstra’s algorithm, johnson’s algorithm, bellmanford and floyd-warshall algorithm. The Python programs in this section also finds the minimum spanning tree using prims and krusals algorithm.