Отличие остовного и взвешенного графа заключается в том, что остовный граф — это связный граф без циклов, между любыми двумя вершинами которого существует единственный путь. 45 Взвешенный граф — это граф, в котором у каждого ребра и/или каждой вершины есть «вес» — некоторое число, которое может обозначать длину пути, его стоимость и т. п.. 4

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

Для остовного графа используются алгоритмы поиска и сортировки данных, а для взвешенного графа — различные алгоритмы оптимизации, например поиск кратчайшего пути. 25