Graphs, and How to Store Them

Graphs vs. trees

You already know one kind of graph: a tree is a graph with special rules (one root, every other node has exactly one parent, no cycles). A general graph drops those rules:

	Tree	Graph
Root?	yes, one	no root
Parents?	every node except the root has exactly one	no parent/child idea; a vertex can connect to any number of others
Cycles?	never	allowed (you can go around and come back)
Connected?	always	not always; some parts can be separate

So: every tree is a graph, but not every graph is a tree.

Directed or undirected?

Graphs can be described in two ways, depending on whether edges have a direction:

In a directed graph, degree splits in two. The out-degree counts arrows leaving a vertex; the in-degree counts arrows coming in. The two pictures below show both counts for vertex A in the directed graph above:

Tip: look at the arrowhead. If the arrowhead touches the vertex, the arrow counts toward its in-degree; if the tail starts there, it counts toward its out-degree.

Weighted or unweighted?

In a weighted graph, each edge carries a number called its weight. It can mean distance, cost, or time.

Here the weights are travel times in minutes (made-up numbers). From A to C, the path A → D → B → C takes 4 + 5 + 12 = 21 minutes, but A → B → C takes 7 + 12 = 19.

An unweighted graph has no numbers: every edge counts the same.

Loops

C has a loop: an edge that leaves C and comes right back to C. Think of a web page that links to itself (like a "back to top" link).

First: a 2D array

In the Arrays lesson, an array was one row of slots. Some data needs a grid: rows and columns. Think of the seat plan in your classroom. To point to one seat, you say two numbers: its row and its column.

row ↓ / col →	0	1	2	3
0	0	0	0	0
1	0	0	7	0
2	0	0	0	0

seats[1][2] is row 1, column 2 (the orange slot). Every other slot still holds 0.

int[][] seats = new int[3][4];   // 3 rows, 4 columns, all 0
seats[1][2] = 7;                 // row 1, column 2
System.out.println(seats[1][2]); // 7
System.out.println(seats.length);    // 3 (rows)
System.out.println(seats[0].length); // 4 (columns)

Here is how to read each line aloud:

An adjacency matrix is exactly this kind of grid. Its rows are the vertices, its columns are the same vertices again, and each slot answers one question: is there an edge from this row's vertex to this column's vertex?

Three things to notice

The matrix shows you the type of graph. Look for these three things:

1. Undirected = mirror image. Every undirected edge A–B is stored twice, as [A][B] and [B][A]. So the matrix matches itself across the diagonal (it is symmetric).
2. The diagonal means loops. Cell [C][C] is an edge from C to itself. If the diagonal is all 0, there are no loops.
3. Weights replace the 1s. In a weighted graph, the cell stores the weight instead of 1. In this course, 0 still means "no edge". Some books write ∞ or leave the cell blank instead, because a real edge could have weight 0.

Adjacency matrix: a 2D array

public class MatrixGraph {
  static char[] names = {'A', 'B', 'C', 'D'};
  static int n = names.length;
  static int[][] adj = new int[n][n];   // all 0 at first

  // undirected edge: set both cells
  static void addEdge(int from, int to) {
    adj[from][to] = 1;
    adj[to][from] = 1;   // remove this line for directed
  }

  public static void main(String[] args) {
    addEdge(0, 1);   // A - B
    addEdge(0, 3);   // A - D
    addEdge(1, 2);   // B - C
    addEdge(1, 3);   // B - D

    // neighbors of B (index 1): scan row 1
    for (int j = 0; j < n; j++) {
      if (adj[1][j] == 1) {
        System.out.print(names[j] + " ");
      }
    }
    // prints: A C D
  }
}

▶ Try it in the Programiz online compiler: tap Copy, paste it there, change public class MatrixGraph to public class Main (Programiz saves your code as Main.java, and Java needs the file name and the public class name to match), then press Run.

Here is how to read the new lines aloud:

Adjacency list: a list of lists

