Kruskal’s Minimum Spanning Tree Algorithm

Standard

Kruskal’s algorithm is the best and probably fastest option if you’re urging to form a subgraph of a graph connecting all nodes. Some implementations are shown.

Minimum Spanning Tree
To form an MST(Minimum Spanning Tree) follow this procedure,

1. Begin with a connected graph G.
2. E is the set of all edges of different weights, from G.
3. Sort edges of E in the ascending order of their weights.
4. Go through each member(edge) of E and see if the nodes of that edge is already connected or not.
5. If they aren’t connected, connect them and include that member of E(edge) int MST.
6. Continue this process untill you’ve got n-1 edges(in case of n nodes).

An implementation in C++ using Disjoint Set data structure, is shown

#include <cstdio>
#include <algorithm>
#define MAX_node 100000
using namespace std;

struct edg{
	int a,b,w;
	bool operator < (const edg &b) const{
		return w<b.w;
	}
}E[MAX_node+1];

int Prev[MAX_node+1];
int parent(int a){
	if(a==Prev[a]) return a;
	return Prev[a]=parent(Prev[a]);
}

int main(){
	int node,edge;
	while(scanf("%d%d",&node,&edge)){
		
		int TOTAL=0;
			
		for(int i=1;i<=node;i++) Prev[i]=i;//*
		for(int i=0;i<edge;i++) scanf("%d%d%d",&E[i].a,&E[i].b,&E[i].w);//**
		
		sort(E,E+edge);//***
		
		for(int i=0; i<edge; i++ ){
			int u=parent(E[i].a);//****
			int v=parent(E[i].b);
			
			if(u!=v){
				TOTAL+=E[i].w;
				Prev[u]=v;//*****
			}
		}
		
		printf("Total Cost of MST %d\n",TOTAL);
	}
	return 0;
}

/*
 * Making each node it's own parent
 ** Input edges in the format "node1 node2 weight"
 *** Sorting them in the ascending order of weight
 **** Find the current parent of a and b
 ***** If the nodes of that edge is not connected yet, Connect them.
 */

if you don’t know Maximum possible number of nodes, then just use a vector(which is a bit slower) of type ‘edg’.

Related Problems
MST(spoj)
Dark Roads(UVa)
Audiophobia(UVa)
Connect the Campus(UVa)
Highways(UVa)



Maximum Spanning Tree
To get a maximum spanning tree, the procedure is almost same. The only difference is that, you got to sort members of E in the descending order of their weights.

Related Problems
Heavy Cargo(UVa)



Second Best Minimum Spanning Tree
There may be some other better procedure to find the second best MST, but this is the one I’ve used.
1. First form an MST of graph G, and mark the edges which formes the MST.
2. Then for each member edge of the MST, Form another MST without using that particular member.
3. Thus, u need to form n-1 (in case of n nodes) ‘another’ MSTs and consider the minimun among them.

Related Problems
Is There A Second Way Left ?(UVa)
ACM contest and Blackout(UVa)

Advertisements

Floyd Warshall

Standard

Add to DiggAdd to FaceBookAdd to Google BookmarkAdd to MySpaceAdd to Twitter

There are many notable algorithms to calculate the shortest path between vertices in a graph. Most are based on single source to a set of destination vertices. Examples of such famous algorithms include Dijkstra’s, Bellman-Ford and even Breadth First Search for weightless graphs. However, sometimes we wish to calculate the shortest paths between all pairs of vertices. An easy way to calculate this is to loop through each possible pair of vertices and run a Dijkstra through it. However, there exists a more efficient way to calculate this in n^3 time complexity.

Floyd-Warshall algorithm, a formula consisting of the core is very simple. A, B, C, I suppose we have 3 points. In this case, the shortest distance between A and C (distance (A, C), distance (A, B) + distance (B, C)) is up. Floyd-Warshall’ı need to apply to a table. The size of this table, depending on the number of points to be determined. We got one point, the table size N * N N

int[,] table = new int[5,5];

On the basis of the algorithm used for the function of the input for this table are the values at the maximum. The distance of each point of self-0, the distance to other points, we will begin by accepting the infinite.

int INFINITY = 9999999;
int N = 5;
for (int i = 0; i < N; i++)
  for(int j = 0; j < N; j++)
    table[i,j] = i == j ? 0 : INFINITY;

