数据机构探险之图篇（代码编写）
- 图的存储（邻接矩阵） & 图的深度优先 & 广度优先
- 图的编码实战-最小生成树（普里姆算法）
- 图的编码实战-最小生成树之克鲁斯卡尔算法
图的存储（邻接矩阵） & 图的深度优先 & 广度优先
要求
题目
#ifndef NODE_H
#define NODE_H
class Node
{
public:
Node(char data = 0);
char m_cData;//数据值
bool m_bIsVisited;//有没有被访问
};
#endif
#include "Node.h"
Node::Node(char data)
{
m_cData = data;
m_bIsVisited = false;
}
#ifndef CMAP_H
#define CMAP_H
#include "Node.h"
#include <vector>
using namespace std;
class CMap
{
public:
CMap(int capacity);
~CMap();
bool addNode(Node *pNode);
//向图中加入顶点
void resetNode();
//重置顶点
bool setValueToMatrixForDirectedGraph(int row,int col,int val =1);
bool setValueToMatrixForUndirectedGraph(int row, int col, int val = 1);
void printMatrix();
//打印邻接矩阵
void depthFirstTraverse(int nodeIndex);//深度优先遍历
void breadthFirstTraverse(int nodeIndex);//广度优先遍历
private:
bool getValueFromMatrix(int row, int col, int &val);//从矩阵中获取权值
void breadthFirstTraverseImpl(vector<int> preVec);//广度优先遍历实现函数
private:
int m_iCapacity;
//图中最多可以容纳的顶点数
int m_iNodeCount;
//已经添加的顶点（结点）个数
Node *m_pNodeArray;
//用来存放顶点数组
int *m_pMatrix;
//用来存放邻接矩阵
};
#endif
Cmap.cpp:
#include "CMap.h"
#include <iostream>
#include <vector>
#include "Node.h"
using namespace std;
CMap::CMap(int capacity)
{
m_iCapacity = capacity;
m_iNodeCount = 0;
m_pNodeArray = new Node[m_iCapacity];
m_pMatrix = new int[m_iCapacity * m_iCapacity];//邻接矩阵size乘size
//邻接矩阵初始化为全0
//memset(m_pMatrix, 0, m_iCapacity * m_iCapacity * sizeof(int));
//将s所指向的某一块内存中的前n个 字节的内容全部设置为ch指定的ASCII值， 第一个值为指定的内存地址，块的大小由第三个参数指定
for (int i=0;i<m_iCapacity*m_iCapacity;i++)
{
m_pMatrix[i] = 0;
}
}
CMap::~CMap()
{
delete []m_pNodeArray;
delete[]m_pMatrix;
}
bool CMap::addNode(Node *pNode)
{
if (pNode == NULL)
{
return false;
}
//保存节点数据
m_pNodeArray[m_iNodeCount].m_cData = pNode->m_cData;
m_iNodeCount++;
return true;
}
void CMap::resetNode()
{
for (int i = 0; i < m_iNodeCount; i++)
{
m_pNodeArray[i].m_bIsVisited = false;
}
}
bool CMap::setValueToMatrixForDirectedGraph(int row, int col, int val)
{
if (row <0 && row >= m_iCapacity)
{
return false;
}
if (col < 0 && col >= m_iCapacity)
{
return false;
}
m_pMatrix[row*m_iCapacity + col] = val;
return true;
}
bool CMap::setValueToMatrixForUndirectedGraph(int row, int col, int val)
{
if (row < 0 && row >= m_iCapacity)
{
return false;
}
if (col < 0 && col >= m_iCapacity)
{
return false;
}
m_pMatrix[row*m_iCapacity + col] = val;
m_pMatrix[col*m_iCapacity + row] = val;
return true;
}
bool CMap::getValueFromMatrix(int row, int col, int &val)
{
if (row < 0 && row >= m_iCapacity)
{
return false;
}
if (col < 0 && col >= m_iCapacity)
{
return false;
}
val = m_pMatrix[row * m_iCapacity + col];
return true;
}
void CMap::printMatrix()
{
//两重循环（i行k列）
for (int i=0;i<m_iCapacity;i++)
{
for (int k=0;k<m_iCapacity;k++)
{
cout << m_pMatrix[i*m_iCapacity + k] << " ";
}
cout << endl;
}
}
//深度优先
void CMap::depthFirstTraverse(int nodeIndex)
{
//访问根左右。与先序遍历类似。把子树延展的所有节点访问完回到根
int value = 0;
cout << m_pNodeArray[nodeIndex].m_cData << " ";
m_pNodeArray[nodeIndex].m_bIsVisited = true;
//通过邻接矩阵判断是否与其他的顶点有连接
for (int i=0;i<m_iCapacity;i++)
{
//取出相应的弧
getValueFromMatrix(nodeIndex, i, value);
if (value !=0)//判断有弧连接其他顶点
{
if (m_pNodeArray[i].m_bIsVisited)
{
continue;
}
else
{
depthFirstTraverse(i);
}
}
else
{
continue;
}
}
}
//每一层放在一个数组中
void CMap::breadthFirstTraverse(int nodeIndex)
{
cout << m_pNodeArray[nodeIndex].m_cData << " ";
m_pNodeArray[nodeIndex].m_bIsVisited = true;
//将节点索引保存到数组中
vector<int> curVec;
curVec.push_back(nodeIndex);
breadthFirstTraverseImpl(curVec);
}
void CMap::breadthFirstTraverseImpl(vector<int> preVec)
{
int value = 0;
vector<int> curVec;
//prevec为上一层节点
for (int j = 0; j < (int)preVec.size(); j++)
{
for (int i=0;i<m_iCapacity;i++)
{
getValueFromMatrix(preVec[j], i, value);
if (value != 0)
{
if (m_pNodeArray[i].m_bIsVisited)
{
continue;
}
else
{
cout << m_pNodeArray[i].m_cData << " ";
m_pNodeArray[i].m_bIsVisited = true;
curVec.push_back(i);
}
}
}
}
if (curVec.size() == 0)
{
return;
}
else
{
breadthFirstTraverseImpl(curVec);
}
}
main.cpp:
#include "CMap.h"
#include <stdlib.h>
#include "Node.h"
#include <iostream>
using namespace std;
int main()
{
CMap *pMap = new CMap(8);
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');
Node *pNodeG = new Node('G');
Node *pNodeH = new Node('H');
pMap->addNode(pNodeA);
pMap->addNode(pNodeB);
pMap->addNode(pNodeC);
pMap->addNode(pNodeD);
pMap->addNode(pNodeE);
pMap->addNode(pNodeF);
pMap->addNode(pNodeG);
pMap->addNode(pNodeH);
pMap->setValueToMatrixForUndirectedGraph(0, 1);
pMap->setValueToMatrixForUndirectedGraph(0, 3);
pMap->setValueToMatrixForUndirectedGraph(1, 2);
pMap->setValueToMatrixForUndirectedGraph(1, 5);
pMap->setValueToMatrixForUndirectedGraph(3, 6);
pMap->setValueToMatrixForUndirectedGraph(3, 7);
pMap->setValueToMatrixForUndirectedGraph(6, 7);
pMap->setValueToMatrixForUndirectedGraph(2, 4);
pMap->setValueToMatrixForUndirectedGraph(4, 5);
pMap->printMatrix();
cout << endl;
pMap->resetNode();
//指定起始点的索引
pMap->depthFirstTraverse(0);
cout << endl;
pMap->resetNode();
pMap->breadthFirstTraverse(0);
cout << endl;
system("pause");
return 0;
}
运行结果：
运行结果
图的编码实战-最小生成树（普里姆算法）
例子
边与边之间存在权值。如a-b 为6
edge.h&cpp:
#ifndef EDGE_H
#define EDGE_H
class Edge
{
public:
Edge(int nodeIndexA = 0, int nodeIndexB = 0,int weightValue = 0);
int m_iNodeIndexA;
int m_iNodeIndexB;
int m_iWeightValue;
//标记已经挑出来的边
bool m_bSelected;
};
#endif
#include "Edge.h"
Edge::Edge(int nodeIndexA, int nodeIndexB, int weightValue)
{
m_iNodeIndexA = nodeIndexA;
m_iNodeIndexB = nodeIndexB;
m_iWeightValue = weightValue;
m_bSelected = false;
}
node.h&cpp:
#ifndef NODE_H
#define NODE_H
class Node
{
public:
Node(char data = 0);
char m_cData;//数据值
bool m_bIsVisited;//有没有被访问
};
#endif
#include "Node.h"
Node::Node(char data)
{
m_cData = data;
m_bIsVisited = false;
}
cmap.h & cpp:
#ifndef CMAP_H
#define CMAP_H
#include "Node.h"
#include <vector>
#include "Edge.h"
using namespace std;
class CMap
{
public:
CMap(int capacity);
~CMap();
bool addNode(Node *pNode);
//向图中加入顶点
void resetNode();
//重置顶点
bool setValueToMatrixForDirectedGraph(int row,int col,int val =1);
bool setValueToMatrixForUndirectedGraph(int row, int col, int val = 1);
void printMatrix();
//打印邻接矩阵
void depthFirstTraverse(int nodeIndex);//深度优先遍历
void breadthFirstTraverse(int nodeIndex);//广度优先遍历
void primTree(int nodeIndex); //普里姆生成树指定的第一个点，找出与他相连的最小边
private:
bool getValueFromMatrix(int row, int col, int &val);//从矩阵中获取权值
void breadthFirstTraverseImpl(vector<int> preVec);//广度优先遍历实现函数
int getMinEdge(vector<Edge> edgeVec);
private:
int m_iCapacity;
//图中最多可以容纳的顶点数
int m_iNodeCount;
//已经添加的顶点（结点）个数
Node *m_pNodeArray;
//用来存放顶点数组
int *m_pMatrix;
//用来存放邻接矩阵
Edge *m_pEdge;
};
#endif
#include "CMap.h"
#include <iostream>
#include <vector>
#include "Node.h"
using namespace std;
CMap::CMap(int capacity)
{
m_iCapacity = capacity;
m_iNodeCount = 0;
m_pNodeArray = new Node[m_iCapacity];
m_pMatrix = new int[m_iCapacity * m_iCapacity];//邻接矩阵size乘size
//邻接矩阵初始化为全0
//memset(m_pMatrix, 0, m_iCapacity * m_iCapacity * sizeof(int));
//将s所指向的某一块内存中的前n个 字节的内容全部设置为ch指定的ASCII值， 第一个值为指定的内存地址，块的大小由第三个参数指定
for (int i=0;i<m_iCapacity*m_iCapacity;i++)
{
m_pMatrix[i] = 0;
}
m_pEdge = new Edge[m_iCapacity - 1];
}
CMap::~CMap()
{
delete []m_pNodeArray;
delete[]m_pMatrix;
}
bool CMap::addNode(Node *pNode)
{
if (pNode == NULL)
{
return false;
}
//保存节点数据
m_pNodeArray[m_iNodeCount].m_cData = pNode->m_cData;
m_iNodeCount++;
return true;
}
void CMap::resetNode()
{
for (int i = 0; i < m_iNodeCount; i++)
{
m_pNodeArray[i].m_bIsVisited = false;
}
}
bool CMap::setValueToMatrixForDirectedGraph(int row, int col, int val)
{
if (row <0 && row >= m_iCapacity)
{
return false;
}
if (col < 0 && col >= m_iCapacity)
{
return false;
}
m_pMatrix[row*m_iCapacity + col] = val;
return true;
}
bool CMap::setValueToMatrixForUndirectedGraph(int row, int col, int val)
{
if (row < 0 && row >= m_iCapacity)
{
return false;
}
if (col < 0 && col >= m_iCapacity)
{
return false;
}
m_pMatrix[row*m_iCapacity + col] = val;
m_pMatrix[col*m_iCapacity + row] = val;
return true;
}
bool CMap::getValueFromMatrix(int row, int col, int &val)
{
if (row < 0 && row >= m_iCapacity)
{
return false;
}
if (col < 0 && col >= m_iCapacity)
{
return false;
}
val = m_pMatrix[row * m_iCapacity + col];
return true;
}
void CMap::printMatrix()
{
//两重循环（i行k列）
for (int i=0;i<m_iCapacity;i++)
{
for (int k=0;k<m_iCapacity;k++)
{
cout << m_pMatrix[i*m_iCapacity + k] << " ";
}
cout << endl;
}
}
//深度优先
void CMap::depthFirstTraverse(int nodeIndex)
{
//访问根左右。与先序遍历类似。把子树延展的所有节点访问完回到根
int value = 0;
cout << m_pNodeArray[nodeIndex].m_cData << " ";
m_pNodeArray[nodeIndex].m_bIsVisited = true;
//通过邻接矩阵判断是否与其他的顶点有连接
for (int i=0;i<m_iCapacity;i++)
{
//取出相应的弧
getValueFromMatrix(nodeIndex, i, value);
if (value !=0)//判断有弧连接其他顶点
{
if (m_pNodeArray[i].m_bIsVisited)
{
continue;
}
else
{
depthFirstTraverse(i);
}
}
else
{
continue;
}
}
}
//每一层放在一个数组中
void CMap::breadthFirstTraverse(int nodeIndex)
{
cout << m_pNodeArray[nodeIndex].m_cData << " ";
m_pNodeArray[nodeIndex].m_bIsVisited = true;
//将节点索引保存到数组中
vector<int> curVec;
curVec.push_back(nodeIndex);
breadthFirstTraverseImpl(curVec);
}
void CMap::breadthFirstTraverseImpl(vector<int> preVec)
{
int value = 0;
vector<int> curVec;
//prevec为上一层节点
for (int j = 0; j < (int)preVec.size(); j++)
{
for (int i=0;i<m_iCapacity;i++)
{
getValueFromMatrix(preVec[j], i, value);
if (value != 0)
{
if (m_pNodeArray[i].m_bIsVisited)
{
continue;
}
else
{
cout << m_pNodeArray[i].m_cData << " ";
m_pNodeArray[i].m_bIsVisited = true;
curVec.push_back(i);
}
}
}
}
if (curVec.size() == 0)
{
return;
}
else
{
breadthFirstTraverseImpl(curVec);
}
}
//普利姆生成树
void CMap::primTree(int nodeIndex) {
//取边存权值
int value = 0;
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;
//什么时候停下来，边数等于点数-1时
while (edgeCount < m_iCapacity - 1)
{
int temp = nodeVec.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++;
//找到与当前边连接的点
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<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;
}
main.cpp:
#include "CMap.h"
#include <stdlib.h>
#include "Node.h"
#include <iostream>
using namespace std;
int main()
{
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;
}
运行结果：
运行结果
图的编码实战-最小生成树之克鲁斯卡尔算法
题目
- 找出所有的边
- 在边中找到最小生成树的集合
node.cpp&h edge.cpp&h与上面的一样
cmap.h&cpp
#ifndef CMAP_H
#define CMAP_H
#include "Node.h"
#include <vector>
#include "Edge.h"
using namespace std;
class CMap
{
public:
CMap(int capacity);
~CMap();
bool addNode(Node *pNode);
//向图中加入顶点
void resetNode();
//重置顶点
bool setValueToMatrixForDirectedGraph(int row,int col,int val =1);
bool setValueToMatrixForUndirectedGraph(int row, int col, int val = 1);
void printMatrix();
//打印邻接矩阵
void depthFirstTraverse(int nodeIndex);//深度优先遍历
void breadthFirstTraverse(int nodeIndex);//广度优先遍历
void primTree(int nodeIndex); //普里姆生成树指定的第一个点，找出与他相连的最小边
void kruskalTree();//克鲁斯卡尔算法生成树
private:
bool getValueFromMatrix(int row, int col, int &val);//从矩阵中获取权值
void breadthFirstTraverseImpl(vector<int> preVec);//广度优先遍历实现函数
bool isInSet(vector<int> nodeSet, int target); //判断顶点是否在点集合中
void mergeNodeSet(vector<int> &nodeSetA, vector<int> nodeSetB);//合并两个点集合
int getMinEdge(vector<Edge> edgeVec);
private:
int m_iCapacity;
//图中最多可以容纳的顶点数
int m_iNodeCount;
//已经添加的顶点（结点）个数
Node *m_pNodeArray;
//用来存放顶点数组
int *m_pMatrix;
//用来存放邻接矩阵
Edge *m_pEdge;
};
#endif
#include "CMap.h"
#include <iostream>
#include <vector>
#include "Node.h"
using namespace std;
CMap::CMap(int capacity)
{
m_iCapacity = capacity;
m_iNodeCount = 0;
m_pNodeArray = new Node[m_iCapacity];
m_pMatrix = new int[m_iCapacity * m_iCapacity];//邻接矩阵size乘size
//邻接矩阵初始化为全0
//memset(m_pMatrix, 0, m_iCapacity * m_iCapacity * sizeof(int));
//将s所指向的某一块内存中的前n个 字节的内容全部设置为ch指定的ASCII值， 第一个值为指定的内存地址，块的大小由第三个参数指定
for (int i=0;i<m_iCapacity*m_iCapacity;i++)
{
m_pMatrix[i] = 0;
}
m_pEdge = new Edge[m_iCapacity - 1];
}
CMap::~CMap()
{
delete []m_pNodeArray;
delete[]m_pMatrix;
delete[]m_pEdge;
}
bool CMap::addNode(Node *pNode)
{
if (pNode == NULL)
{
return false;
}
//保存节点数据
m_pNodeArray[m_iNodeCount].m_cData = pNode->m_cData;
m_iNodeCount++;
return true;
}
void CMap::resetNode()
{
for (int i = 0; i < m_iNodeCount; i++)
{
m_pNodeArray[i].m_bIsVisited = false;
}
}
bool CMap::setValueToMatrixForDirectedGraph(int row, int col, int val)
{
if (row <0 && row >= m_iCapacity)
{
return false;
}
if (col < 0 && col >= m_iCapacity)
{
return false;
}
m_pMatrix[row*m_iCapacity + col] = val;
return true;
}
bool CMap::setValueToMatrixForUndirectedGraph(int row, int col, int val)
{
if (row < 0 && row >= m_iCapacity)
{
return false;
}
if (col < 0 && col >= m_iCapacity)
{
return false;
}
m_pMatrix[row*m_iCapacity + col] = val;
m_pMatrix[col*m_iCapacity + row] = val;
return true;
}
bool CMap::getValueFromMatrix(int row, int col, int &val)
{
if (row < 0 && row >= m_iCapacity)
{
return false;
}
if (col < 0 && col >= m_iCapacity)
{
return false;
}
val = m_pMatrix[row * m_iCapacity + col];
return true;
}
void CMap::printMatrix()
{
//两重循环（i行k列）
for (int i=0;i<m_iCapacity;i++)
{
for (int k=0;k<m_iCapacity;k++)
{
cout << m_pMatrix[i*m_iCapacity + k] << " ";
}
cout << endl;
}
}
//深度优先
void CMap::depthFirstTraverse(int nodeIndex)
{
//访问根左右。与先序遍历类似。把子树延展的所有节点访问完回到根
int value = 0;
cout << m_pNodeArray[nodeIndex].m_cData << " ";
m_pNodeArray[nodeIndex].m_bIsVisited = true;
//通过邻接矩阵判断是否与其他的顶点有连接
for (int i=0;i<m_iCapacity;i++)
{
//取出相应的弧
getValueFromMatrix(nodeIndex, i, value);
if (value !=0)//判断有弧连接其他顶点
{
if (m_pNodeArray[i].m_bIsVisited)
{
continue;
}
else
{
depthFirstTraverse(i);
}
}
else
{
continue;
}
}
}
//每一层放在一个数组中
void CMap::breadthFirstTraverse(int nodeIndex)
{
cout << m_pNodeArray[nodeIndex].m_cData << " ";
m_pNodeArray[nodeIndex].m_bIsVisited = true;
//将节点索引保存到数组中
vector<int> curVec;
curVec.push_back(nodeIndex);
breadthFirstTraverseImpl(curVec);
}
void CMap::breadthFirstTraverseImpl(vector<int> preVec)
{
int value = 0;
vector<int> curVec;
//prevec为上一层节点
for (int j = 0; j < (int)preVec.size(); j++)
{
for (int i=0;i<m_iCapacity;i++)
{
getValueFromMatrix(preVec[j], i, value);
if (value != 0)
{
if (m_pNodeArray[i].m_bIsVisited)
{
continue;
}
else
{
cout << m_pNodeArray[i].m_cData << " ";
m_pNodeArray[i].m_bIsVisited = true;
curVec.push_back(i);
}
}
}
}
if (curVec.size() == 0)
{
return;
}
else
{
breadthFirstTraverseImpl(curVec);
}
}
//普利姆生成树
void CMap::primTree(int nodeIndex) {
//取边存权值
int value = 0;
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;
//什么时候停下来，边数等于点数-1时
while (edgeCount < m_iCapacity - 1)
{
int temp = nodeVec.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++;
//找到与当前边连接的点
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<(int)edgeVec.size();i++)
{
if (!edgeVec[i].m_bSelected)
{
//该边还没有被选过
minWeight = edgeVec[i].m_iWeightValue;
edgeIndex = i;
break;//找到第一条边迅速跳出循环
}
}
if (minWeight == 0)
{
return -1;
}
for ( ;i<(int)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;
}
//克鲁斯卡尔算法生成树
void CMap::kruskalTree()
{
int value = 0;//用来取权值的
int edgeCount = 0;
//定义存放结点集合的数组
vector<vector<int>> nodeSets;
//点的集合不止一个
//第一步取出所有边
vector<Edge> edgeVec;
for (int i=0;i<m_iCapacity;i++)
{
for (int k=i+1;k<m_iCapacity;k++)
{
//取出上半个三角的值
getValueFromMatrix(i, k, value);
if (value!=0)
{
Edge edge(i, k, value);
edgeVec.push_back(edge);
}
}
}
//第二步：从所有边中取出最小生成树的边
//1. 找到算法的结束条件（边数等于顶点数-1）
while (edgeCount <m_iCapacity-1)
{
//2. 从边集合中找到最小边（最小边的点）
int minEdgeIndex = getMinEdge(edgeVec);
edgeVec[minEdgeIndex].m_bSelected = true;
//3. 找出最小边连接的点
int nodeAIndex = edgeVec[minEdgeIndex].m_iNodeIndexA;
int nodeBIndex = edgeVec[minEdgeIndex].m_iNodeIndexB;
bool nodeAIsInSet = false;
bool nodeBIsInSet = false;
int nodeAInSetLabel = -1;
int nodeBInSetLabel = -1;
//4. 找出点所在的点集合
for (int i = 0; i <(int)nodeSets.size(); i++)
{
nodeAIsInSet = isInSet(nodeSets[i],nodeAIndex);
if (nodeAIsInSet)
{
//保存i的值
nodeAInSetLabel = i;
}
}
for (int i = 0; i < (int)nodeSets.size(); i++)
{
nodeBIsInSet = isInSet(nodeSets[i], nodeBIndex);
if (nodeBIsInSet)
{
//保存i的值
nodeBInSetLabel = i;
}
}
//5. 根据点所在集合的不同做出不同处理
if (nodeAInSetLabel == -1 && nodeBInSetLabel == -1)
{
vector<int> vec;
vec.push_back(nodeAIndex);
vec.push_back(nodeBIndex);
nodeSets.push_back(vec);
}
else if (nodeAInSetLabel == -1 && nodeBInSetLabel !=-1)
{
//此时a不在任何一个集合中。而nodeB已经在某一集合中
//因为nodea&b为一边的两点。所有将a也加入b的集合
nodeSets[nodeBInSetLabel].push_back(nodeAIndex);
}
else if (nodeAInSetLabel != -1 && nodeBInSetLabel == -1)
{
//此时b不在任何一个集合中。而nodeA已经在某一集合中
//因为nodea&b为一边的两点。所有将b也加入a的集合
nodeSets[nodeAInSetLabel].push_back(nodeBIndex);
}
else if (nodeAInSetLabel != -1 && nodeBInSetLabel != -1 && nodeAInSetLabel != nodeBInSetLabel)
{
//两者在两个不同的集合中，将集合合并
mergeNodeSet(nodeSets[nodeAInSetLabel], nodeSets[nodeBInSetLabel]);
for (int k = nodeBInSetLabel;k<(int)nodeSets.size()-1;k++)
{
//相当于删除了一个节点后面的都向前挪一位
nodeSets[k] = nodeSets[k + 1];
}
}
else if(nodeAInSetLabel != -1 && nodeBInSetLabel != -1 && nodeAInSetLabel == nodeBInSetLabel)
{
//两个都不等于-1.相等还在同一个集合中。
continue;
}
m_pEdge[edgeCount] = edgeVec[minEdgeIndex];
edgeCount++;
cout << edgeVec[minEdgeIndex].m_iNodeIndexA << "---" << edgeVec[minEdgeIndex].m_iNodeIndexB << " ";
cout << edgeVec[minEdgeIndex].m_iWeightValue << endl;
}
}
bool CMap::isInSet(vector<int> nodeSet, int target)
{
//参数一点的集合。参数二点的索引
for (int i=0;i<(int)nodeSet.size();i++)
{
if (nodeSet[i] == target)
{
return true;
}
}
return false;
}
void CMap::mergeNodeSet(vector<int> &nodeSetA, vector<int> nodeSetB)
{
for (int i=0;i<(int)nodeSetB.size();i++)
{
//合并就是将b的点依次加到a的后面
nodeSetA.push_back(nodeSetB[i]);
}
}
main.cpp:
#include "CMap.h"
#include <stdlib.h>
#include "Node.h"
#include <iostream>
using namespace std;
int main()
{
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);
pMap->kruskalTree();
system("pause");
return 0;
}
运行结果：
运行结果
网友评论