Spanning Tree in data structure and .pptx

H

1. Muneeba Tahreem 2022-CS-544 Muhammad Rameez 2022-CS-543 Ali Haider Javed 2022-CS-509 Abu Bakar Siddique 2022-CS-554 Group Members:

2. Application of Graph: Graph: A graph is a non-linear data structure, which consists of vertices(or nodes) connected by edges(or arcs) where edges may be directed or undirected . In   Computer science  graphs are used to represent the flow of computation .

3. Conti.. In computer science , graphs are used to represent networks of communication, data organization, computational devices, the flow of computation etc. Software engineering Graph has many applications in software engineering. For example: during Requirements Specification, Data Flow diagrams are used where vertices represent transformations and edges represents the data flows. Google maps  uses graphs for building transportation systems, where intersection of two(or more) roads are considered to be a vertex and the road connecting two vertices is considered to be an edge, thus their navigation system is based on the algorithm to calculate the shortest path between two vertices

4. Application of Graph: In   Facebook , users are considered to be the vertices and if they are friends then there is an edge running between them. Facebook’s Friend suggestion algorithm uses graph theory. Facebook is an example of  un directed graph .

5. Application of Graph In   World Wide Web , web pages are considered to be the vertices. There is an edge from a page u to other page v if there is a link of page v on page u. This is an example of  Directed graph . In the  Dijkstra   algorithm , we use a graph. we find the smallest path between two or many nodes. On  social   media  sites , we use graphs to track the data of the users. liked showing preferred post suggestions, recommendations, etc.

6. Application of Graph: Graph algorithms There are many graph algorithms that can be used to solve problems related to graphs. These algorithms include graph traversal algorithms, shortest path algorithms, and minimum spanning tree algorithms. Different activities of a project can be represented using a graph. This graph can be useful in project scheduling

7. Exploring Spanning Trees and Prim's Algorithm Welcome to the enchanting world of spanning trees! In this presentation, we will dive deep into the concept of minimum spanning trees and the elegant Prim's algorithm.

8. Spanning Tree: An Introduction At its core, a spanning tree is a subset of edges in a connected graph that spans all the vertices without forming any cycles. It acts as the backbone, connecting all the nodes while ensuring there are no loops. Let's explore further!

9. s Properties of a Spanning Tree 1 Connectivity 🌐 A spanning tree ensures that all vertices in the graph are reachable from any other vertex. 2 No Cycles 🔄 By definition, a spanning tree avoids forming any loops or cycles among the nodes. 3 Minimum Number of Edges ⚖️ A spanning tree contains the minimum number of edges to connect all the vertices in the graph.

10. Minimum Spanning Tree (MST) The concept of Minimum Spanning Tree focuses on finding a spanning tree with the minimum possible weight. It is highly useful for optimizing network designs, construction projects, and more. Let us dig deeper into this fascinating concept.

11. Finding MST: Different Algorithms Kruskal's Algorithm Kruskal's algorithm takes a greedy approach, selecting edges in ascending order of weight and adding them to the MST as long as they don't create cycles. Prim's Algorithm Prim's algorithm follows a greedy strategy, starting from an arbitrary vertex and continuously growing the MST by adding the edge with the lowest weight.

12. Prim's Algorithm: Overview Prim's algorithm begins with a single vertex and incrementally expands the MST by connecting the closest vertex not yet in the tree until all vertices are included. Let's unravel the magic of Prim's!

13. Example and Analysis of Prim's Algorithm Analyzing the Graph We will illustrate how Prim's algorithm unfolds step by step on a graph, demonstrating the growing MST and the decisions made at each iteration. Output: Minimum Spanning Tree After executing Prim's algorithm, we will witness the emergence of the minimum spanning tree, highlighting the importance of selecting the optimal edges to minimize the overall weight.

14. Conclusion In this journey through the captivating world of spanning trees and Prim's algorithm, we explored the fundamental concepts, examined various ways to find the minimum spanning tree, and analyzed the inner workings of Prim's algorithm. Now you possess the knowledge to conquer the realm of optimization and connectivity!

15. Kruskal's Algorithm Welcome to our presentation on Kruskal's Algorithm. Learn about minimum spanning trees, the importance of finding them, and how Kruskal's algorithm helps us solve this problem efficiently.

16. Minimum Spanning Trees Definition Minimum spanning trees are trees that connect all the vertices of a graph with the minimum total edge weight. Importance They have various applications such as designing network communication systems, constructing road networks, and organizing computer clusters.

