Like this article? We recommend
Like this article? We recommend
Like this article? We recommend
A Simple Application of Graph Theory
A graph is simply a set of vertices (or endpoints) and a set of edges that connect some or all of the vertices.
Figure 1 illustrates a basic graph.
)
Figure 1 A graph structure
The vertices in Figure 1 are the numbered circles, and the edges are the lines joining the circles. A vertex can represent any entity that you want to model; for example, a vertex might represent a geographical location, and the edges might represent routes between those locations. Vertices that are joined are said to have an adjacency with each other.
So how does all this relate to the real world?
Imagine that the graph in Figure 1 represents geographical locations or nodes in a network. Further, let’s assign each edge a cost—the higher the cost the more expensive the route.
I’ve added some costs (or weights) in Figure 2.
)
Figure 2 A graph with weighted edges
Now, to get the best route from one node to another, you add up the weights of the edges traversed. The journey with the lowest overall weight is the cheapest; to get from 0 to 4 via vertices 5 and 3 incurs a cost of 3 + 5 + 1 or 9.
To get from 0 to 4 via vertices 1 and 6 incurs a cost of 2 + 4 + 6, or 12. So we can say that to get from 0 to 4, the cheapest route is 0-5-3-4.
Clearly, this is a very small example, and you can imagine the problems faced using graphs to represent very large data sets: traversal becomes expensive; storage requirements shoot up, and so on. But, you get the idea.
Once you start to understand these simple concepts you’re beginning to get the basics of graphs. Bear in mind that there is an enormous amount of theory behind this area, but it is possible to gain an overview.
Moving up the value chain is all about being able to tackle complex problems and subjects (see references [3] and [4] for more information).
Let’s now look at some simple Java to help us to program some concrete examples.