an EN Mean Value Theorem by Slidesgo.pptx

this shows the en mean value theorem

1. Topological Sort ASHWIN KUMAR V.L I - M.Sc Artificial Intelligence

2. What is Topological Sort? Topological Sort, a fundamental algorithm for ordering vertices in a Directed Acyclic Graph (DAG ). A topological sort of a dag G = (V,E) is a linear ordering of all its vertices such that if G contains an edge ( u, v), then u appears before v in the ordering. (If the graph contains a cycle, then no linear ordering is possible .) We can view a topological sort of a graph as an ordering of its vertices along a horizontal line so that all directed edges go from left to right.

3. Properties of Topological Sort * Acyclic Nature*: Topological sorting is only possible for DAGs. If the graph has cycles, a topological sort is not possible because there would be no way to order the vertices to satisfy all the directed edges . *Non-uniqueness *: A DAG can have multiple valid topological sorts. For example, different tasks that have no dependencies on each other can be ordered in any sequence.

4. Graph Representation To perform a Topological Sort, we need to represent our graph effectively. Common representations include adjacency lists and adjacency matrices . Choosing the right representation can significantly impact the performance of the algorithm.

5. Algorithms for Topological Sort 1. Depth-First Search (DFS) Based Algorithm Algorithm: Step 1: Initialize an empty stack to store the topological sort. Step 2: Mark all vertices as unvisited. Step 3: For each vertex, if it hasn't been visited, perform DFS from that vertex. During the DFS, mark the current vertex as visited. Recur for all the vertices adjacent to this vertex. After all adjacent vertices are processed, push the current vertex onto the stack. Step 4: After the DFS completes for all vertices, the stack will contain the topologically sorted order. Simply pop elements from the stack to get the order. Time Complexity: O(V+E), where V is the number of vertices and E is the number of edges. This method leverages the depth-first search traversal of the graph.

6. 2. Kahn’s Algorithm (BFS Based Algorithm) This method uses a BFS-like approach and is based on the concept of in-degree of vertices. Algorithm: Step 1: Compute the in-degree (number of incoming edges) for each vertex. Step 2: Initialize a queue with all vertices having in-degree of 0 (these vertices have no dependencies). Step 3: While the queue is not empty: Remove a vertex from the queue and add it to the topological order. Decrease the in-degree of all its neighboring vertices by 1. If any neighboring vertex's in-degree becomes 0, add it to the queue. Step 4: If all vertices are processed, the topological order is complete. If some vertices remain unprocessed (indicating a cycle), then the graph is not a DAG. Time Complexity: O(V+E)

7. Example W hen Professor Bumstead gets dressed in the morning. The professor must done certain garments before others (e.g., socks before shoes). Other items may be put on in any order (e.g., socks and pants)

8. (a) Professor Bumstead topologically sorts his clothing when getting dressed. Each directed edge (u, v) means that garment u must be put on before garment v. The discovery and finishing times from a depth-first search are shown next to each vertex.

9. (b) The same graph shown topologically sorted, with its vertices arranged from left to right in order of decreasing finishing time. All directed edges go from left to right.

10. Topological Sort has numerous applications , including task scheduling, build systems, and course prerequisites. By mastering this technique, you can efficiently manage dependencies and optimize workflows in various domains. Applications of Topological Sort

11. THANK YOU!!!