Create a Graph, print it

The problem, simply

You get a number V and a list of pairs. The places are numbered 0 to V - 1. Each pair [u, v] is a road between place u and place v, and you can drive it both ways.

Store these roads in the computer, then print every place followed by the places it has a road to. For example 1 -> 0 2 3 4.

A story to remember it

Picture it

Examples

Way 1: the simple way

Draw the big table. It has one row and one column per place. Put a 1 in row u, column v when there is a road, and a 0 when there is not. This table is called an adjacency matrix.

1. Make a V by V table full of zeros.
2. For each road [u, v], set matrix[u][v] = 1 and matrix[v][u] = 1.
3. To print place i, walk across row i and print every column that holds a 1.

class GraphMatrix {
    public static void createAndPrint(int V, int[][] edges) {
        int[][] matrix = new int[V][V];
        for (int[] edge : edges) {
            int u = edge[0], v = edge[1];
            matrix[u][v] = 1;
            matrix[v][u] = 1;          // two-way road
        }
        for (int i = 0; i < V; i++) {
            StringBuilder line = new StringBuilder(i + " ->");
            for (int j = 0; j < V; j++) {
                if (matrix[i][j] == 1) line.append(' ').append(j);  // look at every box
            }
            System.out.println(line);
        }
    }

    public static void main(String[] args) {
        int[][] edges = {{0, 1}, {0, 4}, {1, 2}, {1, 3}, {1, 4}, {2, 3}, {3, 4}};
        createAndPrint(5, edges);
    }
}

How long it takes: filling the table is O(E), but printing looks at every box, O(V^2). Extra room: the table always has V * V boxes, O(V^2), even when there are almost no roads. It does answer "is there a road from u to v?" in one look, which is its one real strength.

Way 2: the clever way

Give each place its own short list of neighbors, like the friend pages. This is an adjacency list.

1. Make V empty lists.
2. For each road [u, v], add v to the list of u and add u to the list of v.
3. To print place i, read its list from start to end.

class GraphList {
    public static List<List<Integer>> build(int V, int[][] edges) {
        List<List<Integer>> adj = new ArrayList<>();
        for (int i = 0; i < V; i++) adj.add(new ArrayList<>());  // one empty page per place
        for (int[] edge : edges) {
            int u = edge[0], v = edge[1];
            adj.get(u).add(v);
            adj.get(v).add(u);         // leave this line out for one-way roads
        }
        return adj;
    }

    public static void print(List<List<Integer>> adj) {
        for (int i = 0; i < adj.size(); i++) {
            StringBuilder line = new StringBuilder(i + " ->");
            for (int nb : adj.get(i)) line.append(' ').append(nb);  // only real friends
            System.out.println(line);
        }
    }

    public static void main(String[] args) {
        int[][] edges = {{0, 1}, {0, 4}, {1, 2}, {1, 3}, {1, 4}, {2, 3}, {3, 4}};
        print(build(5, edges));
    }
}

How long it takes: each road is written twice and each written name is read once, O(V + E). Extra room: V lists holding 2E names in total, O(V + E). Most real graphs have far fewer roads than V * V, so this is the standard choice in interviews.

Watch out for

• Places with no roads still need their own empty list, or adj.get(i) throws an error.
• Places might be numbered from 1, not 0. Make V + 1 lists, or subtract 1 from every name.
• Repeated roads, like [0, 1] given twice, are stored twice. Use a Set per place if the problem says to ignore repeats.
• With weights, store pairs: adj.get(u).add(new int[]{v, w}).

What interviewers ask next

• When is the table better? When the graph is dense (close to V * V roads) or when you must answer "is u next to v?" very often. The table answers in O(1), the list in O(degree).
• How do you store a weighted graph? Keep int[]{neighbor, weight} in each list, or a Map<Integer, Integer> per place if you need fast lookups.
• What is an edge list? Just the input list of pairs. It is the right shape for algorithms that loop over all roads, like Bellman-Ford and Kruskal.
• How would you store a graph with a billion places? Compressed rows: one long array of all neighbors and an array of start positions for each place. It is the adjacency list packed tight.

Remember this

Grown-up words: places are vertices, roads are edges, the friend pages are an adjacency list, the big table of ticks is an adjacency matrix, and the number of names on a page is the degree of that vertex.