#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;
}