ArrayList is Java's built-in resizable array: you can keep calling add and it grows. Here, we keep one ArrayList per vertex. Each inner list plays the role of the linked lists in our pictures.

import java.util.ArrayList;

public class ListGraph {
  static char[] names = {'A', 'B', 'C', 'D'};
  static int n = names.length;
  static ArrayList<ArrayList<Integer>> list = new ArrayList<>();

  // undirected edge: add each to the other's list
  static void addEdge(int from, int to) {
    list.get(from).add(to);
    list.get(to).add(from);   // remove for directed
  }

  public static void main(String[] args) {
    for (int i = 0; i < n; i++) {
      list.add(new ArrayList<>());   // one empty list each
    }
    addEdge(0, 1);   // A - B
    addEdge(0, 3);   // A - D
    addEdge(1, 2);   // B - C
    addEdge(1, 3);   // B - D

    // neighbors of B: walk B's list only
    for (int j : list.get(1)) {
      System.out.print(names[j] + " ");
    }
    // prints: A C D
  }
}

▶ Try it in the Programiz online compiler: tap Copy, paste it there, change public class ListGraph to public class Main (Programiz saves your code as Main.java, and Java needs the file name and the public class name to match), then press Run.

Here is how to read the new lines aloud:

Why Integer and not int? The types inside < > must be classes. Integer is the class version of int, and Java converts between the two for you, so add(to) works with a plain int, and int j in the for-each loop gets a plain int back.

 1import java.util.ArrayList;
 2
 3public class Main {
 4  static char[] names = {'A', 'B', 'C', 'D', 'E'};
 5  static int n = names.length;
 6
 7  // Builds the adjacency list of a graph from its matrix.
 8  static ArrayList<ArrayList<Integer>> toList(int[][] adj) {
 9    ArrayList<ArrayList<Integer>> list = new ArrayList<>();
10    for (int i = 0; i < n; i++) {
11      list.add(new ArrayList<>());   // one empty list each
12    }
13    // YOUR CODE:
14    // 1. Visit every cell: row i (from 0 to n - 1),
15    //    and in each row, column j (from 0 to n - 1).
16    // 2. If adj[i][j] is 1, there is an edge from i to j:
17    //    add j to vertex i's list.
18
19    return list;
20  }
21
22  // Given: prints each vertex's list, like "A: C D".
23  static void printList(ArrayList<ArrayList<Integer>> list) {
24    for (int i = 0; i < n; i++) {
25      System.out.print(names[i] + ":");
26      for (int j : list.get(i)) {
27        System.out.print(" " + names[j]);
28      }
29      System.out.println();
30    }
31  }
32
33  public static void main(String[] args) {
34    // Test 1: the directed graph from Reading practice
35    int[][] directed = {
36      {0, 0, 1, 1, 0},   // A -> C, A -> D
37      {1, 0, 0, 0, 0},   // B -> A
38      {0, 1, 0, 0, 0},   // C -> B
39      {0, 1, 0, 0, 1},   // D -> B, D -> E
40      {0, 0, 0, 0, 0}    // E points nowhere
41    };
42    printList(toList(directed));
43    // expected:
44    // A: C D
45    // B: A
46    // C: B
47    // D: B E
48    // E:
49
50    // Test 2: undirected A-B, A-D, B-C, B-D (E has no edges)
51    int[][] undirected = {
52      {0, 1, 0, 1, 0},
53      {1, 0, 1, 1, 0},
54      {0, 1, 0, 0, 0},
55      {1, 1, 0, 0, 0},
56      {0, 0, 0, 0, 0}
57    };
58    printList(toList(undirected));
59    // expected:
60    // A: B D
61    // B: A C D
62    // C: B
63    // D: A B
64    // E:
65  }
66}

 1static ArrayList<ArrayList<Integer>> toList(int[][] adj) {
 2  ArrayList<ArrayList<Integer>> list = new ArrayList<>();
 3  for (int i = 0; i < n; i++) {
 4    list.add(new ArrayList<>());   // one empty list each
 5  }
 6  for (int i = 0; i < n; i++) {
 7    for (int j = 0; j < n; j++) {
 8      if (adj[i][j] == 1) {
 9        list.get(i).add(j);   // edge i -> j
10      }
11    }
12  }
13  return list;
14}

