A comparative analysis of Prim, Kruskal, and Reverse-Delete algorithms in optimizing routes within Terengganu’s and Pahang’s attraction road network / Munashahira Mohammad Zahid
This paper presents a detailed comparison of three greedy algorithms—Prim, Kruskal, and Reverse-Delete—in optimizing the routes within Terengganu’s and Pahang’s attraction road network. The goal is to determine the most effective algorithm for constructing the minimum spanning tree (MST) that minimi...
Saved in:
| 主要作者: | |
|---|---|
| 格式: | Thesis |
| 语言: | English |
| 出版: |
2024
|
| 主题: | |
| 在线阅读: | https://ir.uitm.edu.my/id/eprint/106184/1/106184.pdf |
| 标签: |
添加标签
没有标签, 成为第一个标记此记录!
|
| 总结: | This paper presents a detailed comparison of three greedy algorithms—Prim, Kruskal, and Reverse-Delete—in optimizing the routes within Terengganu’s and Pahang’s attraction road network. The goal is to determine the most effective algorithm for constructing the minimum spanning tree (MST) that minimizes total travel distance. Prim’s algorithm builds the MST by starting from an arbitrary node and continually adding the smallest edge that connects a vertex in the tree to a vertex outside the tree. Kruskal’s algorithm, on the other hand, constructs the MST by sorting all the edges and adding the smallest edge to the tree, as long as it doesn’t form a cycle. The Reverse-Delete algorithm works in reverse; it starts with the full graph and iteratively removes the largest edges, ensuring that the graph remains connected. This study meticulously evaluates each algorithm’s computational efficiency, implementation complexity, and performance in generating optimal routes. |
|---|