Hi ! In this post I will share with you 6 Java Graph algorithms I had to code for a discrete mathematics final exam in college. The algorithms were presented in an Applet I built and which I also include for you to play around with them.
Before presenting the algorithms I will give a general background about Graph Theory.
What is a graph?
(from Wikipedia) A graph is an abstract representation of a set of objects where some pairs of the objects are connected by links. The interconnected objects are represented by mathematical abstractions called vertices, and the links that connect some pairs of vertices are called edges.
Type of graphs
There are many, many, many type graphs, most of them associated to maths properties. For the purpose of the API I developed for the algorithms implementations you should know the following:
In terms of representation, a graph can be represented either by an adjacency matrix or an adjacency list. In an adjacency matrix, a true/false (x,y) cell represents if exists a link between node “x” and node “y”. This is the one which I used because of its better performance. In an adjacency list, each node has an own list for storing referenced lists.
Continue Reading →