After this operation, the value of the table will be as follows.

table 1 2 3 4 5
1 0 INF INF INF INF
2 INF 0 INF INF INF
3 INF INF 0 INF INF
4 INF INF INF 0 INF
5 INF INF INF INF 0

Second, to keep the connection between the points and to build the matrix of contiguity for questioning. If you have an edge from one point to another entry in the table that would give a value. For example, point 3 and point 4, one side has 2 points. Therefore, our statements [2,3] = [2.4] = 1 = [3.2] = [4.2]. Grafımız no way we obtain for the diagonal matrix based on contiguity should be symmetrical. 1 to 4, because to have the edge in the 4 to 1, this also means there are also edges. Our example is a way you could tell it had graphs. After this, the final version of the table will be as follows:

table 1 2 3 4 5
1 0 INF INF 1 INF
2 INF 0 1 1 INF
3 INF 1 0 1 INF
4 1 1 1 0 1
5 INF INF INF 1 0

Floyd-Warshall can now apply the formula:

for( int k = 0; k &lt; N; k++)
for( int i = 0; i &lt; N; i++)
for( int j = 0; j &lt; N; j++)
table[i,j] = Math.Min(table[i,j], table[i,k] + table[k,j]);

That’s it. After this, our table will be as final.

table 1 2 3 4 5
1 0 2 2 1 2
2 2 0 1 1 2
3 2 1 0 1 2
4 1 1 1 0 1
5 2 2 2 1 0

Now using the table between the two points (a, b) can query the shortest distance. table [a, b] = table [b, a].

Quick Sort : Sorting array of Strings, Integers and Structs

Standard

Add to DiggAdd to FaceBookAdd to Google BookmarkAdd to MySpaceAdd to Twitter
qsort() takes four arguments:

void qsort(void *base, size_t nel, size_t width, int (*compar)(const void *, const void *));
■base — is a pointer to the beginning of data array
■nel — is a number of elements
■width — is a size of each element (in bytes)
■compar — is a callback function (pointer to function), which does comparison and returns positive or negative integer depending on result.

This example contains three separate functions sort_integers_example(), sort_cstrings_example() and sort_structs_example().

■sort_integers_example() uses int_cmp() as compar callback. Additional function print_int_array is used for printing integer array contents.
■sort_cstrings_example() uses cstring_cmp() as compar callback. Additional function print_cstring_array is used for printing string array contents.
■sort_structs_example() uses struct_cmp_by_price() and struct_cmp_by_product() as compar callbacks. Additional function print_struct_array is used for printing array of struct.

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
 
/* qsort int comparison function */
int int_cmp(const void *a, const void *b)
{
    const int *ia = (const int *)a; // casting pointer types
    const int *ib = (const int *)b;
    return *ia  - *ib; 
	/* integer comparison: returns negative if b > a 
	and positive if a > b */
}
 
/* integer array printing function */
void print_int_array(const int *array, size_t len)
{
    size_t i;
 
    for(i=0; i<len; i++)
        printf("%d | ", array[i]);
 
    putchar('\n');
}
 
/* sorting integers using qsort() example */
void sort_integers_example()
{
    int numbers[] = { 7, 3, 4, 1, -1, 23, 12, 43, 2, -4, 5 }; 
    size_t numbers_len = sizeof(numbers)/sizeof(int);
 
    puts("*** Integer sorting...");
 
    /* print original integer array */
    print_int_array(numbers, numbers_len);
 
    /* sort array using qsort functions */
    qsort(numbers, numbers_len, sizeof(int), int_cmp);
 
    /* print sorted integer array */
    print_int_array(numbers, numbers_len);
}
 
/* qsort C-string comparison function */
int cstring_cmp(const void *a, const void *b)
{
    const char **ia = (const char **)a;
    const char **ib = (const char **)b;
    return strcmp(*ia, *ib);
	/* strcmp functions works exactly as expected from
	comparison function */
}
 
/* C-string array printing function */
void print_cstring_array(char **array, size_t len)
{
    size_t i;
 
    for(i=0; i<len; i++)
        printf("%s | ", array[i]);
 
    putchar('\n');
}
 
