โ Discrete Mathematics learning pathDiscrete Mathematics ยท Module 9 of 10
Trees and graph algorithms
Trees, spanning trees and shortest paths.
๐ Key ideas
- A tree is a connected graph with no cycles; a tree with n vertices has n - 1 edges.
- A spanning tree connects all vertices of a graph with no cycles.
- Minimum spanning tree algorithms: Kruskal (pick cheapest edges) and Prim (grow from a vertex).
- Shortest paths: Dijkstra for non-negative weights; BFS for unweighted graphs.
- Binary trees and their traversals (inorder, preorder, postorder) are used in computing.
๐ก Real-life example: A minimum spanning tree is the cheapest way to lay cables so every building on campus is connected.
TreeConnected acyclic graph
Spanning treeTree containing all vertices of a graph
Kruskal's algorithmMST by adding cheapest safe edges
Dijkstra's algorithmShortest paths with non-negative weights