Binary heap Created 2026-10-13 Updated 2026-10-24
View more
A binary heap represents a priority queue as a complete binary tree obeying a heap order. We use the minimum convention: the priority of every parent in a rooted tree is no greater than the priorities of its children in a rooted tree. Equal priorities are allowed. Each stored entry may be a record carrying a priority key; the numerical example below displays only keys. Reversing the inequalities gives the maximum convention.
The complete binary tree can be stored directly in a zero-indexed array : read its levels from top to bottom, left to right. The root of a tree is at index . The possible children in a rooted tree of index are at and , and an index denotes a present entry only when it is less than . For , its parent in a rooted tree is at , using the floor function. Thus the links of the complete binary tree are determined by arithmetic rather than separately stored pointers.
Consider
(1)
The children in a rooted tree of index have keys ; those of index have keys ; those of index have keys . The six comparisons , , , , , establish the heap order. At index , the parent in a rooted tree is index , carrying key .
Figure 1.
One binary heap viewed as an array and a complete binary tree
. Matching indices identify the same entries in both representations. The heap order compares each parent in a rooted tree with its children in a rooted tree; it does not make a sorted array. Details.
The array is visibly not a sorted array: precedes , and precedes . Nor is the last entry a maximum: it is , whereas the maximum is at index . The heap order compares ancestors and descendants, without imposing an order between separate branches. Nevertheless, following the graph path from the root of a tree to any entry gives a chain of nondecreasing priorities. This short argument proves that peek can return , a minimum, without inspecting the other entries.
Insertion appends an entry to the array, preserving the shape of the complete binary tree, then uses sift up to repair the heap order. Insert key into the displayed binary heap. It is appended at index , and exchanges with indices , , then :
(2)
The moving key follows ; the keys each move down one level. Only this chain needs repair.
Now apply extract-min. Save key , move the last key to the root of a tree, and shorten the array to length . Use sift down, always choosing the smaller of the present children in a rooted tree:
(3)
First exchanges with key at index , since ; then with key at index , since . At index , the possible children in a rooted tree would be indices , both outside the shortened array, so the process stops. The returned key is , and the remaining binary heap is exactly the original one.
Figure 2.
Sift up inserts 1, then sift down restores the original binary heap after removing 1
. The four panels show the start and end of each repair. Colored arrows mark the moving key's graph path. The extraction panels contain seven entries: index 3 has no children in a rooted tree. Details.
For a nonempty binary heap with entries, the deepest level is , using the floor function and logarithm. Each exchange moves one level and uses only a bounded number of comparisons. The resulting time complexity bounds, expressed in Big O notation, are:
OperationTime complexityReason
peekRead the root of a tree.
Insert for Append, then sift up through at most the levels of the complete binary tree.
extract-min for Move the last entry, then sift down through at most those levels.
Build from an arbitrary arrayApply sift down from the last index with children in a rooted tree back to index .
These bounds assume constant-cost indexed access, key comparisons and exchanges, and available array capacity for insertion. Allocating and copying a larger array is a separate cost. Empty and one-entry cases take constant work.
To build a binary heap, begin at index and work backwards. Entries without children in a rooted tree already obey the heap order. Each sift down, also called heapify down, starts with every present smaller rooted tree below it already repaired. Most entries are close to the bottom and can move very little; successively longer repair distances occur for geometrically fewer entries. Summing these distances gives work, rather than charging to every entry. MIT's notes give this bottom-up construction and contrast it with repeated insertion.[ref]
The Dijkstra algorithm additionally needs to decrease the priority of an existing vertex when its tentative distance improves. Given its current index, lowering the key followed by sift up takes time for . An indexed binary heap maintains a separate map from item identity to its current index and updates that map after every exchange. For vertices numbered in a fixed range, the map can be another array, giving constant-time index lookup. An ordinary unindexed binary heap supplies no such guarantee: locating an arbitrary item can require scanning entries. Item identity and priority must remain distinct, especially when several vertices have equal tentative distances.
The attractive compromise is local organization with global usefulness. A binary heap maintains only the heap order, yet every extract-min gives the next smallest key. Repeated extraction of the original example gives , so a priority queue also supplies a sorting algorithm without storing a sorted array between extractions.
Read the full article
Binary search tree Created 2026-10-13 Updated 2026-10-14
View more
A binary search tree stores key-value entries in a binary tree, with distinct keys drawn from a total order. At every vertex, all keys in its left subtree must be smaller than its own key, and all keys in its right subtree must be larger. Thus the entries represent a partial function from keys to values: a key has at most one associated value and may be absent. [ref]
Lookup starts at the root of a tree. Compare the target with the current key: equality returns its value, a smaller target continues into the left subtree, and a larger target continues into the right subtree. Reaching an empty subtree reports absence. The ordering rule justifies discarding the other subtree at every step; this is the algorithm correctness argument for lookup. It applies to the entire subtree, even if that subtree contains many vertices. [ref]
In the seven-key example, search for . At , the comparison selects the right subtree; at , selects the left subtree; at , equality ends the search. The visited keys are , three key comparisons. The right-child chain stores exactly the same keys and satisfies the same binary search tree rule, but lookup of visits , five comparisons. Searching for absent key visits in the first binary search tree and all seven keys in the chain before reaching an empty right subtree.
Figure 1.
Lookup of key in two binary search trees containing the same seven keys
. Orange highlights visited keys and edges; green marks the match. The balanced shape has height of a binary tree and requires three visits, while the chain has height of a binary tree and requires five visits for this target. Details.
For a nonempty binary search tree of height of a binary tree , lookup inspects at most vertices. Under constant-cost key comparisons and child-reference access, its time complexity is in Big O notation, usually written for . With entries, , giving worst-case lookup. If the shape is kept balanced so that , lookup takes for . The empty and one-entry cases take constant work. The worst-case linear bound also appears in Sedgewick and Wayne's ordinary, unbalanced implementation. [ref]
In a shape with every level full, there are vertices, a geometric series. This explains how a small height of a binary tree can accommodate many entries. The binary search tree ordering rule alone does not guarantee this shape or logarithmic time complexity. Breadth-first search also gains no logarithmic key-lookup guarantee merely from having a binary tree: in the displayed balanced example, its left-to-right level order is , so it inspects six keys before finding , and an absent target requires all seven. Directed lookup uses the total order to choose one branch.
The ordering requirement includes every ancestor on the graph path from the root of a tree. Consider the smaller binary tree with root key , left child , right child , and right child under . Key must satisfy both , from its immediate parent in a rooted tree, and , from its position in the root's left subtree. Replacing by preserves all immediate parent-child comparisons, including , but violates . Lookup for would incorrectly go from to and then to an empty left subtree, overlooking the stored key.
Figure 2.
The binary search tree ordering rule constrains an entire subtree
. The valid example has . The invalid example passes immediate parent-child comparisons, but key lies in the left subtree of key and violates its inherited upper bound. Details.
An inorder traversal visits a left subtree, then its own vertex, then a right subtree. On the valid small example its output is ; on the invalid example it is , exposing the descent from to . Both seven-key binary search trees yield . The theorem is that an inorder traversal of a finite binary search tree with distinct keys lists every key once in strictly increasing total order. For a short proof outline, use mathematical induction on the number of vertices: each smaller subtree produces its own sorted list, and the full ordering rule places every left key before the current key and every right key after it. Concatenating these three parts preserves strict order. Sedgewick and Wayne's keys method uses this left-current-right order. [ref]
This combination is useful and attractive: one data structure supports directed lookup and ordered enumeration. An inorder traversal costs time complexity for entries, since it visits every vertex; balance accelerates lookup but cannot eliminate the work of outputting all keys.
// Destination: computer-science.bigb
Read the full article
Bipartite graph Created 2026-09-24 Updated 2026-10-14
View more
A bipartite graph separates its vertices into two independent sets: every edge goes from one part to the other. Here is a finite simple graph and an undirected graph, with no self-loops and no repeated edges. The two parts satisfy
(1)
Thus neither part contains an edge. The parts need not have equal sizes, and some pairs across them may have no edge; requiring every cross pair gives a complete bipartite graph. The independent set and cross-edge definitions are equivalent.[ref]
For example, the six-vertex cycle graph with edges has parts and . Drawing the same graph as a hexagon or in two columns changes neither its edges nor its bipartite property. An extra isolated vertex can go in either part.
Figure 1.
The same six-cycle and isolated vertex drawn as a cycle and as two independent parts
. Details.
We allow either part to be empty. Consequently a graph with no edges is bipartite, even when ; choose , . Here "two colours" means two colours are available, with no requirement to use both. This convention explicitly includes the empty case, whereas definitions requiring two nonempty classes need an exception. For several connected components of a graph, choose the two parts separately in each graph component and take their unions. In a nonempty connected graph that is bipartite, fixing one vertex's colour forces all others along graph paths, so its two-colour assignment is unique up to swapping the colours. Each graph component, including an isolated vertex, can be swapped independently.
The two-colourability criterion for bipartite graphs identifies these parts with the colour classes of a proper vertex colouring: assign colour to and colour to , so adjacent vertices have different colours. More surprisingly, the odd-cycle characterization of bipartite graphs turns a global requirement into one precise obstruction:
(2)
This statement is for the finite undirected graph and simple graph model above; a graph cycle has distinct vertices except for the repeated starting vertex. Along a graph cycle in a bipartite graph, colours alternate, so returning to the starting colour takes an even number of edges. Therefore any odd cycle, whether or not other edges join its vertices, prevents a bipartite split.[ref]
Breadth-first search supplies the converse constructively. Start an uncoloured vertex with colour , and use a FIFO queue to explore its graph component. When an edge first discovers , give the opposite colour to , record as its parent in a rooted tree, and enqueue . If both endpoints of any scanned edge already have the same colour, stop with a conflict. Restart from an uncoloured vertex until every graph component has been examined. If no conflict occurs, all edges cross the two colour classes, which are the required independent sets.[ref]
A conflict also explains the failure. In the rooted tree produced by breadth-first search, let be the graph distance from . The colour of is its distance's integer parity. An edge in an undirected graph satisfies , so equal colours force . Follow the two parent chains upward to their lowest common ancestor , discard the shared graph path from to , and join the remaining two graph paths with the conflict edge . The result is a genuine graph cycle with
(3)
edges, an odd integer. The two branches have no shared vertices except , so this is more than a closed walk. This odd cycle is a certificate that anyone can check directly, using only its listed vertices and edges.
Figure 2.
A BFS colour conflict closes a five-cycle; the shared root path is excluded from the certificate
. Details.
In the example, breadth-first search from gives , , and . The conflict edge closes the odd cycle , with five edges. The common edge is excluded. Thus the same procedure returns either two independent sets covering , or an explicit odd cycle. With adjacency lists and constant-time FIFO queue operations, its time complexity is in Big O notation, with additional storage.[ref]
The two parts often have a practical meaning: workers and jobs, with an edge exactly when a worker can perform a job. A matching in a graph chooses compatible worker–job pairs with no reused endpoint; merely being bipartite does not guarantee enough compatible pairs. Hall's marriage theorem characterizes when every worker can be matched, and the assignment problem adds costs to seek an optimal assignment. These connections make the bipartite structure useful after recognition, as the starting point for selecting edges under constraints.
Read the full article
Breadth-first search Created 2026-09-24 Updated 2026-10-14
View more
Breadth-first search is a graph search that explores successive layers of graph distance from a starting vertex . Here the graph is an undirected graph on a finite set of vertices, and distance counts edges, with no differing edge weights. Mark as discovered, assign , and place it in a FIFO queue. Repeatedly remove the front vertex and scan its adjacency list. Whenever a graph neighbour is still undiscovered, mark it immediately, record as its parent in a rooted tree in the discovery tree, assign , and enqueue at the rear. Marking on insertion ensures that another edge cannot enqueue the same vertex again. [ref]
Use the same undirected graph as depth-first search, with vertex set and edges
(1)
where denotes the unordered pair . Start at and scan graph neighbours in lexicographic order of their one-letter labels. The diagram's generator computes the following layers and the parent in a rooted tree assigned to each discovered vertex; the source is the root of a tree and has no parent in a rooted tree.
Graph distance from Vertices in discovery orderParent in a rooted tree in the same order
none
Figure 1.
Breadth-first search: graph distance layers and two ordered FIFO queue snapshots
. Solid edges record first discovery; dashed edges are still present in the original graph. The FIFO queue contains after processing and after processing , with its front on the left. Colors encode graph distance in the graph without edge weights. Details.
The discovery and removal orders both happen to be . After processing , the FIFO queue is : must be processed before the newer . Processing then skips the already discovered and enqueues , giving . Processing adds nothing. Processing discovers , giving ; later sees already marked and leaves its parent in a rooted tree unchanged. The discovery edges are , forming a rooted tree on all seven vertices even though the original graph contains graph cycles. The discovery tree contains six edges; it need not contain every examined edge.
First arrival is shortest because the FIFO queue keeps assigned distances in nondecreasing order, with entries from at most two consecutive layers. While processing distance , newly discovered vertices receive distance and join the rear. If an undiscovered vertex had a shorter graph path, its preceding vertex on that graph path would lie in an earlier layer and would already have discovered it. Thus is the minimum number of edges from to . This is a mathematical induction over the layers, not an assumption about the drawing. Following the parent in a rooted tree backwards at each step gives ; reverse that sequence to obtain the three-edge graph path . is another shortest graph path, but the specified graph neighbour order makes discover first. Changing that order can change the parent in a rooted tree without changing graph distances. [ref]
The shortest-route guarantee concerns the shortest path problem measured by edge count. It also minimizes total cost when every edge has the same positive cost. With unequal edge weights, first discovery need not minimize total cost; nonnegative costs can instead be handled by the Dijkstra algorithm. Breadth-first search is useful for minimum-hop routes and for finding all vertices within a specified graph distance. Its FIFO queue finishes an older layer before the next one, whereas depth-first search uses a call stack or explicit LIFO stack to pursue one branch immediately.
With adjacency lists and constant-cost discovery checks, together with constant worst-case or amortized analysis cost for FIFO queue insertion and removal, the time complexity is in Big O notation. Every reached vertex is enqueued and removed once, each incident edge is scanned at most twice in an undirected graph, and initializing all marks and distances takes . The FIFO queue contains at most vertices; the example's maximum is three. Discovery marks, distances and the recorded parent in a rooted tree for each nonroot vertex also give auxiliary space complexity, excluding the graph. An array that shifts every entry on front removal can lose the linear time complexity; the FIFO queue abstraction alone does not make removal constant-cost. Ordering the adjacency lists is a separate preprocessing cost.
A single start reaches only its connected component of a graph. Unreached vertices retain distance and have no recorded parent in a rooted tree. Restarting at each still-undiscovered vertex, while preserving all discovery marks, produces a forest covering the graph; each new root of a tree gets distance zero, so these distances refer to that root of a tree, not to the original .
Read the full article
Child in a rooted tree Created 2026-10-14 Updated 2026-10-25
View more
A vertex whose parent in a rooted tree is the specified vertex.
Read the full article
Chromatic polynomial of a unicyclic graph 2026-10-25
View more
If a unicyclic graph has vertices and its unique graph cycle has length , each of its off-graph cycle vertices contributes a factor after its parent in a rooted tree is coloured. Thus . Substituting the chromatic polynomial of a cycle yields the displayed formula, equivalently by repeated application of the chromatic polynomial after attaching a leaf.
Read the full article
Depth-first search Created 2026-10-13 Updated 2026-10-20
View more
Depth-first search is a graph search that follows a branch as far as it can before returning to try the next unexplored branch. Starting at a vertex of an undirected graph on a finite set of vertices, mark as discovered. Scan its graph neighbours in a fixed order: for each undiscovered vertex, record the current vertex as its parent in a rooted tree in the discovery tree, mark the new vertex, and explore it immediately using recursion. Return when its adjacency list is exhausted. Discovery marks persist after return, preventing a graph cycle from causing repeated exploration. This branch-and-return rule is the maze exploration described in MIT's notes. [ref]
Use the same unweighted undirected graph as breadth-first search, with vertex set and edges
(1)
where denotes the unordered pair . Visit graph neighbours in lexicographic order of their one-letter labels, starting at . The discovery order, computed by the diagram's generator, is
(2)
The discovery edges in order are . They form a rooted tree spanning the reached vertices, with root of a tree . The other edges, and , remain in the original graph but never discover a new vertex. In particular, the graph cycle causes no repeated discovery.
Figure 1.
Depth-first search: discovery edges and the active call stack on seven vertices
. Numbers show first-discovery order. Solid edges form the discovery tree; dashed edges belong only to the original graph. The right panel shows the call stack from oldest call to current call, including the return from before entering . Details.
At there is no undiscovered graph neighbour, so its call returns to . The next call enters , then , then , then . Immediately after discovering , the call stack is , with on top; is still discovered but its call has finished. The maximum call stack depth is six, although seven vertices are discovered. Following the recorded parent in a rooted tree backwards at each step reconstructs a graph path; here the route from to is , using five edges. Breadth-first search instead finds , using three edges. Depth-first search establishes reachability but does not guarantee the fewest edges.
An explicit LIFO stack can replace recursion, but its entries and discovery rule must be specified. To reproduce this exact traversal, store one frame per active vertex, retaining the next position in its adjacency list. Advance the top frame by one graph neighbour; if that vertex is undiscovered, mark it and push its frame immediately; pop an exhausted frame. Pushing all undiscovered graph neighbours at once and marking them on push is a different iterative variant. Even pushing them in reverse lexicographic order does not generally reproduce the parent in a rooted tree relationships above: would already be marked while processing , so could not discover .
With an adjacency list representation, constant-cost discovery checks and frame operations, and the graph neighbours already ordered, depth-first search has time complexity in Big O notation. Each reached vertex is entered once and each incident edge is examined at most twice in an undirected graph; initializing all discovery marks costs . The call stack has depth at most , since no active vertex repeats. Discovery marks and the recorded parent in a rooted tree for each nonroot vertex also need auxiliary space complexity, excluding storage for the graph. Sorting adjacency lists to obtain a chosen order is additional work. [ref]
One start explores only its connected component of a graph. To cover a disconnected graph, start again at every still-undiscovered vertex while keeping all discovery marks; the discovery trees form a forest. Depth-first search is useful for reachability, constructing a spanning tree of a connected graph, and organizing the return steps needed by a depth-first traversal of a tree. For detecting a graph cycle in a simple graph that is an undirected graph, an edge to an already discovered vertex other than the current parent in a rooted tree closes a graph cycle; the immediate return edge to that parent in a rooted tree is not itself a graph cycle.
// Target: computer-science.bigb
Read the full article
DFS lowpoint 2026-10-14
View more
For a finite simple graph that is an undirected graph, the DFS lowpoint of is the smallest DFS discovery time reachable by following zero or more discovery edges down its rooted tree, then at most one non-discovery edge to an ancestor. Staying at is allowed. Ignore the reverse traversal of the discovery edge to the parent in a rooted tree: it is the same edge, not an escape route. Start with . On returning from a child in a rooted tree , replace by . For a non-discovery edge from to an earlier ancestor , replace it by . This summarizes how far upward the explored branch can reconnect. [ref]
The cut vertex criterion has a separate case for each root of a tree in the discovery forest:
Why does equality matter? If , the branch below can reconnect to , so the discovery edge lies on a graph cycle and is not a bridge in a graph. Deleting the vertex destroys that reconnection too. If has a parent in a rooted tree, the branch is then separated from that parent in a rooted tree, explaining the non-strict cut vertex test. For a root of a tree, there is no earlier side to separate from; distinct discovery branches cannot have an edge between them, since depth-first search would have explored them as one branch. This gives the two-children in a rooted tree rule. These are proof outlines of the criteria. [ref][ref]
In the joined- example with DFS discovery times , the DFS lowpoints in label order are . For and its child in a rooted tree , : is a bridge in a graph, and is a cut vertex. For and its child in a rooted tree , : is a cut vertex, although is not a bridge in a graph. The root of a tree has only one child in a rooted tree, , so it is not a cut vertex. In the shared- example, the root of a tree has two children in a rooted tree, and , and is a cut vertex, while every DFS lowpoint is and no edge passes the strict bridge in a graph test.
Restart depth-first search at every undiscovered vertex to cover a disconnected graph, applying the root of a tree rule separately in each connected component of a graph. With adjacency lists and constant-cost label operations, computing all DFS lowpoints, cut vertices and bridges in a graph has time complexity in Big O notation, because each vertex is discovered once and each edge is inspected twice. The simple parent-skipping rule assumes a simple graph. In a multigraph, skip only the actual parent edge, identified individually: a parallel edge to the same parent in a rooted tree is a valid reconnection and can prevent the first edge from being a bridge in a graph. The criteria here concern undirected graphs; a directed graph requires a different connectivity analysis.
Read the full article
Disjoint-set forest 2026-10-18
View more
A disjoint-set forest represents each block of a set partition by a rooted tree. Each set element stores a pointer to its parent in a rooted tree; the root of a tree stores a pointer to itself as a stopping convention. These self-pointers are sentinels, omitted from the forest's edges. Following parent pointers reaches the disjoint-set representative, the root of a tree. An indexed array parent suffices when members are numbered consecutively. The rooted trees encode membership; their edges need not be edges of any input graph.
To link different blocks of a set partition, point one root of a tree at the other root of a tree. Linking roots preserves every old membership and joins exactly the two rooted trees. Arbitrarily reparenting a nonroot could detach only part of a block of a set partition, so it would not implement the required disjoint-set union operation. The disjoint-set find operation terminates because each nonroot pointer moves towards the unique root of a tree; linking distinct roots cannot introduce a graph cycle.
Read the full article
Heap order Created 2026-10-13 Updated 2026-10-24
View more
The minimum convention for heap order requires every parent in a rooted tree to have priority no greater than each of its children in a rooted tree. The displayed formula uses the array representation of a binary heap. It permits equal priorities and does not require a sorted array; the maximum convention reverses the inequality.
Read the full article
Huffman coding Created 2026-09-24 Updated 2026-10-14
View more
Huffman coding makes frequent symbols cheap to store by giving them short codewords, while allowing rare symbols longer codewords. For a known probability distribution on a finite alphabet with at least two positive-probability symbols, binary Huffman coding constructs a prefix code minimizing expected codeword length among binary prefix codes that encode one source symbol at a time. The objective is an average under that probability distribution; it does not promise to shorten every message. Encoder and decoder must agree on the resulting Huffman code. [ref]
The construction grows a binary tree from its leaves towards its root of a tree. Start with one leaf per symbol, weighted by its probability. Repeatedly join the two currently smallest weights beneath a new parent in a rooted tree, whose weight is their sum, and replace the pair by that subtree. Include newly formed subtrees when choosing the next pair. When one tree remains, label the two outgoing edges at every internal vertex with and ; the labels on the graph path from the root of a tree to a symbol give its codeword. This is a greedy algorithm: each step makes a locally cheapest merge, yet the result is an optimal prefix code.
For a concrete example, use probabilities , , , . First join and , creating weight . The remaining weights are for , for the subtree, and for . Join the two weights to make , then join with that subtree to make . The merge weights are therefore . Each merge adds one bit to every codeword below it, so their sum is the expected codeword length: bits per source symbol. The diagram fixes the edge labels to produce the Huffman code used below.
Figure 1.
Huffman merges for probabilities 0.4, 0.3, 0.2, 0.1 and their binary codewords
. Details.
The useful insight is that choosing short codewords is a resource allocation problem: the prefix code condition constrains the available codeword lengths through the Kraft inequality. Huffman coding solves this one-symbol problem exactly for the supplied probability distribution. For repeated emissions of a memoryless classical information source, the same Huffman code can be applied symbol by symbol. More general compression can exploit dependencies or encode groups of symbols; the one-symbol optimality statement does not compare all such methods.
Read the full article
Huffman sibling contraction 2026-10-14
View more
Replace sibling leaves in a code tree labelled by their common parent in a rooted tree, now a leaf labelled of weight . All other codewords stay fixed; each of loses one bit. For any such code tree and the contracted code tree , their weighted costs satisfy
(1)
If have two least weights, the Huffman sibling property gives an optimal prefix code containing this pair. Its contracted prefix code must be optimal for the reduced weights : any cheaper reduced prefix code could be expanded at by appending , giving a cheaper original prefix code. Conversely, expanding any optimal reduced prefix code adds precisely and attains the original minimum. This is optimal substructure, the justification for repeating the merge in Huffman coding. [ref]
In the exchange diagram, contract to weight at leaf depth in a code tree . The reduced expected codeword length is bits; expanding restores bits. For , the reduction leaves one symbol: allow its temporary codeword to be empty, of cost zero, so expansion gives the two one-bit codewords. This convention is only the terminal reduced problem; the original source has at least two symbols.
Read the full article
Past exam of the computer science course of the University of Oxford / 2015 / Concurrent programming / 2 / a / ii / Solution 2026-10-31
View more
Use one logical traversal token carrying the discovered vertex set and the active LIFO stack of vertices. The current vertex either discovers its first still-unvisited outgoing graph neighbour, or returns to its preceding stack entry. The former records both the child's parent in a rooted tree and the parent's child. Unlike concurrent flooding discovery, this visits one entire branch before the next, giving an actual depth-first search.
The important directed-graph detail is that a child's parent need not be an outgoing graph neighbour. Return the token by routing it through the original directed graph; a routing hop does not count as a traversal visit. The following duplicate-suppressed flooding route requires no previously known topology and sends only to immediate outgoing graph neighbours.
final case class Token(visited: Set[NodeId], stack: List[NodeId], serial: Int)
sealed trait Msg
final case class Route(serial: Int, target: NodeId, token: Token) extends Msg
case object Finished extends Msg
Here stack.head is the current vertex. Use the same paired toNode and fromNode ports as in (i), now with the new Msg type. Set mailbox capacity to , normalize neighbours with distinct, and again leave the mailboxes open until all processes have joined. The following helpers are local functions inside each node's generated process.
def span: PROC = proc {
  val adj = neighbours.distinct
  val routed = scala.collection.mutable.Set[Int]()
  var entered = false
  var done = false

  def flood(message: Msg): Unit =
    for (w <- adj) toNode(w) ! message

  def move(target: NodeId, state: Token): Unit = {
    val s = state.serial + 1
    routed += s
    flood(Route(s, target, state.copy(serial = s)))
  }

  def step(t: Token): Unit = {
    assert(t.stack.head == me)
    if (!entered) {
      entered = true
      parent = if (t.stack.tail.isEmpty) me else t.stack.tail.head
      children = Nil
    }
    adj.find(w => !t.visited(w)) match {
      case Some(w) =>
        children = children :+ w
        move(w, Token(t.visited + w, w :: t.stack, t.serial))
      case None =>
        t.stack.tail match {
          case p :: rest => move(p, t.copy(stack = p :: rest))
          case Nil => flood(Finished); done = true
        }
    }
  }

  if (me == 0) step(Token(Set(0), List(0), 0))
  while (!done) {
    fromNode(me) ? () match {
      case r @ Route(s, target, t) =>
        if (!routed(s)) {
          routed += s
          if (target == me) step(t) else flood(r)
        }
      case Finished => flood(Finished); done = true
    }
  }
}
Every route number is globally unique: there is one logical token, and its serial increases at every move. The sender inserts that serial in its own routed set before flooding; this stops a returning copy from circulating again. Intermediate vertices forward the first copy of an envelope and ignore later copies. Its target consumes exactly one copy without forwarding it. Because the directed graph is strongly connected, a simple directed path from sender to target exists; its intermediate vertices eventually relay the envelope. Thus each move eventually finishes.
A routed return can pass through a vertex not yet discovered by the depth-first search. That vertex only forwards the envelope: it does not run step, change entered, or assign a parent. This distinction is essential. For the directed cycle , returning from two to one uses , while the logical traversal stack changes from to .
Figure 1.
A depth-first search return follows a routed directed path when the child has no reverse directed edge
. Details.
The discovered vertex set only grows. Each newly discovered vertex is pushed once and later popped once; an exhausted vertex can never acquire a new unvisited neighbour as this set grows. Consequently there are exactly downward moves and return moves. When the root exhausts its outgoing graph neighbours, every vertex has been visited, by the standard reachability argument for depth-first search. Each nonroot parent was recorded along the actual downward directed edge, and children records exactly those assignments in discovery order.
There are route envelopes, each forwarded at most once per outgoing directed edge, and one final Finished flood. Each node forwards Finished before exiting; strong connectivity therefore delivers it everywhere. There are at most total messages into any mailbox, below the proposed capacity. Even a mailbox whose process has already exited cannot block later sends. All processes terminate with
(1)
This deliberately trades communication efficiency for a simple valid solution on a genuinely directed graph. A direct parent acknowledgement would instead require an additional bidirectional-edge assumption, which the question does not supply.
Read the full article
Past exam of the computer science course of the University of Oxford / 2015 / Concurrent programming / 2 / a / i / Solution 2026-10-31
View more
A directed graph needs an explicit termination argument. After assigning its parent in a rooted tree, a vertex must still receive later traffic: having no new graph neighbours to discover is not proof that other senders have finished. Use a discovery wave together with duplicate-suppressed announcements of activated vertices. Both kinds of message identify their immediate sender, who has already activated.
sealed trait Msg { def from: NodeId }
final case class Discover(from: NodeId) extends Msg
final case class Active(from: NodeId, origin: NodeId) extends Msg
Let adj = neighbours.distinct. The actual communication objects must expose both input and output ports: the paper's Seq[![Msg]] annotation supplies only output capabilities, although the following sentence also requires receiving. Set up one shared-writer, single-reader buffered message-passing channel per vertex, publish its output in toNode, and keep its input in fromNode. Only node i reads fromNode(i). These are the two ports of the same underlying mailbox, not additional graph edges. The question's prohibition on buffered message-passing channels applies to Question 1(a), not to this question.
Take , reliable delivery, eventual scheduling, finite adj, and mailbox capacity . Every node has at most distinct incoming neighbours, including itself if there is a self-loop. The bound below ensures that no send blocks merely because a mailbox's receiver is not currently reading. Do not close these shared mailboxes on local process termination: late, redundant traffic is harmless and bounded. Their creator can release them after the parallel composition has joined. For example, the concrete setup can use
val mailbox = Vector.fill(N)(N2NBuf[Msg](B, 0, 1))
val toNode: Seq[![Msg]] = mailbox
val fromNode: Seq[?[Msg]] = mailbox
Here the zero writer count makes the shared output independent of individual writer departures; processes do not call its closeOut during the search.
def span: PROC = proc {
  val adj = neighbours.distinct
  var started = false
  val known = scala.collection.mutable.Set[NodeId]()

  def announce(origin: NodeId): Unit = {
    if (!known(origin)) {
      known += origin
      for (w <- adj) toNode(w) ! Active(me, origin)
    }
  }
  def activate(sender: NodeId): Unit = {
    started = true
    parent = if (me == 0) 0 else sender
    for (w <- adj if me == 0 || w != parent)
      toNode(w) ! Discover(me)
    announce(me)
  }

  if (me == 0) activate(0)
  while (known.size < N) {
    val message = fromNode(me) ? ()
    if (!started) activate(message.from)
    message match {
      case Discover(_) => ()
      case Active(_, origin) => announce(origin)
    }
  }
}
An announcement may be a vertex's first incoming message. It then serves as a discovery message too: its immediate sender is already active, and the receiving vertex adopts that sender as its parent in a rooted tree before forwarding anything. This preserves the required first-message rule. In particular, an inactive vertex never forwards announcements while remaining inactive, which could invalidate the parent-order argument.
For each nonroot vertex, its parent in a rooted tree activated strictly earlier. Repeated parent-following therefore cannot make a graph cycle and eventually reaches the unique initially active vertex, zero. Each parent assignment uses an actual incoming directed edge. Strong connectivity ensures eventual activation of every vertex: if an activated set were proper, a directed path from zero to an inactive vertex would have a first edge leaving that set. Its sender sends a discovery message along that edge; excluding its own parent does not exclude an inactive neighbour.
Each activation sends at most one Discover on each outgoing directed edge. For each of the origins, each vertex forwards Active at most once on each outgoing directed edge. Therefore a mailbox receives at most messages over the whole run, proving the chosen nonblocking storage bound. Each origin's announcement eventually reaches every vertex, since every first receipt forwards it on all outgoing directed edges. Thus every known set reaches size and every process terminates, even if redundant messages remain unread:
(1)
No timeout is used to conclude that the distributed work has finished. This uses larger finite mailboxes to make the termination proof simple, rather than assuming that simultaneous synchronous broadcasts cannot deadlock.
Read the full article
Past exam of the graph theory course of the University of Oxford / 2023 / 2 / d / Solution 2026-10-25
View more
First reduce the unicyclic graph to its unique graph cycle . Delete the edges of but retain every vertex. The remaining graph is a forest, since any surviving graph cycle would be a second one in . Each of its connected components of a graph contains a vertex of : follow a graph path to in the original connected graph, stopping at the first vertex of ; this initial segment uses no edge of .
No such connected component of a graph contains two vertices of . Otherwise, on the tree graph path between them, choose two successive visits to . The segment between these visits has no internal vertex on and uses no edge of . Combining it with either connecting arc of gives a second graph cycle, a contradiction. Thus the remaining graph consists of trees, each rooted at exactly one vertex of .
After choosing a proper vertex colouring of from colours, colour these rooted trees away from their roots. Each of the off-graph cycle vertices has one already coloured parent in a rooted tree, leaving exactly choices. The multiplication principle therefore gives
(1)
Equivalently, this repeatedly applies the chromatic polynomial after attaching a leaf formula.
To compute the chromatic polynomial of a cycle, the base case is the graph triangle:
(2)
For , deleting a cycle graph edge gives a path graph on vertices, while edge contraction gives . The chromatic polynomial of that path graph is , by choosing the colour of its first vertex and then each successive vertex. Hence the deletion-contraction recurrence for the chromatic polynomial gives
(3)
Using mathematical induction, substitute to obtain
(4)
Multiplying by the factor for the attached trees proves the chromatic polynomial of a unicyclic graph formula
(5)
Read the full article
Past exam of the year 1 of the computer science course of the University of Oxford / 2019 / Functional programming, design and analysis of algorithms / 6 / a / i / Solution 2026-10-25
View more
Store a complete binary tree in a one-indexed array , level by level. Index has parent in a rooted tree for and possible children in a rooted tree and , present only when their indices are at most . The max-heap condition is for every .
Following these inequalities from the root of a tree to any entry proves that is a maximum. The heap order does not sort siblings or unrelated branches. The complete binary tree has height , which bounds how far any single repair can travel. Store the current heap size separately from the array's capacity.
Read the full article
Past exam of the year 1 of the computer science course of the University of Oxford / 2019 / Functional programming, design and analysis of algorithms / 6 / c / Solution 2026-10-25
View more
Given the target's current heap index , remove it as follows. If , discard the last entry. Otherwise replace by and reduce by one. If the replacement is larger than its parent in a rooted tree, use sift up; otherwise use the maximum-oriented sift down from .
Only comparisons incident to the replacement can initially violate the heap order. If it exceeds its parent, it also dominates the old children because the old key dominated those children and was no larger than the parent; an upward repair suffices. Otherwise the upward comparison is valid and only a downward repair can be needed. Thus removal takes worst-case time after the location is known. Searching an unindexed heap for an arbitrary specified key can instead require time; the logarithmic bound does not include such a search.
Read the full article
Path compression 2026-10-18
View more
Path compression changes parent pointers during a disjoint-set find operation so that future queries traverse fewer edges. Full path compression first follows the entire parent route to its root of a tree, then makes every member on that route point directly to that same root of a tree. No member changes its block of a set partition or its disjoint-set representative. Pointers outside the traversed route stay as they were. The following iterative Python implements full path compression and union by rank; parent and rank are initially indexed arrays with parent[x] = x and rank[x] = 0 for every valid member.
def find(x):
    root = x
    while parent[root] != root:
        root = parent[root]
    while parent[x] != x:
        following = parent[x]
        parent[x] = root
        x = following
    return root

