Member Avatar for Zay

Hello;

can any 1 explain to me how to find the miniumum spanning tree for a graph ?


see this graph as an example :

Image1.jpg 10.53 KB
  • 4 Contributors
  • 9 Replies
  • 210 Views
  • 4 Years Discussion Span
  • Latest Post Latest Post by Dmitry74

Dani AI

Generated

As 's post shows, a short, exam-friendly recipe is often more useful than long theory. Building on 's pointer to standard MST methods and 's visualization idea, a compact, practical approach is given below (no external links).

A fast hand method (edge-sorting / Kruskal-style):

  • List every edge and sort by increasing weight.
  • Track components (initially each vertex alone).
  • Scan edges from smallest to largest: if an edge connects two different components, add it to the tree and merge those components; if it would close a cycle, skip it.
  • Stop when exactly V-1 edges have been taken (for a connected graph). For disconnected graphs this produces a minimum spanning forest.
  • Equal-weight edges: any tie-breaking that avoids cycles is fine; multiple MSTs can exist.

A minimal C++-style sketch (concept only):

struct DSU { vector<int> p, r; DSU(int n):p(n){iota(p.begin(),p.end(),0);} int find(int x){return p[x]==x?x:p[x]=find(p[x]);} bool unite(int a,int b){a=find(a); b=find(b); if(a==b) return false; p[b]=a; return true;} };
struct Edge{int u,v,w;};
sort(edges.begin(), edges.end(), [](auto &a, auto &b){ return a.w < b.w; });
DSU d(n);
for(auto &e: edges) if(d.unite(e.u,e.v)){ mst.push_back(e); total += e.w; if(mst.size()==n-1) break; }

Quick tips: Kruskal is easy to implement and hand-simulate; Prim (the grow-from-a-vertex method) is better for dense graphs or adjacency-matrix code. MSTs require undirected weighted graphs; for directed graphs the problem is different.

Recommended Answers

All 9 Replies

Member Avatar for Narue

There are several ways. Not to mention that graph algorithms tend not to be trivial, so you'd be better off studying existing solutions, like Prim or Kruskal's algorithms.

Member Avatar for Zay

i do not know these algorithms
we just studying Chapter of graph quickly and with out coding.

but see this solved example :

Im21.jpg 16.17 KB Imag22e2.jpg 9 KB
Member Avatar for ~s.o.s~

> i do not know these algorithms
You would have to learn them to solve the problem at hand. Try the wikipedia. It should help you in getting started at least.

Member Avatar for Narue

>i do not know these algorithms
Which is why I suggested that you study them. If you did know them, you wouldn't be asking how to find a minimum spanning tree. Really, is Google that difficult to use?

Member Avatar for Zay

>i do not know these algorithms
Which is why I suggested that you study them. If you did know them, you wouldn't be asking how to find a minimum spanning tree. Really, is Google that difficult to use?

and it's so difficult to learn some one don't know !

what can i do if teachers don't explain it , and there is no time to search and search .

Member Avatar for ~s.o.s~

But the fact remains that you _do_ have to study them by hook or by crook. Otherwise how do you expect to clear the test?

is a site which would help you in learning them with those pretty visualizations.

Member Avatar for Narue

>and it's so difficult to learn some one don't know !
I gave you the exact name of two algorithms that find a minimum spanning tree. What more do you want? Me to write up two super easy implementations and describe how every line works? I didn't feel the need to do that when just about every result from Google has sample code.

>what can i do if teachers don't explain it , and there is no time to search and search .
http://en.wikipedia.org/wiki/Prim's_algorithm
That's the first result from Google. It took me about 5 seconds to search and search. Stop being a weenie and show some effort.

Member Avatar for Zay

ohh,

stop it plz

sorry sr for wasting your time in typing

and thanks for the algorithm's name

Member Avatar for Dmitry74

There is a good software for solving travelling salesman problem and searching the minimal spaning tree at www.susaninlab.com

Be a part of the DaniWeb community

We're a friendly, industry-focused community of developers, IT pros, digital marketers, and technology enthusiasts meeting, networking, learning, and sharing knowledge.