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

1. Создать массив который будет отслеживать, какие вершины уже включены к в каркас
2. Инициализировать все ключи inf. Стартовой вершине присвоить ключ 0.
3. Пока каркас не содержит в себе все вершины:
	a) Выбрать вершину **u** которая ещё не добавлена в каркас
	b) Добавить **u в** массив каркаса
	с) Обновить ключи всех смежных с **u** вершин. 
Чтобы обновить ключи, нужно просмотреть все смежные вершины **v** и если ребро **uv** 
имеет длину меньшую, чем ключ который до этого имела **v** то сделать этот ключ
равным длине ребра **uv**

Алгоритм работающий за O(V^2):
(так как пройти по всем вершинам - O(V) и найти на каждом шаге минимальный - O(V))
// A C program for Prim's Minimum 
// Spanning Tree (MST) algorithm. The program is 
// for adjacency matrix representation of the graph 
#include <limits.h> 
#include <stdbool.h> 
#include <stdio.h> 
// Number of vertices in the graph 
#define V 5 

// A utility function to find the vertex with 
// minimum key value, from the set of vertices 
// not yet included in MST 
int minKey(int key[], bool mstSet[]) 
{ 
	// Initialize min value 
	int min = INT_MAX, min_index; 

	for (int v = 0; v < V; v++) 
		if (mstSet[v] == false && key[v] < min) 
			min = key[v], min_index = v; 

	return min_index; 
} 

// A utility function to print the 
// constructed MST stored in parent[] 
int printMST(int parent[], int graph[V][V]) 
{ 
	printf("Edge \\tWeight\\n"); 
	for (int i = 1; i < V; i++) 
		printf("%d - %d \\t%d \\n", parent[i], i, graph[i][parent[i]]); 
} 

// Function to construct and print MST for 
// a graph represented using adjacency 
// matrix representation 
void primMST(int graph[V][V]) 
{ 
	// Array to store constructed MST 
	int parent[V]; 
	// Key values used to pick minimum weight edge in cut 
	int key[V]; 
	// To represent set of vertices included in MST 
	bool mstSet[V]; 

	// Initialize all keys as INFINITE 
	for (int i = 0; i < V; i++) 
		key[i] = INT_MAX, mstSet[i] = false; 

	// Always include first 1st vertex in MST. 
	// Make key 0 so that this vertex is picked as first vertex. 
	key[0] = 0; 
	parent[0] = -1; // First node is always root of MST 

	// The MST will have V vertices 
	for (int count = 0; count < V - 1; count++) { 
		// Pick the minimum key vertex from the 
		// set of vertices not yet included in MST 
		int u = minKey(key, mstSet); 

		// Add the picked vertex to the MST Set 
		mstSet[u] = true; 

		// Update key value and parent index of 
		// the adjacent vertices of the picked vertex. 
		// Consider only those vertices which are not 
		// yet included in MST 
		for (int v = 0; v < V; v++) 

			// graph[u][v] is non zero only for adjacent vertices of m 
			// mstSet[v] is false for vertices not yet included in MST 
			// Update the key only if graph[u][v] is smaller than key[v] 
			if (graph[u][v] && mstSet[v] == false && graph[u][v] < key[v]) 
				parent[v] = u, key[v] = graph[u][v]; 
	} 

	// print the constructed MST 
	printMST(parent, graph); 
} 

// driver program to test above function 
int main() 
{ 
	/* Let us create the following graph 
		2 3 
	(0)--(1)--(2) 
	| / \\ | 
	6| 8/ \\5 |7 
	| /	 \\ | 
	(3)-------(4) 
			9		 */
	int graph[V][V] = { { 0, 2, 0, 6, 0 }, 
						{ 2, 0, 3, 8, 5 }, 
						{ 0, 3, 0, 0, 7 }, 
						{ 6, 8, 0, 0, 9 }, 
						{ 0, 5, 7, 9, 0 } }; 

	// Print the solution 
	primMST(graph); 

	return 0; 
}

In prim's algorithm for every vertex you have to search for all the adjacent vertices which can be O(n) in worst case and search for minimum among them takes O(n) time. So TC for one vertex will be O(n)+O(n)=O(n). For n vertices TC will be n*O(n)=O(n^2) Поиск минимального ребра