/* sorting C-strings array using qsort() example */
void sort_cstrings_example()
{
    char *strings[] = { "Zorro", "Alex", "Celine", "Bill", "Forest", "Dexter" };
    size_t strings_len = sizeof(strings) / sizeof(char *);
 
    /** STRING */
    puts("*** String sorting...");
 
    /* print original string array */
    print_cstring_array(strings, strings_len);
 
    /* sort array using qsort functions */
    qsort(strings, strings_len, sizeof(char *), cstring_cmp);
 
    /* print sorted string array */
    print_cstring_array(strings, strings_len);
}
 
 
 
/* an example of struct */
struct st_ex { 
    char product[16];
    float price;
};
 
/* qsort struct comparision function (price float field) */
int struct_cmp_by_price(const void *a, const void *b)
{
    struct st_ex *ia = (struct st_ex *)a;
    struct st_ex *ib = (struct st_ex *)b;
    return (int)(100.f*ia->price - 100.f*ib->price);
	/* float comparison: returns negative if b > a 
	and positive if a > b. We multiplied result by 100.0
	to preserve decimal fraction */
 
} 
 
/* qsort struct comparision function (product C-string field) */
int struct_cmp_by_product(const void *a, const void *b)
{
    struct st_ex *ia = (struct st_ex *)a;
    struct st_ex *ib = (struct st_ex *)b;
    return strcmp(ia->product, ib->product);
	/* strcmp functions works exactly as expected from
	comparison function */ 
} 
 
/* Example struct array printing function */
void print_struct_array(struct st_ex *array, size_t len)
{
    size_t i;
 
    for(i=0; i<len; i++)
        printf("[ product: %s \t price: $%.2f ]\n", array[i].product, array[i].price);
 
    puts("--");
}
 
/* sorting structs using qsort() example */
void sort_structs_example(void)
{
    struct st_ex structs[] = {{"mp3 player", 299.0f}, {"plasma tv", 2200.0f}, 
                              {"notebook", 1300.0f}, {"smartphone", 499.99f}, 
                              {"dvd player", 150.0f}, {"matches", 0.2f }};
 
    size_t structs_len = sizeof(structs) / sizeof(struct st_ex);
 
    puts("*** Struct sorting (price)...");
 
    /* print original struct array */
    print_struct_array(structs, structs_len);
 
    /* sort array using qsort functions */
    qsort(structs, structs_len, sizeof(struct st_ex), struct_cmp_by_price);
 
    /* print sorted struct array */
    print_struct_array(structs, structs_len);
 
    puts("*** Struct sorting (product)...");
 
    /* resort using other comparision function */ 
    qsort(structs, structs_len, sizeof(struct st_ex), struct_cmp_by_product);    
 
    /* print sorted struct array */
    print_struct_array(structs, structs_len);
}
 
 
/* MAIN program (calls all other examples) */
int main()
{
    /* run all example functions */
    sort_integers_example();
    sort_cstrings_example();
    sort_structs_example();
    return 0;
}

Execution result:

*** Integer sorting…
7 | 3 | 4 | 1 | -1 | 23 | 12 | 43 | 2 | -4 | 5 |
-4 | -1 | 1 | 2 | 3 | 4 | 5 | 7 | 12 | 23 | 43 |
*** String sorting…
Zorro | Alex | Celine | Bill | Forest | Dexter |
Alex | Bill | Celine | Dexter | Forest | Zorro |
*** Struct sorting (price)…
[ product: mp3 player price: $299.00 ]
[ product: plasma tv price: $2200.00 ]
[ product: notebook price: $1300.00 ]
[ product: smartphone price: $499.99 ]
[ product: dvd player price: $150.00 ]
[ product: matches price: $0.20 ]

[ product: matches price: $0.20 ]
[ product: dvd player price: $150.00 ]
[ product: mp3 player price: $299.00 ]
[ product: smartphone price: $499.99 ]
[ product: notebook price: $1300.00 ]
[ product: plasma tv price: $2200.00 ]

*** Struct sorting (product)…
[ product: dvd player price: $150.00 ]
[ product: matches price: $0.20 ]
[ product: mp3 player price: $299.00 ]
[ product: notebook price: $1300.00 ]
[ product: plasma tv price: $2200.00 ]
[ product: smartphone price: $499.99 ]