Learn Before
Breadth-First Search (BFS) on Graphs
Breadth-first search (BFS) is a deterministic graph-traversal algorithm that, given a graph and a source vertex (or a set of source vertices), visits every vertex reachable from the source(s) in non-decreasing order of hop-distance (number of edges traversed). It maintains a FIFO queue of frontier vertices: it dequeues the next vertex, marks it visited, and enqueues each of its unvisited neighbors, so vertices at distance are fully expanded before any vertex at distance . The output is a BFS tree rooted at the source(s), and for every visited vertex the algorithm yields the shortest unweighted-edge distance from the nearest source to . Because the order of expansion is determined by the queue discipline and the graph structure, two runs on the same graph and source set produce the same traversal order and the same set of explored paths up to any cutoff depth , which is what makes BFS deterministic and reproducible. The procedure extends to multi-source BFS by initializing the queue with all source vertices at distance before the main loop, and to directed graphs by following only out-edges (or only in-edges, to obtain an 'upward' traversal in a DAG).
0
1
Tags
Science
Auditable Strict-Parity Evaluation of Prerequisite-Graph Retrieval for RAG under Leakage Controls
Related
Disciplinary Research
Legal Research
Historical Research
Scientific Research
Research References
Research Methods
Research Philosophy
Research Center
Empirical Research Report
Reference: What Should I Learn First: Introducing LectureBank for NLP Education and Prerequisite Chain Learning
Reference: R-VGAE: Relational-variational Graph Autoencoder for Unsupervised Prerequisite Chain Learning
Reference: ojs.aaai.org
Reference: Prerequisite Relation Learning for Concepts in MOOCs
Reference: Course Prerequisite Relation (MOOC prerequisite dataset release page)
Reference: MOOCCube: A Large-scale Data Repository for NLP Applications in MOOCs
Reference: QASC: A Dataset for Question Answering via Sentence Composition
Reference: QASC: A Dataset for Question Answering via Sentence Composition (arXiv preprint)
Reference: ColBERTv2: Effective and Efficient Retrieval via Lightweight Late Interaction
Reference: ColBERT: Efficient and Effective Passage Search via Contextualized Late Interaction over BERT
Reference: arxiv.org
Reference: arxiv.org
Reference: Introduction to Information Retrieval
Reference: Evaluation measures (information retrieval)
Reference: REPLUG: Retrieval-Augmented Black-Box Language Models
Reference: arxiv.org
Reference: HotpotQA: A Dataset for Diverse, Explainable Multi-hop Question Answering
Reference: HotpotQA: A Dataset for Diverse, Explainable Multi-hop Question Answering (arXiv preprint)
Reference: HotpotQA Official Dataset and Leaderboard
Reference: Dense Passage Retrieval for Open-Domain Question Answering
Reference: Dense Passage Retrieval for Open-Domain Question Answering (arXiv preprint)
LectureBank Dataset
MOOC-CS Prerequisite Benchmark
QASC Question Answering Benchmark
Late-Interaction Neural Retrieval
Recall@k Retrieval Metric
RePlug Retrieval-Augmented Black-Box Language Model
HotpotQA Multi-Hop QA Benchmark
Single-Vector Dense Passage Retrieval
Reference: Retrieval-Augmented Generation for Knowledge-Intensive NLP Tasks
Reference: How Significant Are the Real Performance Gains? An Unbiased Evaluation Framework for GraphRAG
Reference: arxiv.org
Unbiased GraphRAG Evaluation Framework (Zeng et al., 2025)
Reference: RAG vs. GraphRAG: A Systematic Evaluation and Key Insights
Reference: arxiv.org
RAG vs Graph-RAG Controlled Comparison (Han et al., 2025)
Reference: Controlled Retrieval-augmented Context Evaluation for Long-form RAG
Reference: Controlled Retrieval-augmented Context Evaluation for Long-form RAG (ACL Anthology)
CRUX Controlled RAG Context Evaluation (Ju et al., 2025)
Reference: Anytime Heuristic Search
Reference: The Anatomy of a Large-Scale Hypertextual Web Search Engine