17. Kruskal's Algorithm 1 Step 1: Sorting the Edges Sort the edges of the graph in non-decreasing order based on their weights. 2 Step 2: Selecting the Edges Select edges from the sorted list, starting with the smallest weight, and add them to the minimum spanning tree if they don't create cycles. 3 Step 3: Detecting and Avoiding Cycles Use a disjoint set data structure to detect cycles in the tree and avoid adding edges that create cycles.

18. Illustrative Example Initial Graph A graph with 7 vertices and 9 edges. Sorted Edges List of edges sorted in non-decreasing order based on their weights. Minimum Spanning Tree Final minimum spanning tree obtained using Kruskal's algorithm.

19. Time Complexity Analyzing Kruskal's Algorithm The time complexity of Kruskal's algorithm is O(E log V), where E is the number of edges and V is the number of vertices. Efficiency Kruskal's algorithm has excellent performance for sparse graphs, making it suitable for large-scale applications.

20. Practical Applications Network Design Kruskal's algorithm assists in designing efficient network infrastructures, ensuring optimal connectivity at minimal cost. Transportation Planning It aids in planning transportation routes to maximize efficiency and minimize travel distances. Data Clustering By finding the minimum spanning tree, it helps organize data clusters for streamlined analysis and processing.

21. Conclusion 1 Key Takeaways Understanding minimum spanning trees and Kruskal's algorithm unlocks the ability to efficiently solve network and connectivity optimization problems. 2 Further Exploration Dive deeper into graph theory and explore other algorithms like Prim's algorithm and Boruvka's algorithm.

22. Dijkstra's Algorithm Journey through the world of graph theory and discover how Dijkstra's Algorithm changed the way we think about shortest paths.

23. What is Dijkstra's Algorithm? Dijkstra's algorithm is a graph search algorithm that solves the single-source shortest path problem for a graph. It finds the shortest path from a starting node to all other nodes in a weighted graph. How Does It Work? The algorithm processes the graph in layers, visiting vertices in order of their distance from the starting vertex. Why is it Important? Dijkstra's algorithm has many practical applications, including finding shortest routes on road maps and routing data packets across the internet.

24. Exploring the Problem The shortest path problem is a classic problem in graph theory. It involves finding the shortest path between two nodes in a graph with weighted edges. This problem has many real-world applications, such as finding the shortest route between two cities, minimizing travel time between airports, and routing messages through a computer network. Travel Shortest path algorithms can be used to find the shortest route between two cities. Networking Routing algorithms can be used to find the shortest path for data packets in a computer network.

25. Example of Dijkstra's Algorithm

26. Pseudocode of Dijkstra's Algorithm 1. Create a set of unvisited vertices
2. Set the distance of the starting vertex to zero and all others to infinity
3. While the destination vertex has not been visited:
4.   a) Select the vertex with the smallest distance that hasn't been visited
5.   b) For each neighbor of the selected vertex, update its distance
6.   c) Mark the selected vertex as visited
7. Return the shortest path to the destination vertex

27. Examples of Dijkstra's Algorithm One of the most common real-world applications of Dijkstra's algorithm is in routing packets of data across the internet. Routing Packets Dijkstra's algorithm can be used to find the shortest path for data packets in a computer network. Shortest Route Dijkstra's algorithm can be used to find the shortest route between two cities on a road map.

28. Comparison with Other Algorithms Dijkstra's algorithm is not the only algorithm used to find the shortest path in a weighted graph. Other algorithms include Bellman-Ford algorithm, Floyd-Warshall algorithm and A* Search algorithm. Bellman-Ford Works with negative edge weights. Floyd-Warshall Works with negative edge weights and gurantees the shortest path between every pair of nodes. A* Search Used in pathfinding and graph traversal applications, based on a heuristic function to guide the search.

29. Performance and Time Complexity The worst-case time complexity of Dijkstra's Algorithm is O(E+VlogV), where E is the number of edges and V is the number of vertices in the graph. 1 Advantages Dijkstra's algorithm is easy to understand and has good performance on small graphs with non-negative edge weights. 2 Disadvantages Dijkstra's algorithm does not work with negative edge weights and may not be the most efficient algorithm for larger graphs.

30. Conclusion and Key Takeaways Dijkstra's algorithm is an important algorithm in graph theory and computer science. It changed the way we think about shortest paths and has many practical applications in networking, routing, and mapping. While it has its limitations, it remains a valuable tool for solving the shortest path problem in many situations.