# Fully Dynamic Breadth First Search and Spanning Trees in Directed Graphs

Preprint · Gregory Morse, Tamás Kozsik

- Archive id: arxiv:2604.12370
- Published: 2026-04-14
- arXiv: https://arxiv.org/abs/2604.12370
- Source URL: https://arxiv.org/abs/2604.12370
- PDF: https://arxiv.org/pdf/2604.12370
- Provenance: arxiv

## Abstract

We study the problem of maintaining a breadth-first spanning tree and the induced BFS ordering in a directed graph under edge updates. While semi-dynamic algorithms are known, maintaining the spanning tree, level information, and numbering together in the fully dynamic setting is less developed. This preprint presents a framework for fully dynamic BFS in directed graphs together with supporting data structures for maintaining the BFS tree, single-source shortest paths, and single-source reachability under both insertions and deletions.

_Abstract reproduced under CC0-1.0 (arXiv descriptive metadata)._

---
Space Kitty Archive · https://space-kitty.com · API: https://space-kitty.com/api/v1 · MCP: https://space-kitty.com/mcp · Premium: $0.20/request via x402 (Base Sepolia (testnet)). Metadata: arXiv (CC0), OpenAlex (CC0), Europe PMC (CC BY/CC0 works), ClinicalTrials.gov.