An undirected simple graph has 9 vertices and 7 edges. What is the sum of the degrees of all its vertices?
A social network has 1,000,000 users and each user has about 150 friends. You need to run BFS on it. Which representation should you use?
Which operation is asymptotically faster with an adjacency matrix than with adjacency lists?
Graph G is drawn below as adjacency lists.
// undirected graph G, 8 vertices, 10 edges
0: 3, 5
1: 3, 6
2: 5, 7
3: 0, 1, 4
4: 3, 5, 6
5: 0, 2, 4
6: 1, 4, 7
7: 2, 6
In what order does BFS starting at vertex 0 visit the vertices? Neighbours are taken in the order listed (increasing).
Using the same graph G:
// undirected graph G, 8 vertices, 10 edges
0: 3, 5
1: 3, 6
2: 5, 7
3: 0, 1, 4
4: 3, 5, 6
5: 0, 2, 4
6: 1, 4, 7
7: 2, 6
In what order does the recursive DFS below, called as dfs(adj, 0, visited), print the vertices?
static void dfs(List<List<Integer>> adj, int u, boolean[] visited) {
visited[u] = true;
System.out.print(u + " ");
for (int v : adj.get(u)) {
if (!visited[v]) dfs(adj, v, visited);
}
}
Using the same graph G:
// undirected graph G, 8 vertices, 10 edges
0: 3, 5
1: 3, 6
2: 5, 7
3: 0, 1, 4
4: 3, 5, 6
5: 0, 2, 4
6: 1, 4, 7
7: 2, 6
What does this iterative DFS print when s = 0?
Deque<Integer> stack = new ArrayDeque<>();
boolean[] visited = new boolean[8];
stack.push(s);
while (!stack.isEmpty()) {
int u = stack.pop();
if (visited[u]) continue;
visited[u] = true;
System.out.print(u + " ");
for (int v : adj.get(u)) {
if (!visited[v]) stack.push(v);
}
}
Run BFS on graph G starting from vertex 7.
// undirected graph G, 8 vertices, 10 edges
0: 3, 5
1: 3, 6
2: 5, 7
3: 0, 1, 4
4: 3, 5, 6
5: 0, 2, 4
6: 1, 4, 7
7: 2, 6
Which vertices are at distance exactly 2 (two edges) from 7?
A BFS from vertex 0 produced this parent array (−1 means "no parent"):
index: 0 1 2 3 4 5 6 7
parent: -1 3 5 0 3 0 1 2
Which shortest path to vertex 6 does it encode, printed from source to target?
An undirected graph has vertices 0–9 and exactly these edges:
0-4 4-7 7-0 1-2 2-8 5-9
How many connected components does it have?
This BFS marks vertices when they are dequeued. What does it print?
List<List<Integer>> adj = new ArrayList<>();
adj.add(Arrays.asList(1, 2)); // 0
adj.add(Arrays.asList(0, 3)); // 1
adj.add(Arrays.asList(0, 3)); // 2
adj.add(Arrays.asList(1, 2)); // 3
boolean[] seen = new boolean[4];
Deque<Integer> q = new ArrayDeque<>();
q.add(0);
while (!q.isEmpty()) {
int u = q.poll();
seen[u] = true;
System.out.print(u + " ");
for (int v : adj.get(u)) {
if (!seen[v]) q.add(v);
}
}
What is the running time of BFS on a graph with V vertices and E edges stored as adjacency lists?
You run the same BFS on a graph stored as an adjacency matrix, scanning row u to find u's neighbours. What is the running time now?
In this undirected cycle test, what happens if the condition v != parent is removed (so the else branch always returns true)?
static boolean hasCycle(List<List<Integer>> adj, int u, int parent, boolean[] visited) {
visited[u] = true;
for (int v : adj.get(u)) {
if (!visited[v]) {
if (hasCycle(adj, v, u, visited)) return true;
} else if (v != parent) {
return true;
}
}
return false;
}
A directed graph has the edges 0 → 1, 0 → 2, 1 → 3, 2 → 1. A colour-based DFS (WHITE / GREY / BLACK) starts at 0 and takes neighbours in increasing order. When it examines the edge 2 → 1, what colour is vertex 1, and what does that mean?
The 6-cycle 0–1–2–3–4–5–0 is bipartite. Which single extra edge makes it no longer bipartite?
Which statement about bipartite graphs is true?
Run Kahn's algorithm on the DAG D below, always removing the smallest vertex whose in-degree is 0 (use a PriorityQueue<Integer>).
// directed acyclic graph D, 7 vertices (u: out-neighbours)
0:
1:
2: 3
3: 1
4: 0, 1
5: 0, 2
6: 2, 4
What order does it produce?
On the same DAG D, run DFS from vertices 0, 1, …, 6 in turn (skipping visited ones), neighbours in increasing order, and record each vertex when its call finishes. Which topological order do you get by reversing the finishing order?
// directed acyclic graph D, 7 vertices (u: out-neighbours)
0:
1:
2: 3
3: 1
4: 0, 1
5: 0, 2
6: 2, 4
Which of these is not a valid topological order of DAG D?
// directed acyclic graph D, 7 vertices (u: out-neighbours)
0:
1:
2: 3
3: 1
4: 0, 1
5: 0, 2
6: 2, 4
How many different topological orders does this DAG have?
// 5 vertices, edges:
0 -> 1 0 -> 2 1 -> 3 2 -> 3 4 -> 3
Kahn's algorithm stops with only 5 of the graph's 8 vertices in its output list. What can you conclude?
Does this compile (with import java.util.*;)?
List<Integer>[] adj = new ArrayList<Integer>[5];
System.out.println(adj.length);
What does this print?
int[][] edges = {{2, 0}, {1, 2}, {0, 1}, {2, 3}};
List<List<Integer>> adj = new ArrayList<>();
for (int i = 0; i < 4; i++) adj.add(new ArrayList<>());
for (int[] e : edges) {
adj.get(e[0]).add(e[1]);
adj.get(e[1]).add(e[0]);
}
System.out.println(adj.get(2) + " " + adj.get(0).size());
An airline wants the connection with the fewest flights from one city to another (every flight counts the same). Which algorithm fits best?
Explain why BFS finds a path with the fewest edges but recursive DFS in general does not. Use graph G (neighbours in increasing order, start 0, target 7) as your example.
// undirected graph G, 8 vertices, 10 edges
0: 3, 5
1: 3, 6
2: 5, 7
3: 0, 1, 4
4: 3, 5, 6
5: 0, 2, 4
6: 1, 4, 7
7: 2, 6
To detect a cycle in a directed graph, a student reuses the undirected idea: "if DFS meets an already visited vertex, there is a cycle". Give a small directed graph where this gives the wrong answer, and explain how three colours fix it.
Explain why Kahn's algorithm outputs fewer than V vertices exactly when the directed graph has a cycle.
For each situation, choose edge list, adjacency matrix or adjacency lists, and give a one-line reason: (a) a city road map with 20,000 junctions and 50,000 roads, used for route finding; (b) a 300-vertex graph in which almost every pair is connected and the program constantly asks "are u and v joined?"; (c) the input of an algorithm that first sorts all edges by weight and then processes them one by one.
Write a static method int countComponents(int n, int[][] edges) that returns the number of connected components of the undirected graph with vertices 0 … n − 1 and the given edges (each edges[i] is {u, v}). It must run in O(V + E) and must not use recursion. Example: countComponents(5, new int[][]{{0, 1}, {1, 2}, {3, 4}}) returns 2.
Write a static method boolean isBipartite(List<List<Integer>> adj) for an undirected graph given as adjacency lists (vertices 0 … n − 1, possibly disconnected). Use BFS 2-colouring. Example: a 4-cycle is bipartite; a triangle is not.