You are to implement Kursakal\'s algorithm. Which data structures and algorithms

Question

You are to implement Kursakal's algorithm. Which data structures and algorithms you would use and why those rather than some alternative. Be sure to specify the contents of any required record types.

Kursakal's Minimum Cost Spanning Tree Algorithm:

(a) create a forest F (a set of trees), where each vertex in the graph is a separate tree.

(b) create a set S containing all the edges in the graph.

(c) while S is nonempty and F is not yet spanning
- remove an edge with minimum weight from S
- if that edge connects two dierent trees, then add it to the forest, combining two trees into a single tree

- otherwise discard that edge.

At the termination of the algorithm, the forest has only one component and forms a minimum spanning tree of the graph.

Explanation / Answer

-> This Program is to implement Kruskal algorithm. -> This program is to find minimum spanning tree for undirected weighted graphs -> Data Structers used: Graph:Adjacency Matrix -> This program works in microsoft vc++ 6.0 environment. **************************************************************/ #include class kruskal { private: int n; //no of nodes int noe; //no edges in the graph int graph_edge[100][4]; int tree[10][10]; int sets[100][10]; int top[100]; public: void read_graph(); void initialize_span_t(); void sort_edges(); void algorithm(); int find_node(int ); void print_min_span_t(); }; void kruskal::read_graph() { cout

Related Questions

Navigate

• Browse (All)
• Browse Y
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.