本文共 1991 字，大约阅读时间需要 6 分钟。

再次推荐B站视频的数据结构，讲的非常通俗易懂。结合了“大话数据结构”用C++实现了相关代码；

#include
   
    #include
    
     using namespace std;struct Graph {
   	vector
     
      
       > arc;	vector
       
         vexs;	int numVexter;	int numEdge;	Graph(){
   }	Graph(int m, int n) {
   		numVexter = m;		numEdge = n;		arc = vector
        
         
          >(m, vector
          
           (m, INT_MAX)); vexs = vector
           
            (m); }};class Solution { private: int findIndex(char x, vector
            
             & s) { for (int i = 0; i < s.size(); i++) if (s[i] == x) return i; return -1; }public: Graph* CreatGraph() { int vexter, edge; cout << "Input vexter and edge number: " << endl; cin >> vexter >> edge; Graph* G = new Graph(vexter, edge); cout << "Input vexter char: " << endl; for (int i = 0; i < G->numVexter; i++) cin >> G->vexs[i]; cout << "Input vexter and the weight: " << endl; for (int k = 0; k < G->numEdge; k++) { char x, y; int weight; cin >> x >> y >> weight; int i = findIndex(x, G->vexs); int j = findIndex(y, G->vexs); _ASSERT(i >= 0 && j >= 0); G->arc[i][j] = weight; //如果对于无向网，则下一条语句不要忘记，对称的 G->arc[j][i] = weight; } return G; } void MiniSpanTree(Graph* G) { //用于存储目前lowcost数组中该位置的数的节点编号 vector
             
               adjvex(G->numVexter, 0); //用于存储动态更新的过程中最小的价值 vector
              
                lowcost(G->numEdge, 0); //lowcost的初始化 for (int i = 0; i < G->numVexter; i++) lowcost[i] = G->arc[0][i]; lowcost[0] = 0; cout << "The mini span tree path is: " << endl; for (int i = 1; i < G->numVexter; i++) { int min = INT_MAX; int k = 0; //找到最小的代价值，index为下一个加入最小生成树的节点 for (int j = 0; j < G->numVexter; j++) { if (lowcost[j] != 0 && min > lowcost[j]) { min = lowcost[j]; k = j; } } //输出的最小生成树的节点和路径 cout << "(" << G->vexs[adjvex[k]] << "->" << G->vexs[k] << ") " << G->arc[adjvex[k]][k] << endl; lowcost[k] = 0; //更新lowcost的值 for (int j = 0; j < G->numVexter; j++) { if (lowcost[j] != 0 && lowcost[j] > G->arc[k][j]) { lowcost[j] = G->arc[k][j]; adjvex[j] = k; } } } }};int main() { Solution sol; Graph* G = new Graph(); G =sol.CreatGraph(); sol.MiniSpanTree(G); return 0;}
              
             
            
           
          
         
        
       
      
     
    
   

转载地址：http://ptyci.baihongyu.com/