普利姆（Prim）算法

加点，选择相邻点中边权最小的

需要两个一维数组，一个存权值，另一个存起始点；

初始化数组；n个顶点n-1条边：找权最小的边，更新数组；释放空间。

void Graph::MST_Prim(char v)
{/*lowwei存储权值，start存储起始顶点例如 顶点g(6)-h(7) 权值 为19则表示为lowwei[7] = 19start[7] = 6*/int* lowwei = new int[m_NumVertex];int* start = new int[m_NumVertex];int k = GetVertexIndex(v);//当前顶点的下标if (k == -1)return;//初始化int i, j;for (i = 0; i < m_NumVertex; ++i){if (i == k)lowwei[i] = 0;//自己到自己权值为0else{lowwei[i] = m_Edge[k][i];}start[i] = k;//所有顶点的开始都是当前顶点k}//生成MSTint min, min_index;//最小权值、最小权值下标for (i = 0; i < m_NumVertex - 1; ++i){min = MAX_WEIGHT;min_index = -1;for (j = 0; j < m_NumVertex; ++j)//找最小权值的边{if (lowwei[j] != 0 && lowwei[j] < min){min = lowwei[j];min_index = j;}}//begin = start[min_index]  end = min_indexcout << m_VertexArr[start[min_index]] << "->" <<m_VertexArr[min_index] << ":" << min << endl;//当前权值最小的下标即为要到的顶点lowwei[min_index] = 0;//表示此顶点已经被选中//从新选中的顶点min_index进行更新lowwei和startfor (j = 0; j < m_NumVertex; ++j){if (lowwei[j] != 0 && m_Edge[min_index][j] < lowwei[j]){lowwei[j] = m_Edge[min_index][j];start[j] = min_index;}}}delete[]lowwei;delete[]start;lowwei = nullptr;start = nullptr;
}