How to create a complete responsive Online Portfolio – Personal Portfolio Website Design Template – Using HTML CSS JavaScript
Handout 6 in Graph Theory: Minimum Spanning Tree (Kruskal’s Algorithm)
In the previous post we saw how to determine mst using Primus algorithm. What mst is also said in previous post. In this post we will look at another algorithm to find mst which is known as Kruskal’s Algorithm. This is the simplest algorithm to find mst. But you must know about disjoint set data structure, if you don’t know then you must see this post.
I will not use my own picture in this post. Kruskal is very well written on the wiki, I will try to explain the algorithm briefly using the pictures there.
First we don’t even have an edge in the tree. We will sort the edges of the original graph according to cost. I will take the edge of the lowest cost first, the edge of the highest cost will be taken later. If the cost of two edges is equal, I can take any one first. Then take one edge at a time and see if there is already a path between the two edge nodes, if there is then taking the edge will create a cycle, so we will not take that edge. As you can see, this is also a ‘greedy’ algorithm like PRIMS.
Personal Portfolio Website Design Free Download
Above AD and CE are the lowest cost edges. We subgraph AD.
Similarly add CE then DF, AB and BE:
Then the smallest edge is EF, we cannot take it because taking EF will create a cycle, the path from E to F is already there, so there is no need to take the edge. Thus the edges in red along with BC,DB will be dropped as they form a cycle.
Finally adding EG we get mst.
Now we come to the implementation. Our first task is to sort. The next task is to check with an edge whether the two edge nodes have a path between them, i.e. they are inside the same component. It will need to check the disjoint set. In the tutorial on disjoint sets, I showed how to find out whether two nodes are in the same subgraph or not. That’s what you do here. Then if they are not in the same subgraph it will bring them together by calling the Union function as before and saving the edge in a vector or array.
Below is an implementation, hopefully it makes sense without copying:
struct edge {
int u, v, w;
bool operator<(const edge& p) const
{
return w < p.w;
}
};
int pr[MAXN];
vector<edge> e;
int find(int r)
{
return (pr[r] == r) ? r : find(pr[r]);
}
int mst(int n)
{
sort(e.begin(), e.end());
for (int i = 1; i <= n; i++)
pr[i] = i;
int count = 0, s = 0;
for (int i = 0; i < (int)e.size(); i++) {
int u = find(e[i].u);
int v = find(e[i].v);
if (u != v) {
pr[u] = v;
count++;
s += e[i].w;
if (count == n – 1)
break;
}
}
return s;
}
int main()
{
// READ(“in”);
int n, m;
cin >> n >> m;
for (int i = 1; i <= m; i++) {
int u, v, w;
cin >> u >> v >> w;
get edge;
get.u = u;
get.v = v;
get.w = w;
e.push_back(get);
}
cout << mst(n) << endl;
return 0;
}
Complexity Analysis:
Let E be the number of edges. Sort the edges, complexity O(ElogE), then run a linear loop over only the edges. Then the total complexity is O(ElogE)
.
I have given many simple problems related to mst in Prims tutorial, you can solve them and practice. For a better problem, see:
2nd best spanning tree?
Many times the problem asks to find the second best MST. We can brute force it out. After extracting the MST, we have to exclude each of the edges that we get and calculate a new MST, in this way the MST that is minimum is the second best MST.
Data Structure: Disjoint Set(Union Find)
Data structures are one of the fascinating areas of computer science. We can store data on computers in numerous ways. We can make a binary tree, then go down that tree and extract the data in logN, make a queue like a bus line, make a prefix tree or trie and do a very fast string search. Today we will look at an amazing data structure called “Disjoint Set”.
Disjoint sets are very important to implement algorithms like kruskal’s MST or tarjan’s offline LCA. To implement this we need nothing more than an array.
First we will see what kind of work we need this data structure for. I think A,B,C,D,E are 5 people. If A-B are friends and if B-C are friends then we can say A-C are also friends, i.e. their friendship is transitive. Now I said that A-B,B-C,D-E are friends of each other. Now I asked you whether A-C are friends of each other? Are B-D friends? The answer to the first question will be “yes”, the answer to the second question will be “no”.
It is easy to understand that the nodes in the graph which are in the same component or subgraph are friends of each other. So to know if two people are friends we need to see if they are in the same subgraph. It can be easily figured out by running BFS or DFS. But even better than these is “Disjoint Set”, you will understand why it is good after a while.
Personal Portfolio Website Design Free Download
If each person is a node, the solution idea with a disjoint set is:
1. All those who are friends of each other belong to the same set
2. There are as many sets as there are subgraphs
3. Each set will have a representative.
4. Two nodes are in the same set if their representative is the same. So to understand whether two people are friends or not we have to check the representative of the set they belong to.
Before Download
You must Join our Facebook Group and Subscribe YouTube Channel
All Links in Below:
Join Our FreeWebsiteCreate Facebook Group to get an instant update for projects, templates, design resources, and solutions.
Join Our YouTube Channel & Subscribe with Bell Icon for New Video:
Join Our Official Facebook Page For the Latest updates All Code Projects are Free:
Visit our service page to get premium services.
Free Website Create – HTML CSS, PHP, JavaScript Programming Projects For Free
Follow Us
Thank You,
Before Download
You must Join our Facebook Group and Subscribe YouTube Channel
FreeWebsiteCreate.net tries to provide HTML, CSS, SCSS, JavaScript, React, Android Studio, Java, PHP, Laravel, Python, Django, C#(C Sharp), and ASP.net-related projects 100% free. We try to make learning easier. Free Website Create always tries to give free projects to new learners. Free projects and source code will help to learn quickly.
They can save time and learn more. In this post, we share a free portfolio project website code with HTML and CSS. This free code portfolio contains a single landing page with a responsive design. In this post, we get a free best carpenter and craftsman service website designed by FreeWebsiteCreate with HTML, CSS, Bootstrap, and JavaScript.