The Graph Abstract Data Type
This project was to create two implementation of a Directed Graph, an adjacency list, and
an adjacency matrix. I collaborated with two other members using Git and we wrote this in Java.
A test-driven development process was followed, and we used JUnit as our testing library.
After designing these datatypes, we wrote some basic algorithms to work on these graphs.
| Algorithm | Function |
|---|---|
| Breadth First Search | Starts a graph traversal at a node, exploring all neighbouring nodes before moving to the next depth level. |
| Depth First Search | Starts a graph traversal at a node, exploring one path to its deepest depth level, before moving to a neighbor node. |
| Common Upstream Vertices | Given a graph and two vertices, return a list of vertices which have an edge to both vertices. |
| Common Downstream Vertices | Given a graph and two vertices, return a list of vertices which both vertices have an edge to. |
| Shortest Distance | Given a graph and two vertices, returns the minimum number of edges to get from one vertex to the other. |
| Graph Diameter | Given a graph, returns the maximum distance among all the distances between every pair of vertices. |