Ronzii's Blog

Just your average geek's blog

Kruskal’s algorithm

Kruskals Algorithm is used to find the minimum spanning tree for a connected weighted graph and is an ideal greedy algorithm. Additionally, I’ve calculated the total weight of the Minimum Spanning Tree.

Algorithm

1. Take a Forest or a set of edges as input.

2. Create sets for each vertices. What I’ve done is merely kept track of the parent of each list i.e if the parent is same then they belong to the same list.

3. Now, Sort all the edges in non-decreasing order of their weights.

4. Extract the smallest edge (u,v). Compare whether they belong to the same set or not.  If the edge connects two different trees add it to the MST otherwise discard that edge.

The time complexity of this algorithm is O(E log V) where E is number of edges and V is number of vertices.

#include<iostream>
#include<vector>
#include<cstdio>
#include<algorithm>
#define MAX 10001
#define edge pair<int,int>
using namespace std;
vector< pair<int, edge > > Graph,MST;
int n,e,parent[MAX];
void initialize(int n)
{
    for(int i=1; i<=n; i++)
    {
        parent[i] = i;
    }
    MST.clear();
    Graph.clear();
}
int findSet(int x, int *parent)
{
    if(x!=parent[x])
    {
        parent[x] = findSet(parent[x],parent);
    }
    return parent[x];
}
void kruskal()
{
    sort(Graph.begin(),Graph.end());
    int total = 0;
    for(int i=0; i<e; i++)
    {
        int pu = findSet(Graph[i].second.first,parent);
        int pv = findSet(Graph[i].second.second,parent);
        if(pu!=pv)
        {
            total+=Graph[i].first;
            MST.push_back(Graph[i]);
            parent[pu] = parent[pv];
        }
    }
    cout<<total<<"\n";
}
int main()
{
    cin>>n>>e;
    initialize(n);
    int u,v,w;
    for(int i=0; i<e; i++)
    {
        cin>>u>>v>>w;
        Graph.push_back(pair<int, edge>(w,edge(u,v)));
    }
    kruskal();
    return 0;
}
Advertisements

July 7, 2011 Posted by | C++ | , , , | Leave a comment

Dijkstra’s algorithm using STL

Dijkstra’s algorithm requires a priority queue so I have used STL’s inbuilt priority queue functions. The class Prioritize ensures that the queue remains sorted according to the first value of the pair<int,int> object

Algorithm
1. Assign to every node a distance value: set it to zero for our initial node and to infinity(999) for all other nodes. Mark all nodes as unvisited.
2. Set initial source as current.
3.  Consider all its unvisited neighbors and calculate their distance. For example, if current node (A) has distance of 1, and an edge connecting it with another node (B) is 2, the distance to B through A will be 1+2=3
4.When we are done considering all neighbors of the current node, mark it as visited. A visited node will not be checked ever again; its distance recorded now is final and minimal
5. The next current node will be the node with the lowest distance in the unvisited set that is the topmost element of the priority queue.

#include<iostream>
#include<cstdio>
#include<vector>
#include<queue>
#define pp pair<int,int>
using namespace std;
class Prioritize
{
public:
    int operator() ( const pair<int, int>& p1, const pair<int, int>& p2 )
    {
        return p1.second < p2.second;
    }
};
int main()
{
    priority_queue<pp, vector<pp > , Prioritize > Q;
    int n;
    cin>>n;
    vector< pp > G[n+1];
    int e,u,v,w;
    cin>>e;
    for(int i=0;i<e;i++)
    {
        cin>>u>>v>>w;
        G[u].push_back(pp(v,w));
        G[v].push_back(pp(u,w));
    }
    int s;
    cin>>s;
    int d[n+1];
    for(int i=1;i<=n;i++)
    {
        d[i] = 999;
    }
    d[s] = 0;
    Q.push(pp(s,d[s]));
    while(!Q.empty())
    {
        u = Q.top().first;
        Q.pop();
        int size = G[u].size();
        for(int i = 0 ; i < size ; i++)
        {
            v = G[u][i].first;
            w = G[u][i].second;
            cout<<u<<" "<<v<<" "<<w<<endl;
            if(d[v] > d[u] + w)
            {
                d[v] = d[u] + w;
                Q.push(pp(v,d[v]));
            }
        }
    }
    for(int i=1; i<=n; i++) printf("Node %d, min weight = %d\n", i, d[i]);
    return 0;
}

July 7, 2011 Posted by | C++ | , , , , | 2 Comments