Минимальные остовные деревья позволяют решить задачу, в которой требуется соединить множество точек (города, дома и т.п.) наименьшим объёмом дорожного полотна, проводов и т.п. В главе буду рассматриваться способы поиска минимального остовного дерева

Остовным деревом связного графа G = (V, E) называется подмножество рёбер множества E, которые создают дерево, содержащее все вершины V.

Минимальные остовные деревья - это деревья с минимальной суммой весов рёбер. На след. рисунке слева изображён взвешенный граф (у ребёр есть значения), справа минимальное остовное дерево к нему.

Алгоритм Прима для построения минимального остовного дерева начинает обход с одной вершины и создаёт дерево, добавляя по одному ребру, пока не будут включены все вершины. Доказательство алгоритма Прима основывается на определении остовного дерева, где все вершины связаны и "жадном" выборе.

Листинг 8.4 Реализация алгоритма Прима:

int prim(graph *g, int start) 
{
    int i;                  
    edgenode *p;           
    bool intree[MAXV+1];    
    int distance[MAXV+1];  
    int v;                 
    int w;                  
    int dist;               
    int weight = 0;         

    for (i = 1; i <= g->nvertices; i++) 
    {
        intree[i] = false;
        distance[i] = MAXINT;
        parent[i] = -1;
    }
}