Graph Algorithms
This page contains implementations of graph algorithms. [Download]
Related:
- [Directed Graphs]
- [Heaps]
- [Timing Library] (used by some test programs)
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
- description
Tarjan's Algorithm (Strongly Connected Components)
- C source files: sc.c sc.h
- example program: sc_test.c
- picture
- description
Dijkstra's Algorithm
Two implementations are given which differ by the data structure used for the frontier set.
Implemented with a one-dimentional array:
- C program source file: da_simple.c
- picture
- description
Floyd's Algorithm
- C program source file: floyd.c
Minimal Spanning Tree Algorithms
Currently only Prim's minimal spanning tree algorithm is implemented.
- C source files: mst.c mst.h
- example program: mst_test.c
Maximum Flow Algorithms
The Ford and Fulkerson, Dinic, MPM, and Karzonov maximum flow algorithms are implemented.
- C source files: mf.c mf.h
- example program: mf_test.c
- picture
- description
- CPU time measurements
Last modified: Wednesday, 08-Dec-2004 10:37:42 NZDT
