Graphs/Java/Adjacency Map Lite

Note: this implementation is more practical for a lightweight problem, such as a programming competition or coding challenge.

The Classes

A lightweight implementation of the adjacency map still requires three classes, but can skimp on infrastructure. The three classes are:

• Graph
• Vertex
• Edge

Class Implementations

Following is a list of methods and fields that each of the above classes should implement

Graph class:

• Constructor: initializes list of vertices, list of edges
• Add vertex method (identified by integers)
• Add edge method (takes two integers)
• (Optional) Depth first search (or any other methods/algorithms required specifically by the problem)

Vertex class:

• Map of Vertex objects to Edge objects, to store connecting edges
• Integer (element/identifier)
• Method: get neighbors
• Method: get element

Edge class:

• List of Vertex objects
• (Optional) int array (element/identifier)
• Constructor: two vertices, set as endpoints
• Method: get endpoints
• Method: get element

Static Classes

To keep things simple, bundle everything as a single single class, and make the Graph, Vertex, and Edge classes static. The main objective here is implementing the algorithm and data structure, rather than coordinating permissions and access.

Exceptions

See Java/Exceptions

Easiest way to do this is to raise new IllegalArgumentException("Error message here")

Algorithms

// u is an empty dictionary
def dfs_connected(g):
    forest is empty dictionary
    for each vertex u in graph:
        if u not in forest:
            forest[u] = None
            do_dfs(g, u, forest)
    return forest

// complementary method: do depth first search
def do_dfs(g, u, discovered):
    for e in g.incident_edges(u):
        if v not in discovered:
            discovered[v] = e
            do_dfs(g, v, discovered)