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.
Depth First Search and Breadth First Search
- C source files: dfs_bfs.c dfs_bfs.h
- Example program: dfs_bfs_test.c
- DFS picture
- BFS picture
Tarjan's Algorithm (Strongly Connected Components)
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:
- C program source file: floyd.c
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>.
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.
- Example program: [Dijkstra's Algorithm]
- Test data - using heaps in Dijkstra's algorithm: 2-3 heap test data, trinomial heap test data
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.
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:
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
Standard 2-3 tree:
Modified 2-3 tree, supporting delete_min() in O(1) worst case time:
Digital Search Tree
Radix Search Trie
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.
Various heaps for use in Dijkstra's algorithm are provided. These are all derived from a common base class.
- Heap base class: heap.h
The individual heap implementations are given below:
- Fibonacci heap: fheap.cpp fheap.h
- 2-3 heap: heap23.cpp heap23.h
- trinomial heap: triheap.cpp triheap.h
- extended trinomial heap (with O(1) worst-case time for decrease-key operations): triheap_ext.cpp triheap_ext.h
- radix heap: radixheap.cpp radixheap.h, (description)
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.
- Graph algorithms: graphalg.tar.gz
- Sorting algorithms: sorting.tar.gz
- Searching algorithms: searching.tar.gz
- Graphs: graphs.tar.gz - source files for graphs used by algorithms in this repository.
- Heaps: heaps.tar.gz
- Dictionaries: dict.tar.gz
- Timing library: timing.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.