My Kruskal

//Handed by Oria Gruber to Dr. Leonid Kugel.
//Very important please read: When entering the adjacency matrix, since our graph is undirected
//I only scan the upper half to conserve memory. So if you have an adjacency matrix written down and you want to enter it
//Only enter the upper triangular half, diagonal included.
#include <stdio.h>
#include <conio.h>
#include <stdlib.h>
typedef struct edge //this represents an edge in a graph
{
	int vertex1,vertex2,weight;
}edge;
typedef struct parent_array_element //parent_array
{
	int parent,depth,root;
}parent_array_element;
int **get_adjacency_matrix(int* num_of_vertices,int *num_of_edges); //scan info from user
edge *get_edges_array(int **graph,int num_of_vertices,int num_of_edges); //put edges of graph into an array
void quick_sort(edge *a,int n); //to sort the edges
parent_array_element *get_parent_array(int num_of_vertices); //initialize parent_array
int find(parent_array_element *parent_array,int x); //returns the root of x's tree
void tree_union(parent_array_element *parent_array,int x,int y); //unifies the trees of x and y
void main()
{
	parent_array_element *parent_array;
	int **graph,num_of_vertices=0,num_of_edges=0,k=0,edge_counter_in_msp=0,i,sum=0;
	edge *edges_array;
	graph=get_adjacency_matrix(&num_of_vertices,&num_of_edges); //get the graph
	edges_array=get_edges_array(graph,num_of_vertices,num_of_edges); //get the edges
	parent_array=get_parent_array(num_of_vertices); //get parent array
	printf("The MSP is: \n");
	while(edge_counter_in_msp<num_of_vertices-1) //exactly num_of_vertices-1 edges in MSP.
	{
		if(find(parent_array,edges_array[k].vertex1+1)!=find(parent_array,edges_array[k].vertex2+edges_array[k].vertex1+1)) //x and y dont have the same root
		{ //so they dont create a cycle
			printf("(%d,%d) with weight %d\n",edges_array[k].vertex1+1,1+edges_array[k].vertex2+edges_array[k].vertex1,edges_array[k].weight);
			sum+=edges_array[k].weight;
			tree_union(parent_array,edges_array[k].vertex1+1,edges_array[k].vertex1+1+edges_array[k].vertex2); //make them same tree
			k++;
			edge_counter_in_msp++;
			continue;
		}
		else
			k++;
	}
	printf("\nSum of weights: %d",sum);
	getch();
}
int **get_adjacency_matrix(int* num_of_vertices,int *num_of_edges)
{
	int i,j,k,**graph,rows=0;
	printf("Enter the number of vertices in your connected undirected graph:");
	scanf("%d",num_of_vertices);
	printf("\nVery important: I assume there are no parallel edges\n");
	rows=*num_of_vertices;
	graph=(int**)malloc(rows*sizeof(int*));
	for(i=0;i<rows;i++)
		graph[i]=(int*)malloc((rows-i)*sizeof(int));
	printf("Please Enter the upper triangular cost-adjacency matrix\n");
	for(i=0;i<rows;i++)
	{
		for(k=0;k<i;k++)
			printf("  "); //blank spaces for readability.
		for(j=0;j<rows-i;j++)
		{
			scanf("%d",&(graph[i][j]));
			if((j!=0)&&(graph[i][j]>0))
				(*num_of_edges)++; //edge found. ignore loops.
		}
	}
	for(i=0;i<rows;i++) //remove loops
		graph[i][0]=0;
	return graph;
}
edge *get_edges_array(int **graph,int num_of_vertices,int num_of_edges)
{
	int i,j,k=0;
	edge *edges_array;
	edges_array=(edge*)malloc(num_of_edges*sizeof(edge));
	for(i=0;i<num_of_vertices;i++)
	{
		for(j=0;j<num_of_vertices-i;j++)
		{
			if(graph[i][j]!=0) //edge found
			{
				edges_array[k].weight=graph[i][j];
				edges_array[k].vertex1=i;
				edges_array[k].vertex2=j;
				k++;
			}
		}
	}  //edge_array is done. we now need to sort it.
	quick_sort(edges_array,num_of_edges);
	return edges_array;
}
void quick_sort (edge *a, int n) //taken from wikipedia, fixed it a little bit
{ //so it would work with edges rather than ints
    int i, j, p;
	edge t;
    if (n < 2)
        return;
    p = a[n / 2].weight;
    for (i = 0, j = n - 1;; i++, j--) {
        while (a[i].weight < p)
            i++;
        while (p < a[j].weight)
            j--;
        if (i >= j)
            break;
        t = a[i];
        a[i] = a[j];
        a[j] = t;
    }
    quick_sort(a, i);
    quick_sort(a + i, n - i);
}
parent_array_element *get_parent_array(int num_of_vertices)
{
	int i;
	parent_array_element *parent_array;
	parent_array=(parent_array_element*)malloc((num_of_vertices+1)*sizeof(parent_array_element));
	for(i=0;i<num_of_vertices+1;i++)
	{
		parent_array[i].parent=-1;
		parent_array[i].depth=0;
		parent_array[i].root=i;
	}
	return parent_array;
}
int find(parent_array_element *parent_array,int x)
{
	return parent_array[x].root;
}
void tree_union(parent_array_element *parent_array,int x,int y)
{
	if(parent_array[parent_array[x].root].depth > parent_array[parent_array[y].root].depth) //x tree deeper than y tree. add y to x
	{ //so trees remain at minimal depth
		while(parent_array[y].parent!=-1) //change roots of all nodes in y tree to root of x
		{
			parent_array[y].root=parent_array[x].root;
			y=parent_array[y].parent;
		}
		parent_array[y].parent=parent_array[x].root; //the parent of root of y is root of x
		parent_array[y].root=parent_array[x].root;
		return;
	}
	if(parent_array[parent_array[x].root].depth==parent_array[parent_array[y].root].depth) //same depth. add y to x (arbitrary) and change depth of x
	{
		while(parent_array[y].parent!=-1) //change roots of all nodes in y tree to root of x
		{
			parent_array[y].root=parent_array[x].root;
			y=parent_array[y].parent;
		} //y is now root of y tree
		parent_array[y].parent=parent_array[x].root; //the parent of root of y is root of x
		parent_array[y].root=parent_array[x].root;
		parent_array[parent_array[x].root].depth++;
		return;
	}
	if(parent_array[parent_array[x].root].depth < parent_array[parent_array[y].root].depth) //y tree deeper than x tree. add x to y
	{ //so trees remain at minimal depth
		while(parent_array[x].parent!=-1) //change roots of all nodes in y tree to root of x
		{
			parent_array[x].root=parent_array[y].root;
			x=parent_array[x].parent;
		}
		parent_array[x].parent=parent_array[y].root; //the parent of root of x is root of y
		parent_array[x].root=parent_array[y].root;
		return;
	}
}