Graph - Prim.txt

//Greedy
// Prim deals with vertex as compared to Kruskal dealing with edges
// Can make graph global and avoid passing
const int MAX = 1e4 + 5;
bool marked[MAX];

int prim(int source, vector < pair < int,int > > graph) {
	priority_queue < pair<int,int> , vector<pair<int,int>>, greater<pair<int,int>> > nodes;

	nodes.push(make_pair(0, source));
	int minCost = 0;

	while(!nodes.empty()) {
		// Selecting node with min weight

		pair <int, int> minNode = nodes.front();
		nodes.pop();

		int cost = minNode.first;
		int node = minNode.second;

		//Check if cycle exists
		if(marked[node])
			continue;

		minCost += cost;
		marked[node] = true;

		for(int i=0; i<graph[node].size();i++) {
			int neighborPair = graph[node][i];

			int neighbor = neighborPair.second;

			if(!marked[neighbor]) {
				nodes.push(neighborPair);
			}
		}
	}

	return minCost;
}

int main () {
	cin>>nodes>>edges;
	vector < pair < int,int > > graph[nodes+1];

	for(i=0 to edges) {
		cin>>x>>y>>weight;

		graph[x].push_back(make_pair(weight, y));
		graph[y].push_back(make_pair(weight, x));
	}

	int minimumCost = prim(1, graph);

}