def unite(x, y):
    a, b = find(x), find(y)
    if a == b:
        return False
    if rank[a] < rank[b]:
        a, b = b, a
    parent[b] = a
    if rank[a] == rank[b]:
        rank[a] += 1
    return True
Starting from the displayed disjoint-set forest, find(3) traverses , returns and changes only from to . The route still has two edges. Then find(5) changes only from to . The final parent array is ; every stored rank retains its displayed value. The rooted tree at now has height one although its root's rank is two. Root still represents a separate singleton set.
Figure 1.
Full path compression shortens two parent routes while union by rank metadata stays unchanged
. Arrows point towards the parent in a rooted tree; self-pointers at roots are omitted. The same partition of a set appears before and after find(3) followed by find(5). Labels record stored ranks, including historical ranks at nonroots. Details.
The two-pass algorithm first discovers the answer and then reuses it. During the second pass, saving following before overwriting the pointer preserves the remaining route. Every replacement pointer targets the original root of a tree, proving that the partition of a set is unchanged.
Full path compression is one specific rule. The authored UF.java implementation instead uses path halving, redirecting a visited member to its parent's parent while advancing along the route. Its union by rank rule agrees with the one above.[ref]
Read the full article
Rooted tree Created 2026-09-28 Updated 2026-10-14
View more
A rooted tree is a tree with a distinguished vertex, its root of a tree . Choosing turns connections into a hierarchy: every other vertex has a unique parent in a rooted tree, the preceding vertex on its graph path from . Conversely, the vertices whose parent in a rooted tree is are the children in a rooted tree of . Choosing the root of a tree changes this description, while the underlying edges remain the same. Arrows towards the root of a tree can encode the relationship, as in MIT's counting notes; the undirected tree itself needs no arrows. [ref]
In the seven-vertex tree above, choose . The levels, grouped by graph distance from the root of a tree, are , , , . The children in a rooted tree of are , and the parent in a rooted tree of is . Choosing instead makes the levels , , , , , : now has parent in a rooted tree , reversing their relationship. All six edges survive.
This hierarchy supports structural recursion: process the smaller rooted trees below each vertex, then combine their results. A depth-first traversal of a tree explores one branch before returning; breadth-first search processes successive levels. The lowest common ancestor identifies where two routes from the root of a tree last coincide. For it is when . A binary tree imposes an additional restriction on children in a rooted tree; a general rooted tree has no such bound.
Read the full article
Root of a tree Created 2026-10-14 Updated 2026-10-20
View more
The distinguished vertex that specifies a rooted tree. Its choice determines the parent in a rooted tree and children in a rooted tree relationships.
Read the full article