Topological Sorts using indegree (Kahn's algorithm)

Tutorial - Kahn's Algorithm for Topological Sorting
             
                Shafaetsplanet

                Tutorial


ALGORITHM:


The usual algorithms for topological sorting have running time linear in the number of nodes plus the number of edges, asymptotically, ${\displaystyle O(\left|{V}\right|+\left|{E}\right|)}$.

Implementation:

Depth-first search Implementation

1 thing i always remember about dfs is "Using dfs We go to the depth of a node and then we come back"

I learned dfs from my friend and from this blog shafaetsplanet . In shafaetsplanet the algorithm is explained very easily.


Algorithm :


Basic DFS Traversal of a Graph:


Here starting node is 0.

Breadth-first search implementation

I learned bfs from my friend and from this blog shafaetsplanet . In shafaetsplanet the algorithm is explained very easily. There the bfs code was implemented using adjacent metrix. Here we will implement it using adj list.

from safaet's blog I will take few lines to show everyone how bfs works

     01. A node can't be visited more than once.
     02. The source node is always level 0.
     03. All nodes directly connected to level 0 or source node are level 1.
     04. All nodes directly connected to level 1 are level 2.And this is how level will keep on rising one by one.
     05. Level of each node is the shortest path distance from its source node


Basic Graph:

Second best mst (using Kruskal)

Sometimes we are asked to find Second best mst in some problems. We can do this with brute force.
At first we will find the mst and all the edges of mst. From all the edges of mst we will remove every edge once and and will create a new mst. In this way the minimum of all newly created mst is the Second best mst

mst:

yellow edges are edges of mst

sum of all weights is 110.

minimum spanning tree (Kruskal's algorithm) Implementation

There is an awesome kruskal algorithm tutorial  in - shafaetsplanet

here I will try to implement the algorithm in my way

a normal undirected graph