A solution to the problem of finding an optimal spanning tree using the computer
This paper presents two algorithms in finding an optimal (minimum or maximum) spanning tree of a given weighted, simple, connected graph G on n vertices, where 1 n 10. The algorithms, which are a version of Kruskal's and Prim's algorithms combined, are coded into two programming languages...
Saved in:
| Main Authors: | , |
|---|---|
| Format: | text |
| Language: | English |
| Published: |
Animo Repository
1991
|
| Subjects: | |
| Online Access: | https://animorepository.dlsu.edu.ph/etd_bachelors/15943 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| Institution: | De La Salle University |
| Language: | English |
| Summary: | This paper presents two algorithms in finding an optimal (minimum or maximum) spanning tree of a given weighted, simple, connected graph G on n vertices, where 1 n 10. The algorithms, which are a version of Kruskal's and Prim's algorithms combined, are coded into two programming languages namely CLIPPER and TURBO C. A detailed proof of the algorithm for finding a minimum spanning tree of G is provided. The researchers likewise presented a variation of Kruskal's algorithm, that is, finding optimal spanning trees with arbitrarily fixed edges. |
|---|