Graphs · Intermediate – Online Test

Question 1 Topological sort Intermediate Practice Answer computed

Kahn's algorithm repeatedly removes a vertex with in-degree 0, always choosing the smallest such vertex. What order does it produce?

Directed acyclic graph

012345 452031 450231 542310

Question 2 Shortest paths Intermediate Practice Answer computed

Dijkstra runs from A. What are the shortest distances to A, B, C, D, E?

Weighted undirected graph

03147 04158 04147 03169

Question 3 Minimum spanning trees Intermediate Practice Answer computed

What is the total weight of a minimum spanning tree of this graph?

Weighted undirected graph

Your answer

Question 4 Minimum spanning trees Intermediate Practice Answer computed

Prim's algorithm starts at A and repeatedly adds the cheapest edge leaving the tree. In what order are vertices added?

Weighted undirected graph

ABCDE ACDBE ACBDE ACBED

Question 5 Cycles Intermediate Practice

DFS colours vertices white (unvisited), grey (on the current path) and black (finished). In a directed graph, which edge proves a cycle?

An edge to a grey vertex (a back edge) An edge to a black vertex An edge to a white vertex Any edge to a visited vertex

Question 6 Bipartite graphs Intermediate Practice Code executed

What does this 2-colouring check print for the graph shown (all of its cycles have length 4) and for a triangle?

Undirected graph (neighbours in alphabetical order)

Python main.py

from collections import deque

def bipartite(adj):
    color = {}
    for s in adj:
        if s in color:
            continue
        color[s] = 0
        q = deque([s])
        while q:
            u = q.popleft()
            for v in adj[u]:
                if v not in color:
                    color[v] = 1 - color[u]; q.append(v)
                elif color[v] == color[u]:
                    return False
    return True

g1 = {'A': 'BD', 'B': 'ACE', 'C': 'BF', 'D': 'AE', 'E': 'BDF', 'F': 'CE'}
tri = {'X': 'YZ', 'Y': 'XZ', 'Z': 'XY'}
print(bipartite(g1), bipartite(tri))

False True False False True False True True

Question 7 Grid graphs Intermediate Practice Answer computed

How many islands (groups of 1s connected up, down, left or right) are in the grid?

Grid

	0	1	2	3	4
0	1	1	0	0	0
1	1	1	0	0	1
2	0	0	1	0	1
3	0	0	0	1	1

Your answer

Question 8 Shortest paths Intermediate Practice

Why can Dijkstra's algorithm give wrong answers when some edges have negative weights?

It loops forever on any negative edge It cannot store negative numbers It finalises a vertex when popped, assuming no later path can be cheaper – a negative edge found later can break that It works fine with negative edges

Question 9 Union-find Intermediate Practice Code executed

What does this disjoint-set program print?

Python main.py

parent = list(range(8))

def find(x):
    while parent[x] != x:
        parent[x] = parent[parent[x]]
        x = parent[x]
    return x

def union(a, b):
    parent[find(a)] = find(b)

for a, b in [(0, 1), (2, 3), (1, 3), (5, 6)]:
    union(a, b)
print(find(0) == find(2), find(4) == find(5), len({find(x) for x in range(8)}))

False False 5 True True 3 True False 4 True False 5

Question 10 BFS Intermediate Practice Code executed

This BFS should print the distances 0 1 2 1 2 3 for vertices A–F of the graph shown. Which line completes it?

Undirected graph (neighbours in alphabetical order)

Python main.py Line 9 is missing

from collections import deque

G = {'A': 'BD', 'B': 'ACE', 'C': 'BF', 'D': 'AE', 'E': 'BDF', 'F': 'CE'}
dist, q = {'A': 0}, deque('A')
while q:
    u = q.popleft()
    for v in G[u]:
        if v not in dist:
            ____________
            q.append(v)
print(*[dist[x] for x in 'ABCDEF'])

dist[u] = dist[v] + 1

dist[v] = len(dist)

dist[v] = dist[u] + 1

dist[v] = dist[u]

Question 11 Topological sort Intermediate Practice

When does a DAG have exactly one topological order?

When it has exactly one source When it is a tree Always When it contains a path through all vertices (a Hamiltonian path), i.e. Kahn's queue never holds two vertices at once

Question 12 Strongly connected components Intermediate Practice

How does Kosaraju's algorithm find strongly connected components?

BFS once from vertex 0 Union every edge with union-find Run Dijkstra from every vertex DFS to record finishing order, then DFS on the reversed graph in decreasing finish time; each tree is one SCC – O(V + E)

Question 13 Topological sort Intermediate Practice Answer computed

How many vertices of this DAG have in-degree 0 (sources)?

Directed acyclic graph

Your answer

Question 14 Grid graphs Intermediate Practice Answer computed

Moving up, down, left or right through open cells (0) only, what is the fewest number of moves from the top-left to the bottom-right cell? (1 = wall)

Maze

	0	1	2	3
0	0	0	0	1
1	1	1	0	1
2	0	0	0	0
3	1	0	1	0

Your answer

Question 15 Cycles Intermediate Practice Code executed

Can all courses be finished? [a, b] means b must be taken before a. What does this print?

Python main.py

from collections import deque

def can_finish(n, prereq):
    adj, indeg = [[] for _ in range(n)], [0] * n
    for a, b in prereq:
        adj[b].append(a); indeg[a] += 1
    q = deque(i for i in range(n) if indeg[i] == 0)
    done = 0
    while q:
        u = q.popleft(); done += 1
        for v in adj[u]:
            indeg[v] -= 1
            if indeg[v] == 0:
                q.append(v)
    return done == n

print(can_finish(4, [[1, 0], [2, 1], [3, 2]]), can_finish(3, [[1, 0], [2, 1], [0, 2]]))

False True True True True False False False

Graphs · Intermediate

Before you start