问题描述

这段代码不知道怎么改，总是改不出来，希望各位帮忙看看

#include
#include
#include
#include
using namespace std;
// 用于存储图的节点及其相邻节点的结构体变量类型
struct SGNode {
int key; // 结点自身标识
map neighNodes; // 与当前结点相邻的结点集合，及其与相邻结点之间路径的权值
};

// 用于存储边的结构体变量类型
struct SGEdge {
int start;
int end;
};

// 用于存储边及其权重的map容器（注意：会按照权重自小而大自动排序）
typedef map EdgeSet;

class CMyGraph
{
public:
CMyGraph(void);
~CMyGraph(void);

public: // 其他函数，供实例调用
void DFS();
void DFS(int i, vector& mystack, bool* visited);
void BFS();
void BFS(int i, deque& mydeque, bool* visited);
void Prim();
void Kruskal();
protected: // 属性变量
/* 自行设计完成 */
private: // 成员变量
vector NodeSet;
};

CMyGraph::CMyGraph(void)
{
float g[8][8] =
{
{0, 12, 1, 0, 0, 0, 0, 4},
{12, 0, 0, 11, 0, 10, 0, 0},
{1, 0, 0, 9, 2, 0, 0, 0},
{0, 11, 9, 0, 0, 0, 8, 0},
{0, 0, 2, 0, 0, 0, 5, 3},
{0, 10, 0, 0, 0, 0, 7, 6},
{0, 0, 0, 8, 5, 7, 0, 0},
{4, 0, 0, 0, 3, 6, 0, 0}
};

for (int i = 0; i < 8; i++)
{
    SGNode sg;
    sg.key = i;

    NodeSet.push_back(sg);
}

for (int i = 0; i < 8; i++)
{
    for (int j = 0; j < 8; j++)
    {
        if (g[i][j] != 0)
        {
            NodeSet[i].neighNodes.insert(map<int, float>::value_type(j, g[i][j]));
        }
    }
}

vector<SGNode>::iterator iter;
for (iter = NodeSet.begin(); iter != NodeSet.end(); iter++)
{
    cout << (*iter).key;
    map<int, float>::iterator iter2;
    for (iter2 = (*iter).neighNodes.begin(); iter2 != (*iter).neighNodes.end(); iter2++)
    {
        cout << ", (" << (*iter2).first << ", " << (*iter2).second << ")";
    }
    cout << endl;
}

}

CMyGraph::~CMyGraph(void)
{
}

void CMyGraph::DFS()
{

bool *visited;
visited = new bool[8];
for (int i = 0; i < 8; i++)
visited[i] = false;
vector mystack;
DFS(0, mystack, visited);
}

void CMyGraph::DFS(int i, vector& mystack, bool * visited)
{
if (i >= 0 && i < NodeSet.size())
{
if (!visited[i])
{
cout << i << "n";
mystack.push_back(i);
visited[i] = true;
}
map::iterator iter;
for (iter = NodeSet[i].neighNodes.begin(); iter != NodeSet[i].neighNodes.end(); iter++)
{
if (!visited[(*iter).first])
DFS((*iter).first, mystack, visited);
}

    if (iter == NodeSet[i].neighNodes.end())
    {
        if (mystack.size() > 0)
        {
            mystack.pop_back();
            if (mystack.size() > 0)
                DFS(mystack.at(mystack.size() - 1), mystack, visited);
        }
    }

}

}

void CMyGraph::BFS()
{
bool *visited;
visited = new bool[8];
for (int i = 0; i < 8; i++)
visited[i] = false;
deque mydeque;
BFS(0, mydeque, visited);
}

void CMyGraph::BFS(int i, deque& mydeque, bool* visited)
{
if (!visited[i])
{
cout << i << "n";
for (map::iterator iter = NodeSet[i].neighNodes.begin();
iter != NodeSet[i].neighNodes.end(); iter++)
{
if (!visited[(*iter).first])
mydeque.push_back((*iter).first);
}
visited[i] = true;
}

while (mydeque.size() > 0)
{
    int i = mydeque.at(0);
    mydeque.pop_front();
    BFS(i, mydeque, visited);
}

}

void CMyGraph::Prim()
{
// 选择图中的任一顶点作为起点
int start = 0;
int s1;
set mtSet;
mtSet.insert(start); // 选择初始节点

float weight;
while (1)
{
    weight = 100000.0f; // 人为设定较大值
    start = -1;
    s1 = -1;
    for (set<int>::iterator iter = mtSet.begin(); iter != mtSet.end(); iter++)
    {
        map<int, float>::iterator curIter = NodeSet[(*iter)].neighNodes.begin();
        while (curIter != NodeSet[(*iter)].neighNodes.end())
        {
            // 当前节点已经在集合中
            if ( mtSet.end() != ( mtSet.find( (*curIter).first ) ) )
            {
                curIter++;
                continue;
            }

            // 当前节点不在集合中，记录该节点并作为备选节点
            if ((*curIter).second < weight) // 选择权重最小的边所边接的节点
            {
                s1 = (*iter);
                start = (*curIter).first;
                weight = (*curIter).second;
            }

            curIter++;
        }
    }

    if (-1 != start)
    {
        // 从备选边与节点加入到最小生成树中
        mtSet.insert(start);
        cout << "(" << s1 << ", " << start << ") " << endl;

        if (mtSet.size() == NodeSet.size())
            break;
    }
}

}

void CMyGraph::Kruskal()
{
// 对所有边进行排序
EdgeSet es;

for (int i = 0; i < NodeSet.size(); i++)
{
    for (map<int, float>::iterator iter = NodeSet[i].neighNodes.begin();
        iter != NodeSet[i].neighNodes.end(); iter++)
    {
        if ((*iter).second != 0.0f)
        {
            SGEdge sg;
            sg.start = i;
            sg.end = (*iter).first;
            es.insert(EdgeSet::value_type( (*iter).second, sg));
        }
    }
}

set<int> mtSet;
// 依次加入权重最小的边（数目：顶点数－1）
EdgeSet::iterator iter = es.begin();
for (int i = 0; i < NodeSet.size() - 1;)
{
    // 初始最小生成树为空的情况
    if (mtSet.size() == 0)
    {
        cout << "(" << (*iter).second.start;
        cout << ", ";
        cout << (*iter).second.end << ")" << endl;

        mtSet.insert((*iter).second.start);
        mtSet.insert((*iter).second.end);
        iter++;
        i++;

        continue;
    }

    // 待加入边的两个端点位于两个不同的子图中
    if ((mtSet.find((*iter).second.start) == mtSet.end() && mtSet.find((*iter).second.end) != mtSet.end()) ||
        (mtSet.find((*iter).second.start) != mtSet.end() && mtSet.find((*iter).second.end) == mtSet.end()))
    {
        cout << "(" << (*iter).second.start;
        cout << ", ";
        cout << (*iter).second.end << ")" << endl;

        mtSet.insert((*iter).second.start);
        mtSet.insert((*iter).second.end);
        iter++;
        i++;
    }
    else
    {
        iter++;
    }
}

}

int main()
{
CMyGraph mg;

cout << "Depth first scanning:" << endl;
mg.DFS();

cout << "Breadth first scanning:" << endl;
mg.BFS();

cout << "Prim:n";
mg.Prim();

cout << "Kruskal:n";
mg.Kruskal();

return 0;

}

解决方案

目测是最小生成树的程序？你要说清楚你要做什么，遇到什么错误。