Работа всякого алгоритма обхода графа состоит в последовательном посещении вершин и исследовании ребер. Какие именно действия выполняются при посещении вершины и исследовании ребра - зависит от конкретной задачи, для решения которой производится обход. В любом случае, однако, факт посещения вершины запоминается, так что с момента посещения и до конца работы алгоритма она считается посещенной. Вершину, которая еще не посещена, будем называть новой. В результате посещения вершина становится открытой и остается такой, пока не будут исследованы все инцидентные ей ребра. После этого она превращается в закрытую. Идея поиска в ширину состоит в том, чтобы посещать вершины в порядке их удаленности от некоторой заранее выбранной или указанной стартовой вершины α. Иначе говоря, сначала посещается сама вершина α, затем все вершины, смежные с α, то есть находящиеся от нее на расстоянии 1, затем вершины, находящиеся от α на расстоянии 2, и т.д. Основная особенность поиска в ширину, отличающая его от других способов обхода графов, состоит в том, что в качестве активной вершины выбирается та из открытых, которая была посещена раньше других. Именно этим обеспечивается главное свойство поиска в ширину: чем ближе вершина к старту, тем раньше она будет посещена. Для реализации такого правила выбора активной вершины удобно использовать для хранения множества открытых вершин очередь - когда новая вершина становится открытой, она добавляется в конец очереди, а активная выбирается в ее начале. Схематически процесс изменения статуса вершин изображен на рисунке. Черным кружком обозначена активная вершина.
Если компонента связности единственная в графе, то пройденные ребра образуют
остовное дерево.
Если граф состоит из более чем одной компоненты связности, то следует повторить процесс для каждой стартовой вершины, оставшейся "новой" после предыдущего прохода алгоритма. В результате будет получен остовный лес.