Обходы графов, реализуемые итерационными методами решения систем линейных уравнений

Обходы графов используются для решения многих задач. Обычные варианты обхода графа — это поиск в глубину и в ширину. При обходе связного графа последовательно достигаются все его вершины в результате переходов по рёбрам. Поиск в ширину — обычный выбор при построении эффективных алгоритмов нахождения компонент связности графа. Методы простой итерации для решения систем линейных алгебраических уравнений с модифицированными матрицами смежности графов и заданной правой частью могут быть рассмотрены как алгоритмы обхода графа. Эти алгоритмы дают обходы, вообще говоря, отличные от обходов графа в глубину и в ширину. Примером такого алгоритма является алгоритм обхода графа, который даёт метод Гаусса — Зейделя. Для произвольного связного графа этому алгоритму требуется количество итераций не большее, чем для обхода в ширину. Для большого количества индивидуальных задач достаточно меньшего числа итераций.