Algorithm and Data Structure Repository

Developed for educational purposes, this repository provides example implementations of algorithms and data structures. Various algorithms and data structures implemented in C are given. The downloads below provide a package containing all of the main algorithm repository's C source files.

A separate section of this repository specialises in shortest path algorithms and priority queues implemented in C++.

All algorithms and source files provided by this repository are subject to the disclaimer1.

Main Repository

Please note that the timing library can be used to test algorithims (C Source Files: timing.c timing.h)

Algorithms

Depth First Search and Breadth First Search

Tarjan's Algorithm (Strongly Connected Components)

Dijkstra's Algorithm

Two implementations are given which differ by the data structure used for the frontier set.

Implemented with a one-dimentional array:

Implemented with a heap:

Floyd's Algorithm

Minimal Spanning Tree Algorithms

Currently only Prim's minimal spanning tree algorithm is implemented.

Maximum Flow Algorithms

The Ford and Fulkerson, Dinic, MPM, and Karzonov maximum flow algorithms are implemented.

Some CPU time data is available for a performance comparison of functions in sort.c, and the qsort() function provided by the C header <stdlib.h>.

Quicksort

Mergesort

Radix Sort

Heap Sort

 

Currently only binary search is implemented.

Convex Hulls

An implementation of Graham's scan for simple 2-dimensional convex hulls.

Data Structures

These C source files are used by the graph algorithms in this repository.

Common Files

A description of all the heaps implemented is provided.

The header file heap_info.h defines a common structure type for heaps so that they can be used interchangeably. A program which uses this common structure type is then able to use different heaps interchangeably. The heap implementation of Dijkstra's algorithm is an example of this.

Binary Heap

Fibonacci Heap

2-3 Heap

The trees in a 2-3 heap can be viewed in two different ways, and this leads to two different 2-3 heap implementations.

Implemented using linked lists of child nodes:

Implemented using linked lists of child node-pairs:

In the node-pair implementation the linked list of child nodes is defined differently. Nodes have an extra pointer which points to an optional partner node with which the node forms a node-pair. Each node has a boolean field which identifies whether it is the "extra" node a node-pair.

Trinomial heap

The extended trinomial heap implementation supports O(1) worst case time for decrease_key:

The basic trinomial heap implementation supports O(1) amortized time for decrease_key:

Common Files

The header file dict_info.h defines a common structure type that each dictionary can provide. A program which uses this common structure type is then able to use different dictionaries interchangeably, as done by the supplied example program.

Binary Search Tree

AVL Tree

2-3 Tree

Standard 2-3 tree:

Modified 2-3 tree, supporting delete_min() in O(1) worst case time:

Red-Black Tree

Hash Table

Skip List

Digital Search Tree

Radix Search Trie

Specialised Repositories

Shortest Path Algorithms and Priority Queues in C++

This secondary repository contains C++ implementations of shortest path algorithms and the priority queues that they use. A standard implementation of Dijkstra's algorithm is provided which is able to use the various priority queues interchangeably.

A standard implementation of directed graphs is used by Dijkstra's algorithm.

Various heaps for use in Dijkstra's algorithm are provided. These are all derived from a common base class.

The individual heap implementations are given below:

Since the radix heap works specifically with Dijkstra's algorithm, it is described separately from the other heaps. A description of other heaps can be found in the heaps section of the main algorithm repository.

Dijkstra's algorithm was implemented with the ability to use any of the above heaps.

Example Usage (Experiment Code)

The following example program demonstrates how to use the different heap implementations with Dijkstra's algorithm.

In addition, the following experiment code can be used to compare the different instances of Dijkstra's algorithm on different graphs.

Algorithm Repository downloads

Files may only be downloaded in acceptance with the disclaimer1.

The entire algorithm repository source code and makefiles can be downloaded as a single package containing the directory structure expected by the source files. Alternatively, individual parts of the algorithm repository are available as separate packages. Individual C source files are viewable from the algorithm repository web pages. A README file is available, which gives an outline of source files in this repository and the directory structure used.

  • alg.tar.gz contains all of the algorithm repository source code and makefiles.

Algorithms

Data Structures

Related

  • Shortest Path Algorithms and Priority Queues in C++: spalgs.tar.gz

1Discalimer: You agree that this repository contains non-commercially developed algorithms and that the source code and related files may contain errors. In no event will the provider of this repository be held responsible for any damages resulting from the source code and related files supplied by this repository or the use thereof. You acknowledge that you use all source code and related files supplied by this repository at you own risk.