Java Algorithms for Graph Theory

On this site you can find the source code of java classes that implement various data structures and algorithms presented at the courses A zip file with all these classes can be downloaded from here. It contains

List of the classes implemented so far:

[This list may grow]

Graphs: General-purpose

  1. IGraph: interface to work with arbitrary graphs. It is implemented by the classes Graph and Digraph.
  2. Graph: implementation an undirected graph of vertices named 0 through V –1, using adjacency-lists representation.
  3. Digraph: implementation a digraph of vertices named 0 through V –1, using adjacency-lists representation.
  4. Edge: representation of an edge as a pair of nodes.

Graphs: BFS/DFS/Applications

  1. CC: DFS-based implementation of an algorithm to detect (1) the connected components of an undirected graph and (2) cycles, if any.
  2. SCC: DFS-based implementation of an algorithm to detect the strongly connected components of a digraph. It implements the Kosaraju-Sharir algorithm.
  3. DCycle: DFS-based implementation of an algorithm to detect cycles in digraphs.
  4. DepthFirstOrder: Computation of the preorder, postorder and reverse-postorder orderings od nodes induced by a depth-first-search traversal of a graph.
  5. SSPaths: abstract class with API to traverse a graph starting from a source node. It is implemented by the classes DFS and BFS
  6. DFS: subclass of GraphSearch which implements depth-first search for graph traversal.
  7. BFS: subclass of GraphSearch which implements breadth-first search for graph traversal.
  8. Topologic: DFS-based implementation of an algorithm to compute a topological sort of a directed acyclic graph (DAG).

Weighted graphs: General-purpose

  1. WeighedEdge: representation of an outgoinf edge in a weighted graph.
  2. WeighedEdge: representation of an outgoinf edge in a weighted graph.
  3. IWeightedGraph: interface to work with arbitrary weighted graphs. It is implemented by the classes WeightedGraph and WeightedDigraph.
  4. WeightedGraph: implementation an undirected weighted graph of vertices named 0 through V –1, using adjacency-lists representation.
  5. WeightedDigraph: implementation a weighted digraph of vertices named 0 through V –1, using adjacency-lists representation.

Weighted graphs

APIs for single-source paths with minimum weight:
  1. WeightedSSPaths: abstract class with API to find the paths with minimum weights from a source node in a weighted graph. It is implemented by the classes BellmanFord and Dijkstra
  2. BellmanFord: implementation of Bellman-Ford algorithm
  3. Dijkstra: implementation of Dijkstra algorithm
APIs for all-pairs paths with minimum weight:

Note

Note: The java library algs4.jar contains classes named Graph, Digraph and Edge. They are different from the classes defined here.

Whenever a class is defined both here and in an external java library, you are advised to use the class defined here.