Работа со связными и несвязными графами в прикладных задачах отличается возможностью перемещения между любыми двумя вершинами. 4

В связном графе существует путь между любой парой вершин. 4 В несвязном графе существуют такие пары вершин, между которыми нет пути. 4

Работа со связными графами позволяет, например, решать задачи поиска маршрута на картах, где графы моделируют карту местности и с рёбрами связаны числа (длины дорог или плата за проезд). 1 Также связные графы используются в задачах планирования, когда нужно упорядочить задачи по времени выполнения, и существуют алгоритмы, позволяющие вычислить оптимальный порядок. 12

Работа с несвязными графами предполагает разбиение его на несколько частей (подграфов), каждая из которых будет связной (компонентами связности). 3 Возможно, что некоторые компоненты связности будут состоять всего лишь из одной вершины. 3