为何普利姆算法输出结果与老师的不一样？

Question

这是我的输出结果

与数据结构课程的不一样

这是我的主函数

int main(void)
{
    CMap *pMap=new CMap(6);
     
    Node *pNodeA=new Node('A');
    Node *pNodeB=new Node('B');
    Node *pNodeC=new Node('C');
    Node *pNodeD=new Node('D');
    Node *pNodeE=new Node('E');
    Node *pNodeF=new Node('F');
 
     
    pMap->addNode(pNodeA);
    pMap->addNode(pNodeB);
    pMap->addNode(pNodeC);
    pMap->addNode(pNodeD);
    pMap->addNode(pNodeE);
    pMap->addNode(pNodeF);
 
     
     
    pMap->setValueToMatrixForUndirectedGraph(0,1,6);
    pMap->setValueToMatrixForUndirectedGraph(0,4,5);
    pMap->setValueToMatrixForUndirectedGraph(0,5,1);
    pMap->setValueToMatrixForUndirectedGraph(1,2,3);
    pMap->setValueToMatrixForUndirectedGraph(1,5,2);
    pMap->setValueToMatrixForUndirectedGraph(2,5,8);
    pMap->setValueToMatrixForUndirectedGraph(2,3,7);
    pMap->setValueToMatrixForUndirectedGraph(3,5,4);
    pMap->setValueToMatrixForUndirectedGraph(3,4,2);
    pMap->setValueToMatrixForUndirectedGraph(4,5,9);
     
    pMap->primTree(0);
 
 
    system("pause");
    return 0;
}

普利姆算法

void CMap::primTree(int nodeIndex)//普利姆生成树
{
    int value=0;//边的权值保存到value中 
    int edgeCount=0;//取出的边数 
    vector<int>nodeVec;//点的索引的集合 
    vector<Edge> edgeVec;//边的集合 
     
    cout<<m_pNodeArray[nodeIndex].m_cData<<endl;
     
    nodeVec.push_back(nodeIndex);
    m_pNodeArray[nodeIndex].m_bIsVisited=true;
    //
    while(edgeCount<m_iCapacity-1)//边数小于m_iCapacity-1则一直要循环 
    {
        int temp= nodeVec.back();//取出nodeIndex，back()函数是取当前数组中尾部的元素
        for(int i=0;i<=m_iCapacity;i++)
        {
            getValueFromMatrix(temp,i,value);
            if(value!=0)
            {
                if(m_pNodeArray[i].m_bIsVisited)
                {
                    continue;
                }
                else
                {
                    Edge edge(temp,i,value);
                    edgeVec.push_back(edge);
                }
            }
        }//所有边放入备选边集合中
         
        //从可选边集合中找出最小的边 
        int edgeIndex=getMinEdge(edgeVec);//找最小权值边的索引 
        edgeVec[edgeIndex].m_bSelected=true;
        //将过程打印出来 
        cout<<edgeVec[edgeIndex].m_iNodeIndexA<<"---"<<edgeVec[edgeIndex].m_iNodeIndexB<<" ";
        cout<<edgeVec[edgeIndex].m_iWeightValue<<endl;
     
        m_pEdge[edgeCount]=edgeVec[edgeIndex]; //保存边 
        edgeCount++;
         
        //nodeVec为点集合 
        int nextNodeIndex=edgeVec[edgeIndex].m_iNodeIndexB;
     
        nodeVec.push_back(nextNodeIndex); 
        m_pNodeArray[nextNodeIndex].m_bIsVisited=true;
        cout<<m_pNodeArray[nextNodeIndex].m_cData<<endl;
    }
}
int CMap::getMinEdge(vector<Edge> edgeVec)
{
    int minWeight=0;//初始化最小权值 
    int edgeIndex=0;
    int i=0;
    for(i=0;i<edgeVec.size();i++)
    {
        if(!edgeVec[i].m_bSelected)
        {
            minWeight=edgeVec[i].m_iWeightValue;
            edgeIndex=i;
            break;//这里需要注意 
        }
    }
     
    if(minWeight==0)
    {
        return -1;
    }
    //判断后面是否还存在最小权值边 
    for(;i<edgeVec.size();i++)
    {
        if(edgeVec[i].m_bSelected)
        {
            continue;
        }
        else
        {
            if(minWeight>edgeVec[i].m_iWeightValue)
            {
                minWeight=edgeVec[i].m_iWeightValue;
                edgeIndex=i;
            }
        }
             
    } 
     
    return edgeIndex;
}

Answer 1

你连下标6都出来了！感觉你的prime算法好复杂！