kruskal.h File Reference

The declaration of the functions needed to compute the MST with Kruskal's algorithm. More...

#include "../data_structures/mst.h"

Go to the source code of this file.

Functions
static void	swap (Graph *graph, unsigned short swap_1, unsigned short swap_2)
	Swaps two edges in the list of edges in the Graph.
static int	pivot_quicksort (Graph *graph, unsigned short first, unsigned short last)
	The core of the quick sort algorithm.
static void	quick_sort (Graph *graph, unsigned short first, unsigned short last)
	The quick sort algorithm O(n log n).
void	wrap_quick_sort (Graph *graph)
	The wrapper of the quick sort algorithm.
void	kruskal (Graph *graph, MST *mst)
	The Kruskal algorithm to find the Minimum Spanning Tree O(|E| log |V|)

Detailed Description

The declaration of the functions needed to compute the MST with Kruskal's algorithm.

Author

Lorenzo Sciandra

This file contains the declaration of the Kruskal algorithm to find the Minimum Spanning Tree.

Version

1.0.0 @data 2024-05-1

Copyright

Copyright (c) 2024, license MIT

Repo: https://github.com/LorenzoSciandra/GraphConvolutionalBranchandBound

Definition in file kruskal.h.

Function Documentation

kruskal()

void kruskal	(	Graph *	graph,
		MST *	mst
	)

The Kruskal algorithm to find the Minimum Spanning Tree O(|E| log |V|)

This is the classic Kruskal algorithm that uses Merge-Find Sets.

Parameters

graph	The Graph from which we want to find the MST.
mst	The Minimum Spanning Tree.

Definition at line 131 of file kruskal.c.

pivot_quicksort()

static int pivot_quicksort ( Graph *  graph, unsigned short  first, unsigned short  last  )

static

The core of the quick sort algorithm.

This function find the pivot position to recursively call the quick sort algorithm. While doing this all the edges with weight less than the pivot are moved to the left of the pivot and to the right otherwise.

Parameters

graph	The Graph to which we want to sort the edges.
first	The index of the first Edge to consider in the list of edges.
last	The index of the last Edge to consider in the list of edges.

Returns

the index of the pivot.

quick_sort()

static void quick_sort ( Graph *  graph, unsigned short  first, unsigned short  last  )

static

The quick sort algorithm O(n log n).

It is used to sort the edges of the Graph in ascending order in O(n log n). It is recursive.

Parameters

graph	The Graph to which we want to sort the edges.
first	The index of the first Edge to consider in the list of edges.
last	The index of the last Edge to consider in the list of edges.

swap()

static void swap ( Graph *  graph, unsigned short  swap_1, unsigned short  swap_2  )

static

Swaps two edges in the list of edges in the Graph.

This function is used to swap two edges in the list of edges in the Graph.

Parameters

graph	The Graph to which the edges belong.
swap_1	The index of the first Edge to swap.
swap_2	The index of the second Edge to swap.

wrap_quick_sort()

void wrap_quick_sort

(

Graph *

graph

)

The wrapper of the quick sort algorithm.

If the Graph is not sorted, this function calls the quick sort algorithm to sort the edges of the Graph.

Parameters

graph

The Graph to which we want to sort the edges.

Definition at line 123 of file kruskal.c.