Yep. Fun stuff
Well, I mean...If you think about it, linked lists and trees are all graphs, with special properties
IMPORTANT: If you are not really familiar with graphs, please refer to Chapter 10 of Discrete Mathematics And Its Applications 7th Edition by Kenneth H. Rosen
The content below will mainly talk about implementation, instead of theory. Make sure you are familiar with the theory part before moving on!
Note that your implementations will be different and this is just an example
When implementing a graph, first think about what parts does a graph have.
Well, a graph has vertices and edges (either directed or undirected), thus you would need a Vertex class and an optional Edge class.
Your Vertex, as you have seen in Dijkstra's Algorithm, would probably need to keep track of:
- If the vertex has been visited (if it is known)
- The distance from the vertex to the starting point/ending point (based on implementation) of your path
- The next node in the shortest path
So in a simple, mathematical graph with undirected and unweighted edges, you probably would have:
public class Vertex{
final int id;
boolean known; //If I have visited this vertex before
double distance; //To store the distance for comparison in Dijkstra
Vertex next; //For storing shortest path
//Constructor, probably taking an int as your parameter
}You may choose to have an Edge class, but there wouldn't too much to keep track of
Oh, and it may also be a good idea to make your Vertex implement Comparable<Vertex> so you can compare them and sort a Collection of them, perhaps based on distance.
In real life application, say for example, storing a map of streets and roads, with weighted and directed edges, you may have something like:
public class Vertex implements Comparable<Vertex>{
public final String ID;
public double distance, longitude, latitude;
public boolean known;
public Vertex path;
//Constructor, probably taking ID, longitude and latitude as parameters
}In this case, it will probably be a good idea to have an Edge class to keep track of starting and ending vertices, its weight, and maybe its ID (Well, streets and roads have their IDs). It will also be easier if you want to draw out the map. So, something like this:
public class Edge implements Comparable<Edge>{
public final String ID;
public double weight;
public Vertex v, w;
//Constructor
}Any picture of graphs you see are just artistic impressions of graphs, and you can draw them however you want. The vertices, the edges and their relationships are what defines a graph.
Prof. Hermann (MTH 150, Fall 2016)
If you are familiar with the theory, you should remember two representations of graphs. Adjacency Matrix and Adjacency List
Example: Fig. 10.3.1 from Rosen Discrete Math
For a graph that looks like this:
You get an adjaceny matrix Like:
| 0 1 1 0 1 |
| 1 0 0 0 0 |
| 1 0 0 1 1 |
| 0 0 1 0 1 |
| 1 0 1 1 0 |
And an adjaceny list Like:
And in terms of java, they will correspond to boolean[][] and HashMap<[Some Key/ID], List<Vertex>>
Your MTH 150 professor probably told you those representations are the same. In CSC 172, they are not.
Adjacency matrix is instant at telling you if two vertices are connected or not, but takes a lot of space (space complexity is O(n^2)). It is a good idea when you have a lot of space to spare, and your graphs looks more or less complete
Completeness? You ask.
A complete graph has all the vertices connected to each other, and thus, apart from the diagonal (no vertex connects to ifself), all entries in the matrix are true.
For a graph that is almost complete, like the one below, not many entries are false.
Rosen Discrete Math Exercise 10.3 Q.1 & 5
Now, for a linked list as a graph:
a - b - c - d - e
Its adjacency matrix looks like:
| 0 1 0 0 0 |
| 1 0 1 0 0 |
| 0 1 0 1 0 |
| 0 0 1 0 1 |
| 0 0 0 1 0 |
This is called a sparse matrix as not many entries are actually true.
Thus for street mapping, it is probably not a good idea to store eveything in a 2D array. Facing with millions of vertices that are not really well connected, you will soon run out of memory, and if not, most of it will be 0 anyways.
Thus, in real life scenarios, you are probably better off using an adjacency list. With roadmaps, as one vertex is most likely connected to only two other vertices, you don't have to worry too much about linear time access.
We all love Dijkstra's Algorithm. It has a log in its Big-O!
Okay, for those who read this far, here is the pseudocode for the amazing algorithm:
Data Structures and Algorithm Analysis in Java 3rd Edition By Mark Allen Weiss
Sifan Ye