kruskal.c File Reference

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

#include "kruskal.h"

Go to the source code of this file.

Functions
static void	swap (Graph *graph, unsigned short swap_1, unsigned short swap_2)
static int	pivot_quicksort (Graph *graph, unsigned short first, unsigned short last)
static void	quick_sort (Graph *graph, unsigned short first, unsigned short last)
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 implementaion of the functions needed to compute the MST with Kruskal's algorithm.

Author

Lorenzo Sciandra

This file contains the implementation 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.c.

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

Definition at line 39 of file kruskal.c.

quick_sort()

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

static

Definition at line 110 of file kruskal.c.

swap()

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

static

Definition at line 18 of file kruskal.c.

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.