Graph Algorithms

This page contains implementations of graph algorithms.

Related:

[Directed Graphs]
[Heaps]
[Timing Library] (used by some test programs)

Depth First Search and Breadth First Search

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

Implemented with a heap:

C source files: da.c da.h
example program: da_test.c

Floyd's Algorithm

C program source file: floyd.c

Minimal Spanning Tree Algorithms

Implementations of Prim's and Kruskal's minimal spanning tree algorithms.

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