Table of Contents
A graph models relationships between things. It consists of vertices – which represent entities – connected together by edges – which represent the relations between those entities.
For example, a social network maps people (vertices) and their friendships (edges):
Graphs allow us to solve interesting problems about connections and dependencies. This tutorial will explain the common types, properties, structures and algorithms you need to know about graphs in Java…and have some fun along the way!
Graph Basics
Formally, a graph is:
Graph = (Vertices, Edges)
Where:
- Vertices – Also called nodes. Represent entities/objects
- Edges – Represent relations between the vertices
For example, cities and routes between them:
Some key terms:
- Path: Sequence of edges between vertices
- Directed Graph: Edges go one way
- Undirected Graph: Edges go both ways
- Weighted Graph: Edges have numeric values
Next let‘s look at variants and properties…
Types of Graphs
There are a few common graph types and properties to know:
| Graph Type | Description | Example |
|---|---|---|
| Directed | Edges go one direction | Web links |
| Undirected | Edges go both directions | Friendships |
| Weighted | Edges have numeric values | Airline prices |
| Cyclic | Has cycles (arrows that start/end at same vertex) | Comment threads |
| Acyclic | No cycles allowed | Family trees |
| Connected | All vertices are connected somehow | Facebook friends |
These categories intersect – you can have a weighted, cyclic, directed graph and so on.
The structure impacts possible algorithms. Cycles allow feedback paths, while acyclic graphs have defined inputs/outputs useful for scheduling. Weights on edges enable computed shortest paths or minimum spanning trees.
First though, we need to represent graphs programmatically…
Graph Representations
There are two common ways to store graphs:
Adjacency Matrix
An adjacency matrix uses a VxV boolean matrix, where V is number of vertices. Each cell indicates if an edge exists between two vertices.
For example, a 5 vertex graph:
| A | B | C | D | E | |
|---|---|---|---|---|---|
| A | – | x | x | – | x |
| B | x | – | x | – | – |
| C | x | x | – | – | – |
| D | – | – | – | – | x |
| E | x | – | – | x | – |
- Simple, intuitive
- Fast edge lookup O(1)
- But uses more memory (V^2 space)
Adjacency List
The adjacency list format has each vertex store a list of its adjacent vertices.
- Saves space on sparse graphs
- Edge check is slower O(E)
- Faster to iterate edges
Tradeoffs depend on graph density and operations used.
Up next, graph processing in Java!
Graph Implementation in Java
We‘ll implement a directed weighted graph using adjacency lists in Java:
class Graph {
private Map<Integer, List<Edge>> adjList = new HashMap<>();
static class Edge {
int dest;
int weight;
// Constructor
Edge(int dest, int weight) {
this.dest = dest;
this.weight = weight;
}
}
public void addEdge(int src, int dest, int weight) {
// Add edge to source vertex adjacency list
adjList.computeIfAbsent(src, x-> new ArrayList());
adjList.get(src).add(new Edge(dest, weight));
}
}This maps vertices to adjacency lists containing destination vertices and weights.
We can add edges with:
Graph g = new Graph();
g.addEdge(0, 1, 5); // 0->1 edge with weight 5And there we have a graph structure in Java!
Now what can we do with graphs? Turns out, a lot!
Graph Algorithms
Some key things we can compute on graphs include:
- Pathfinding – Find paths between two vertices
- Shortest Paths – Optimize routes by edge weights
- Spanning Trees – Define structure backbone
- Connectivity – Check if all connected
- Cycles & Dependencies – Detect feedback loops
This involves graph traversal – systematically visiting vertices of a graph.
Popular ways to traverse graphs:
Depth First Search
- Start at one vertex and explores as far as possible down each branch before backtracking
- Uses less memory, explores rapidly
- Useful for checking connectivity
DFS in Java:
void dfs(int node, Set<Integer> visited) {
visited.add(node);
// Recurse on adjacent unvisited vertices
for (Edge e : adjList.get(node)) {
if (!visited.contains(e.dest)) {
dfs(e.dest, visited);
}
}
}Breadth First Search
- Explores all neighbors first before going deeper
- Finds shortest paths in unweighted graphs
- Uses more memory with vertex queue
And breadth-first in Java:
void bfs(int root) {
Set<Integer> visited = new HashSet();
Queue<Integer> queue = new LinkedList();
visited.add(root);
queue.add(root);
while (!queue.isEmpty()) {
int node = queue.poll();
for (Edge e : adjList.get(node)) {
if (!visited.contains(e.dest)) {
visited.add(e.dest);
queue.add(e.dest);
}
}
}
}Choosing an algorithm depends on the problem and graph traits.
Now let‘s look at real-world uses!
Applications of Graphs
Graphs have tons of practical applications:
- Networks: Model road systems, computer networks, infrastructure etc. Optimize traffic flows.
- Recommendations: Build suggestion graphs based on similarity/preferences
- Shortest Paths: Find fastest routes in mapping apps like Google Maps
- Scheduling: Resolve task dependencies and order using directed acyclic graphs
- Machine Learning: Probabilistic models like Bayes Nets or Markov Chains
- Databases: Store non-tabular linked data with graph databases
And many more uses…
The connections and relations modeled by graphs are everywhere!
Key Takeaways
We covered a lot of ground working with graphs in Java! To recap:
- Graphs connect vertices via edges
- Directed/weighted graphs add constraints
- Adjacency lists efficiently store relations
- Traversals like DFS & BFS visit vertices
- Applications span networks, data and more
So in summary:
- Graphs flexibly represent connections
- Structure impacts algorithms
- Implementations optimize space/time tradeoffs
- Useful both abstractly and practically!
I hope you feel better equipped to leverage graphs for modeling domains and tackling problems. Reach out if you have any other questions!