4.2.4.1 - Graphs and adjacency representations (Java)
Model relationships with graphs and implement adjacency matrices and lists in Java, choosing a representation suited to the operations and density of the graph.
Java route status: incomplete: runnable support pending. The code tasks are native written practice.
Nodes, edges and weights
A graph represents relationships that need not form a sequence or a simple hierarchy.
Graph
A set of vertices, also called nodes, together with edges, also called arcs, that join pairs of vertices.
A road network can use junctions as vertices and roads as edges. A social network uses accounts and relationships; a dependency graph uses tasks and required ordering. An undirected graph has edges usable in both directions, while a directed graph has ordered relationships: A to B does not imply B to A. A weighted graph attaches a value such as distance, time or cost to each edge. A weight is not necessarily a geometric length on the drawing.
Our three-node directed weighted example has edges A→B of weight 4, A→C of weight 2, B→C of weight 1 and C→A of weight 3. There is no B→A edge. The route A→B→C has two edges and total weight 5, while the direct A→C edge has weight 2. Graph representation records these possibilities; finding a shortest path is a separate algorithm.
[DIAGRAM: asset_slug: directed_weighted_graph; description: Directed weighted graph with A to B weight 4, A to C weight 2, B to C weight 1 and C to A weight 3.]
Adjacency matrices
An adjacency matrix uses the row as the source vertex and the column as the destination vertex.
Number A, B and C as 0, 1 and 2. Here all edge weights are positive and zero means no edge; the meaning of zero is part of this representation's contract.
| From / to | A | B | C |
|---|---|---|---|
| A | 0 | 4 | 2 |
| B | 0 | 0 | 1 |
| C | 3 | 0 | 0 |
int[][] weights = {
{0, 4, 2},
{0, 0, 1},
{3, 0, 0}
};
boolean direct = weights[0][1] != 0; // A to B exists
int weight = weights[0][1]; // 4
For an undirected graph, store an edge in both symmetric positions. Adding A—B with weight 4 writes 4 at [0][1] and [1][0]; removing it sets both to zero. A directed graph need not be symmetric. A matrix for vertices allocates entries, even when few edges exist, and gives immediate lookup of a specified pair.
An unweighted graph can use a Boolean matrix. If zero-weight edges are allowed, zero cannot also unambiguously mean absence: use a separate presence matrix or a documented sentinel. Reading a matrix without its convention can reverse direction or invent/remove an edge.
Continue this lesson.
You’re previewing NovaLearn without an account. Create a free account to read the rest.
Create free account