五、請使用 Prim 演算法找出下圖的最小生成樹（Minimum Spanning Tree），起始點為節點 a，請將搜尋結果畫出來。（15 分）

// Number of vertices in the graph
#define V 6

// Function to find the vertex with minimum key value, from the set of vertices not yet included in MST
int minKey(std::vector<int>& key, std::vector<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;
}

// Function to print the constructed MST stored in parent[]
void printMST(std::vector<int>& parent, int graph[V][V]) {
std::cout<<“Edge \tWeight\n”;
for (int i = 1; i < V; i++)
std::cout<<char(parent[i] + ‘a’)<<” – “<<char(i + ‘a’)<<” \t”<<graph[i][parent[i]]<<” \n”;
}

// 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
std::vector<int> parent(V);
// Key values used to pick minimum weight edge in cut
std::vector<int> key(V, INT_MAX);
// To represent set of vertices not yet included in MST
std::vector<bool> mstSet(V, false);

// Always include first 1st vertex in MST.
key[0] = 0;     // Make key 0 so that this vertex is picked as first vertex
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.
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);
}

int main() {
/* Let us create the following graph
2    3
(a)–(b)–(c)
|   / \   |
6| 8/   \5 |7
| /     \ |
(d)——-(e)
9          */

int graph[V][V] = {
{0, 3, 2, 0, 0, 11},
{3, 0, 2, 4, 4, 0},
{2, 2, 0, 9, 5, 3},
{0, 4, 9, 0, 6, 0},
{0, 4, 5, 9, 0, 8},
{11, 0, 3, 0, 8, 0},
};

// Print the solution
primMST(graph);

return 0;
}