Real-life application: a mini map app

Extra topic. This goes a step beyond the lesson and is not in the self-check. Read it if you are curious how map apps find a route.

This program finds the fastest route from A to C in the travel-time graph . The method is called Dijkstra's algorithm (say "DIKE-struh"), named after the Dutch computer scientist Edsger Dijkstra, who came up with it in 1956. It follows four steps, the same ones you would do by hand:

1. Start at A with a time of 0. Every other place is "not reached yet."
2. Each round, pick the unfinished place with the smallest time so far. Its time is now final.
3. From that place, check each road. If going through it is faster than the time written for a neighbor, write the new time and remember where you came from.
4. When every place is done, walk back from C using "came from" to read the route.

 1public class FastestRoute {
 2  static char[] names = {'A', 'B', 'C', 'D'};
 3  static int n = names.length;
 4  static int[][] mins = new int[n][n];   // travel minutes; 0 = no road
 5  static final int INF = Integer.MAX_VALUE;   // "not reached yet"
 6
 7  // two-way road: set both cells
 8  static void addRoad(int a, int b, int minutes) {
 9    mins[a][b] = minutes;
10    mins[b][a] = minutes;
11  }
12
13  public static void main(String[] args) {
14    addRoad(0, 1, 7);    // A - B: 7 min
15    addRoad(0, 3, 4);    // A - D: 4 min
16    addRoad(1, 2, 12);   // B - C: 12 min
17    addRoad(1, 3, 5);    // B - D: 5 min
18
19    int start = 0, goal = 2;           // from A to C
20    int[] best = new int[n];           // fastest time found so far
21    int[] cameFrom = new int[n];       // the place just before it
22    boolean[] done = new boolean[n];   // time is final
23    for (int i = 0; i < n; i++) {
24      best[i] = INF;
25      cameFrom[i] = -1;
26    }
27    best[start] = 0;
28
29    for (int round = 0; round < n; round++) {
30      // 1. pick the unfinished place with the smallest time
31      int u = -1;
32      for (int i = 0; i < n; i++) {
33        if (done[i]) continue;
34        if (u == -1 || best[i] < best[u]) u = i;
35      }
36      if (best[u] == INF) break;   // the rest cannot be reached
37      done[u] = true;
38
39      // 2. try every road out of u: is going through u faster?
40      for (int v = 0; v < n; v++) {
41        if (mins[u][v] > 0 && !done[v]) {
42          int t = best[u] + mins[u][v];
43          if (t < best[v]) {
44            best[v] = t;
45            cameFrom[v] = u;
46          }
47        }
48      }
49    }
50
51    // 3. walk back from the goal to build the route
52    String route = "" + names[goal];
53    for (int v = cameFrom[goal]; v != -1; v = cameFrom[v]) {
54      route = names[v] + " -> " + route;
55    }
56    System.out.println("Fastest route: " + route);
57    System.out.println("Time: " + best[goal] + " minutes");
58    // prints: Fastest route: A -> B -> C
59    //         Time: 19 minutes
60  }
61}

▶ Try it in the Programiz online compiler: tap Copy, paste it there, change public class FastestRoute to public class Main (Programiz saves your code as Main.java, and Java needs the file name and the public class name to match), then press Run.

Here is how to read the new lines aloud:

The table below traces the program round by round, so you can check each step:

Walking back: C came from B, and B came from A. So the route is A → B → C, 19 minutes, the same answer as in Part 2.

Why is the picked time final? Every other unfinished place already takes longer to reach, and travel times are never negative, so no detour through them can be faster. (This is also why Dijkstra's algorithm does not work if a weight can be negative.)

Real map apps have millions of places, so they use faster versions of this idea, with shortcuts worked out ahead of time. The core question is the same: which path has the smallest total weight?