โ† Discrete Mathematics learning path
Discrete Mathematics ยท Module 9 of 10

Trees and graph algorithms

Trees, spanning trees and shortest paths.

๐Ÿ“– Key ideas

  1. A tree is a connected graph with no cycles; a tree with n vertices has n - 1 edges.
  2. A spanning tree connects all vertices of a graph with no cycles.
  3. Minimum spanning tree algorithms: Kruskal (pick cheapest edges) and Prim (grow from a vertex).
  4. Shortest paths: Dijkstra for non-negative weights; BFS for unweighted graphs.
  5. 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