数据结构-图(c++)
图在数据结构中有重要作用
·
文章目录
前言
本文简单介绍了图的相关概念，介绍了图的存储、遍历相关方法，重点在于对无向图的存储、遍历、以及最小生成树相关的算法进行了编码和原理的详细解释。篇幅有限，代码仅仅实现了以邻接矩阵作为图数据的连接方式，其他方式仅仅讲述了原理。
1.01^3 * 0.99^2 = 1.0097980101 < 1.01
三天打鱼两天晒网，终将一无所获
1、什么是图？
在计算机科学中，一个图就是一些顶点的集合，这些顶点通过一系列边结对（连接）。顶点用圆圈表示，边就是这些圆圈之间的连线。顶点之间通过边连接。简言之，图是由节点以及它们之间的连线的集合，根据连线的不同又分为有向图和无向图。
2、为什么要使用图？
事实证明图是一种有用的数据结构。
如果你有一个编程问题可以通过顶点和边表示出来，那么你就可以将你的问题用图画出来，然后使用著名的图算法（比如广度优先搜索 或者 深度优先搜索）来找到解决方案。
例如，假设你有一系列任务需要完成，但是有的任务必须等待其他任务完成后才可以开始。你可以通过非循环有向图来建立模型：
每一个顶点代表一个任务。两个任务之间的边表示目的任务必须等到源任务完成后才可以开始。比如，在任务B和任务D都完成之前，任务C不可以开始。在任务A完成之前，任务A和D都不能开始。
现在这个问题就通过图描述清楚了，你可以使用深度优先搜索算法来执行执行拓扑排序。这样就可以将所有的任务排入最优的执行顺序，保证等待任务完成的时间最小化。
不管是什么时候遇到困难的编程问题，问一问自己：“如何用图来表述这个问题？”。图都是用于表示数据之间的关系。 诀窍在于如何定义“关系”。
3、无向图相关概念
4、有向图相关概念
节点在图中书面称为顶点，而顶点之间的连线，有向图中称为弧，无向图中称为边
而弧根据箭头指向，又有弧头和弧尾。 出度是当前顶点指出去的弧的条数，反之，入度则是指向当前顶点的弧的条数。
弧上的数据用权值表示。
5、连通图
图中从一个顶点到达另一顶点，若存在至少一条路径，则称这两个顶点是连通着的。无向图中，如果任意两个顶点之间都能够连通，则称此无向图为连通图。
6、完全图
完全图是一个每对不同的顶点之间都恰连有一条边相连的图。
a、无向完全图
b、有向完全图
7、图的应用
路径规划：这里简单举例，比如顶点表示每个城市，权值表示每个城市之间搭建电缆的费用，这样，我们通过最小生成树算法能求出最节约成本的路。
工程规划。。。 战略规划。。。
8、邻接矩阵原理
a、有向图邻接矩阵原理
v1弧头指向了v2、v3、v4，因此值为1
而
v2到v1和其他顶点都没有弧 所以v2的一行全为0
v3只有到v4有弧，记为1，其他为0
v4只有到v1有弧，记为1，其他为0
注：
顶点自身和自身置为0表示
v1-v1 0
v2-v2 0
v3-v3 0
v4-v4 0
b、无向图邻接矩阵原理
无向图的邻接矩阵存在对称，由此可见，我们在使用无向图邻接矩阵时，在内存中可以只保存上三角或者下三角部分。
c、邻接矩阵在代码中的描述
在图（map）中，包括所有的顶点和邻接矩阵，邻接矩阵用于记录边和弧病描述顶点之间的关系。
9、邻接表–链式存储原理（有向图）
由上图我们知道
顶点表示方法为：
顶点索引、出弧链表头指针、顶点数据
顶点索引：是自己定义的不同的字符或者数字，
出弧链表头指针：我们以v1为例，v1顶点有三条出弧，分别指向v2、v3、v4，因此这里的出弧链表头指针，表示的是指向这三条弧，分别是指向v2、v3、v4，至于头指针具体指向谁这取决于v2、v3、v4谁更早被创建，当然既然叫出弧链表头指针，那也就是说在弧的数据结构中我们保存着一个next指针也就是下一条弧指针，那这个指针肯定是把v2、v3、v4以链表的形式连续指向的。
顶点数据：就是我们自定义的数据。
弧的表示方法为
弧头顶点索引、下一条弧指针、弧数据
弧头顶点索引：同样的，也是是自己定义的不同的字符或者数字，以v1到v2的这条弧为例，弧头顶点索引，那也就是v2的索引。
下一条弧指针：以链表形式存储的next指针。
弧数据：这里的弧数据就是我们常常画在弧上的表示路径的权值。
可分析出下图在程序中的表示
我们假设v1、v2、v3、v4的索引分别为0、1、2、3，
对于v1顶点，顶点索引为0，出弧链表头指针我们指向a这条弧，而a这条弧记录了弧头顶点索引为1，那也就是v2，同时a这条弧的下一条弧指针指向了b这条弧，而b这条弧保存了弧头顶点索引为2，也就是顶点v3，同理b这条弧又指向了c这条弧，而我们知道，v1顶点的出弧总共就三条，因此最后c的next指向了null，至此，v1的出弧顶点就全部找到了。
对于v2顶点，由图我们知道v2是没有出弧的，因此v2的出弧链表头指针就是null。
对于v3顶点，由图我们知道v3顶点是有一条出弧指向v4的，因此，我们将v3顶点的出弧链表头指针指向d这条弧，而d这条弧保存了顶点索引3，也就是v4顶点，因此达到了我们目的。
对于v4顶点，也是同理，v4顶点中保存了e这条弧指针，而e这条弧指针保存了v1顶点的索引。
行进至此，我们就通过顶点、在顶点中包含弧的方式表示出了这个图。
在代码中对应的数据结构如下：
同时，逆邻接表，顶点中就应该记录入弧链表头指针，而弧中的弧头顶点索引就改为弧尾顶点索引。
10、十字链表-链式存储原理（有向图）
为了方便说明，我将每条弧设置了标号。分别为abcde。
简单来说，十字链表存储中，顶点保存了当前顶点所有的弧，包括出弧和入弧，分别用两个指针来指向来记录所有弧，例如v1顶点的出弧有a、b、c，入弧有e。分别用出弧指针和入弧指针指向。
而弧中记录了弧头相同的弧指针与弧尾相同的弧指针，例如，c这条弧，就记录了与c的弧头相同的下一条弧指针，也就是d，同时也记录了与c的弧尾相同的下一条弧指针，也就是a、b。
因此，在代码中十字链表的数据结构我们可以具体表示为以下。
11、邻接多重表-链式存储原理（无向图）
顶点索引和顶点数据就不用说了，连接该顶点的边也是一个链式结构存储所有边，例如v1这个顶点，就有三条边a、b、c。
至于边的表示方法，例如b这条边，保存了v1顶点索引，v3顶点索引，同时记录了与v1相连的其他所有边（a、c）以及与v3相连的所有边（d），边数据就是权值。
因此，在代码中邻接多重表的数据结构我们可以具体表示为以下。
12、图的遍历原理
a、深度优先搜索
b、广度优先搜索
将这张图分为几层，按层数遍历。
c、最小生成树原理
前面的遍历并未涉及到权值，相对简单。
最小生成树是从所有路径中获取到权值最低并且能连接所有顶点的路径的方法。
这样的算法分成两种实现方式。
普里姆算法基本思想：
点集合包含所有的点即A、B、C、D、E、F。
边集合是将待选边集合中选出的最小权值边放进其中。
待选边集合就是连接顶点的所有边，对于顶点A来说，有三条边（AB、AF、AE）。
第一步，假设从A开始遍历，那就将A放入点集合，然后待选边中纳入AB、AF、AE，再选出待选边中权值最小的边，纳入边集合。
第二步，有了第一个点和第一条边，我们根据边集合发现A连接了F，于是我们将F纳入点集合，进而发现新的待选边集合变大了，新增了F连接的所有边FB、FC、FD、FE，随后我们发现AF已经被选走了，在剩下的边中最小的是FB，因此将FB纳入边集合中。
第三步，随着FB进入边集合，我们自然的将B纳入点集合，随后将BC加入待选边中，通过比较剩下的待选边权值，将BC纳入边集合。
第四步，随着BC进入边集合，我们自然的将C纳入点集合，随后将CD加入待选边中，通过比较剩下的待选边权值，将FD纳入边集合。
第五步，随着FD进入边集合，我们自然的将D纳入点集合，随后将DE加入待选边中，通过比较剩下的待选边权值，将DE纳入边集合。随着DE纳入边集合，我们自然的将E也纳入点集合，行进至此，就生成了我们想要的最小生成树。
克鲁斯卡尔算法思想：
第一步,将所有边纳入待选边集合，将权值最小的边纳入已选边集合，此处即是AF，此时已涉及的点包括AF,将A、F纳入已涉及的点集合中。
第二步,选择权值次小的边，这里就是FB和DE，当然这里权值相同谁先谁后都无所谓，假设我们这里选择FB，随后我们需要判断FB与AF是否形成闭环，如果形成闭环，我们需要抛弃FB。此时已涉及的点就是A、F、B了。
第三步，FB和DE权值相同，第二步中选择了FB，所以这里我们要选择DE纳入已选边集合中，同时将DE两个点新增一个集合，此时就是两个集合，因为DE和AF、FB不是连续的。
第四步，再到剩下的待选边集合中选择最小的边，这里是BC，将BC纳入边集合，同时BC和FB连续，因此和点A、F、B、C放入同一集合。
第五步，从剩下的待选边集合我们选出了FD，此时F和D分别来自两个不同的集合，于是两个集合就有了连系合并成了一个集合。此时，最小生成树也就生成完毕了。
13、无向图邻接矩阵编码
这里用到了一个小技巧，就是用一个数组来表示邻接矩阵。ABCDEFGH这八个顶点，我们肯定是依次添加进map中，因此我们自然而然得到他们的下标，从0到7。所以此处我们定义的数组大小为，8 *8，从而能很容易的想到我们通过row *8+col的方式去访问第row行第col列的数据，此时，我们的row和col的最大值就是下标7，那就是7 *8+7=63，那我们就可以直接通过下标访问并保存邻接矩阵的所有值了。例如我们访问第5行第6列，那我们传入的row和col分别为4和5，从图上看就是那就是行是E列是F的元素，也就是访问数组的4 * 8+5个元素，此时我们通过matrix[row * 8+col] = val,就可以给邻接矩阵赋值了，同时也能从矩阵中把指定的行列值取出来。
Node.h
#ifndef NODE_H
#define NODE_H
//顶点
struct Node
{
explicit Node(char data = 0)
:m_cData(data),m_bIsVisited(false)
{
}
char m_cData;
bool m_bIsVisited;
};
#endif // !NODE_H
CMap.h
#ifndef CMAP_H
#define CMAP_H
#include "Node.h"
#include <vector>
using namespace std;
class CMap
{
public:
CMap(size_t capacity);
~CMap();
bool addNode(Node *pNode); //向图中加入顶点（结点）
void resetNode(); //重置顶点
bool setValueToMatrixForDirectedGraph(size_t row, size_t col,int val=1); //为有向图设置邻接矩阵
bool setValueToMatrixForUndirectedGraph(size_t row, size_t col, int val = 1); //为无向图设置邻接矩阵
void printMatrix(); //打印邻接矩阵
void depthFirstTraverse(size_t nodeIndex); //深度优先遍历
void breahFirstTraverse(size_t nodeIndex); //广度优先遍历
private:
bool getValueFromMatrix(size_t row, size_t col,int &val); //从矩阵中获取权值
void breadthFirstTraverseImpl(vector<int> preVec); //广度优先遍历实现函数
private:
size_t m_iCapacity; //图中最多可以容纳的定点数
size_t m_iNodeCount; //已经添加的顶点个数
Node *m_pNodeArrray; //存放顶点数组
int *m_pMatrix; //存放邻接矩阵
};
#endif
CMap.cpp
#include "CMap.h"
#include <iostream>
CMap::CMap(size_t capacity)
{
m_iCapacity = capacity;
m_iNodeCount = 0;
m_pNodeArrray = new Node[m_iCapacity]; //开辟一段m_iCapacity大小的Node类型数组空间
m_pMatrix = new int[m_iCapacity*m_iCapacity]; //开辟一段m_iCapacity^2大小的int类型数组空间
memset(m_pMatrix, 0, m_iCapacity*m_iCapacity * sizeof(int)); //将m_pMatrix数组的所有元素初始值设为0
}
CMap::~CMap()
{
delete[]m_pNodeArrray; //释放m_pNodeArrray，需注意开辟空间时使用的是[]数组，因此需要使用delete[]
delete[]m_pMatrix; //释放m_pMatrix
}
/***************添加顶点原理：************************
*因为构造函数中已经给我们保存顶点的数组分配了内存空间
*因此我们只需要将待添加的顶点作为函数参数，赋值给我们
*数组空间的指定位置，由于此处我们不需要插入，仅仅使用
*m_iNodeCount顶点数量就可以表示顶点的下标。*********/
bool CMap::addNode(const Node * pNode)
{
//空指针不能添加
if (pNode == NULL)
{
return false;
}
if (m_iNodeCount >= m_iCapacity)
{
cout << "add node failed! out size of map " << endl;
return false;
}
//将添加的顶点保存到m_pNodeArrray中
m_pNodeArrray[m_iNodeCount].m_cData = pNode->m_cData;
m_iNodeCount++;
return true;
}
//重置顶点:将所有顶点初始化为未访问
void CMap::resetNode()
{
for (size_t i = 0; i < m_iNodeCount; i++)
{
m_pNodeArrray[i].m_bIsVisited = false;
}
}
bool CMap::setValueToMatrixForDirectedGraph(size_t row, size_t col, int val)
{
//如果传入的行和列不符合[0,m_iCapacity],就return false
if (row < 0 || row >= m_iCapacity)
{
return false;
}
if (col < 0 || col >= m_iCapacity)
{
return false;
}
//通过matrix[row*size+col] = val,给邻接矩阵中指定的行列元素赋值
m_pMatrix[row*m_iCapacity + col] = val;
return true;
}
bool CMap::setValueToMatrixForUndirectedGraph(size_t row, size_t col, int val)
{
//如果传入的行和列不符合[0,m_iCapacity],就return false
if (row < 0 || row >= m_iCapacity)
{
return false;
}
if (col < 0 || col >= m_iCapacity)
{
return false;
}
//对于无向图的邻接矩阵，因为沿对角线对称，所以我们知道(1,0)相应的就知道了(0,1)
m_pMatrix[row*m_iCapacity + col] = val;
m_pMatrix[col*m_iCapacity + row] = val;
return true;
}
//从邻接矩阵中获取指定行列的值
bool CMap::getValueFromMatrix(size_t row, size_t col, int & val)
{
//如果传入的行和列不符合[0,m_iCapacity],就return false
if (row < 0 || row >= m_iCapacity)
{
return false;
}
if (col < 0 || col >= m_iCapacity)
{
return false;
}
//通过matrix[row*size+col] = val,取出邻接矩阵中指定的行列元素
val = m_pMatrix[row * m_iCapacity + col];
return true;
}
void CMap::printMatrix()
{
for (size_t i = 0; i < m_iCapacity; i++)
{
for (size_t k = 0; k < m_iCapacity; k++)
{
cout << m_pMatrix[i*m_iCapacity + k] << " ";
}
cout << endl;
}
}
/****************
* A
* / \
* B D
* / \ / \
* C F G H
* \ /
* E
***************/
/*************************************************************
/*深度优先遍历：程序执行过程，将A作为当前顶点传入，通过遍历邻接
*矩阵找到和A连接的第一个顶点B，然后B又去遍历邻接矩阵找到C，然后
*C又去遍历邻接矩阵找到E，然后E又去遍历邻接矩阵找到C和F，但因为C
*是访问过的，F又去找到B，B又到A，A又到D，D又到G，G又到D，D到H。*/
void CMap::depthFirstTraverse(size_t nodeIndex)
{
//先打印当前传入的顶点数据，将它设置为访问过了
cout << m_pNodeArrray[nodeIndex].m_cData << " ";
m_pNodeArrray[nodeIndex].m_bIsVisited = true;
//其次，我们需要通过邻接矩阵来判断当前顶点是否与其他顶点有连接。
int value = 0;
//遍历邻接矩阵
for (size_t i = 0; i < m_iCapacity; i++)
{
//从邻接矩阵中去取值，相当于取出一条边
getValueFromMatrix(nodeIndex, i, value);
//nodeIndex和i顶点直间有边
if (value == 1)
{
//并且i顶点没有被访问过，如果访问过了就跳出循环
if (m_pNodeArrray[i].m_bIsVisited)
{
continue;;
}
/*如果i顶点没有被访问过，那就将i顶点作为当前顶点递归继续去遍历，
**直到所有的顶点都是被访问，那也就相当于我们通过邻接矩阵遍历完
**了所有顶点*/
else
{
depthFirstTraverse(i);
}
}
else
{
continue;
}
}
}
/*
* A
* / \
* B D
* / \ / \
* C F G H
* \ /
* E
*
*/
//广度优先遍历
/*程序执行过程，将A作为当前顶点传入，通过遍历邻接矩阵找到和A连接的所有顶点，
*放进数组v1中，这里v1也就是B和D两个顶点，然后遍历v1，通过邻接矩阵找到和
*B、D两个顶点相连接的所有顶点，但在找的过程中需要注意判断顶点是否访问过了。
*放进数组v2中，然后再*遍历v2，也就是CFGH四个顶点，找到E，行进至此，我们
*就通过完成了图的广度优先遍历。
*/
void CMap::breahFirstTraverse(size_t nodeIndex)
{
/*先打印当前传入的顶点数据，将它设置为访问过了。*/
cout << m_pNodeArrray[nodeIndex].m_cData << " ";
m_pNodeArrray[nodeIndex].m_bIsVisited = true;
vector<int> curVec;
curVec.push_back(nodeIndex);
//将第一层顶点数组传入breadthFirstTraverseImpl
breadthFirstTraverseImpl(curVec);
}
//用于遍历每一层的顶点，将每一层顶点所连接的
//下一层顶点找出来，以此达到遍历的目的
void CMap::breadthFirstTraverseImpl(const vector<int> &preVec)
{
//用于保存从邻接矩阵中获取出来的权值，权值为0，说明两个顶点直接没有边
int value = 0;
//用于保存preVec数组中连接的下一层的顶点
vector<int> curVec;
//遍历preVec和所有顶点
for (size_t j = 0; j < preVec.size(); j++)
{
for (size_t i = 0; i < m_iCapacity; i++)
{
//根据邻接矩阵找出preVec中的顶点相连的顶点
getValueFromMatrix(preVec[j], i, value);
if (value != 1)//如果preVec[j]顶点与i顶点之间有边
{
if (m_pNodeArrray[i].m_bIsVisited)//如果preVec[j]顶点与i顶点之间的边被访问了就跳出循环
{
continue;
}
else//否则preVec[j]与i之间就有边，就找到了与preVec[j]相连的顶点
{
//将找到的与preVec[j]相连的顶点设为已访问过，并添加进curVec数组中
cout << m_pNodeArrray[i].m_cData << " ";
m_pNodeArrray[i].m_bIsVisited = true;
curVec.push_back(i);
}
}
else
{
continue;
}
}
}
//如果preVec中的顶点已经没有了相连的顶点，则退出
if (curVec.size() == 0)
{
return;
}
//否则，继续去找与curVec中所有顶点相连的下一层顶点
else
{
breadthFirstTraverseImpl(curVec);
}
}
main.cpp
#include "CMap.h"
#include <iostream>
using namespace std;
/*
* A
* / \
* B D
* / \ / \
* C F G H
* \ /
* E
*
*/
/*
* A B C D E F G H
*A 1 1
*B 1 1 1
*C 1 1 1
*D 1 1 1
*E 1
*F 1 1
*G 1 1
*H 1 1
**/
int main()
{
CMap *pMap = new CMap(8);
Node* pNodeA = new Node('A');
Node* pNodeB = new Node('B');
Node* pNodeC = new Node('F');
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->depthFirstTraverse(0);
cout << endl;
pMap->resetNode();
pMap->breahFirstTraverse(0);
return 0;
}
运行结果：
14、最小生成树编码
Node.h
#ifndef NODE_H
#define NODE_H
//顶点
struct Node
{
explicit Node(char data = 0)
:m_cData(data),m_bIsVisited(false)
{
}
char m_cData;
bool m_bIsVisited;
};
#endif // !NODE_H
Edge.h
#ifndef EDGE_H
#define EDGE_H
//边
struct Edge
{
Edge(size_t nodeIndexA = 0, size_t nodeIndexB = 0, int weightValue = 0)
:m_iNodeIndexA(nodeIndexA),
m_iNodeIndexB(nodeIndexB),
m_iWeightValue(weightValue),
m_bSelected(false)
{}
size_t m_iNodeIndexA;
size_t m_iNodeIndexB;
int m_iWeightValue;
bool m_bSelected;
};
#endif // !EDGE_H
CMap.h
#ifndef CMAP_H
#define CMAP_H
#include "Node.h"
#include "Edge.h"
#include <vector>
using namespace std;
class CMap
{
public:
CMap(size_t capacity);
~CMap();
bool addNode(const Node *pNode); //向图中加入顶点（结点）
void resetNode(); //重置顶点
void printMatrix(); //打印邻接矩阵
public:
bool setValueToMatrixForUndirectedGraph(const size_t &row, const size_t &col, const int &val = 1); //为无向图设置邻接矩阵
public:
void primeTree(size_t nodeIndex); //普里姆生成树
void kruskalTree(); //克鲁斯卡尔生成树
private:
bool getValueFromMatrix(const size_t &row, const size_t &col, int &val); //从矩阵中获取权值
int getMinEdge(const vector<Edge> &edgeVec); //从待选边中找出最小边
bool isInSet(vector<int> nodeSet,size_t target);
void mergeNodeSet(vector<int> &nodeSetA, const vector<int> &nodeSetB);
private:
size_t m_iCapacity; //图中最多可以容纳的定点数
size_t m_iNodeCount; //已经添加的顶点个数
Node *m_pNodeArrray; //存放顶点数组
int *m_pMatrix; //存放邻接矩阵
Edge *m_pEdge; //保存最小边集合
};
#endif
CMap.cpp
#include "CMap.h"
#include <iostream>
CMap::CMap(size_t capacity)
{
m_iCapacity = capacity;
m_iNodeCount = 0;
m_pNodeArrray = new Node[m_iCapacity]; //开辟一段m_iCapacity大小的Node类型数组空间
m_pMatrix = new int[m_iCapacity*m_iCapacity]; //开辟一段m_iCapacity^2大小的int类型数组空间
memset(m_pMatrix, 0, m_iCapacity*m_iCapacity * sizeof(int)); //将m_pMatrix数组的所有元素初始值设为0
m_pEdge = new Edge[m_iCapacity-1]; //由于是无向图，求出的最小生成树的边的值为顶点数量减一，如六个顶点，五条边就能将6个顶点全部连接。
}
CMap::~CMap()
{
delete[]m_pNodeArrray; //释放m_pNodeArrray，需注意开辟空间时使用的是[]数组，因此需要使用delete[]
delete[]m_pMatrix; //释放m_pMatrix
delete[]m_pEdge; //释放m_pEdge
}
/*添加顶点原理：
*因为构造函数中已经给我们保存顶点的数组分配了内存空间
*因此我们只需要将待添加的顶点作为函数参数，赋值给我们
*数组空间的指定位置，由于此处我们不需要插入，仅仅使用
*m_iNodeCount顶点数量就可以表示顶点的下标。
**/
bool CMap::addNode(const Node * pNode)
{
if (pNode == NULL)
{
return false;
}
if (m_iNodeCount >= m_iCapacity)
{
cout << "add node failed! out size of map " << endl;
return false;
}
m_pNodeArrray[m_iNodeCount].m_cData = pNode->m_cData;
m_iNodeCount++;
return true;
}
void CMap::resetNode()
{
for (size_t i = 0; i < m_iNodeCount; i++)
{
m_pNodeArrray[i].m_bIsVisited = false;
}
}
bool CMap::setValueToMatrixForUndirectedGraph(const size_t &row,const size_t &col, const 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;
}
void CMap::printMatrix()
{
for (size_t i = 0; i < m_iCapacity; i++)
{
for (size_t k = 0; k < m_iCapacity; k++)
{
cout << m_pMatrix[i*m_iCapacity + k] << " ";
}
cout << endl;
}
}
bool CMap::getValueFromMatrix(const size_t &row, const size_t &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::primeTree(size_t nodeIndex)
{
int value = 0; //保存边的权值
size_t edgeCount = 0; //边的计数器
vector<size_t> nodeVec; //顶点的集合，保存顶点索引
vector<Edge> edgeVec; //边的结合，Edge
//将第一个顶点放入顶点的集合nodeVec中
cout << m_pNodeArrray[nodeIndex].m_cData << endl;
nodeVec.push_back(nodeIndex);
m_pNodeArrray[nodeIndex].m_bIsVisited = true;
//边数小于所求边数时进入循环
while (edgeCount < m_iCapacity - 1)
{
//取出第一个顶点索引，即m_pNodeArrray[nodeIndex]，以该顶点为基准去找与它连接的边
int temp = nodeVec.back();
for (size_t i=0;i<m_iCapacity;++i)
{
getValueFromMatrix(temp, i, value);
if (value != 0)//如果i和temp顶点之间有边
{
if (m_pNodeArrray[i].m_bIsVisited)//如果顶点被访问过就跳出循环
{
continue;
}
else//否则就找到了可选边
{
Edge edge(temp,i,value);
edgeVec.push_back(edge);
}
}
}
//从可选边集合中找出最小的边，并将其设成已访问过
size_t edgeIndx = getMinEdge(edgeVec);
edgeVec[edgeIndx].m_bSelected = true;
cout << edgeVec[edgeIndx].m_iNodeIndexA << "----" << edgeVec[edgeIndx].m_iNodeIndexB << " ";
cout << edgeVec[edgeIndx].m_iWeightValue << " ";
//保存边
m_pEdge[edgeCount] = edgeVec[edgeIndx];
edgeCount++;
//找到与当前最小边所连接的顶点
//edgeVec[edgeIndx]是最小边，是前面通过getMinEdge获取
//同时将最小边所连接的顶点加入点集合，并设为已访问过
size_t nextNodeIndex = edgeVec[edgeIndx].m_iNodeIndexB;
nodeVec.push_back(nextNodeIndex);
m_pNodeArrray[nextNodeIndex].m_bIsVisited = true;
cout << m_pNodeArrray[nextNodeIndex].m_cData << endl;
}
}
int CMap::getMinEdge(const vector<Edge>& edgeVec)
{
int minWeight = 0; //最小权值
size_t edgeIndex = 0; //
size_t i = 0; //用于for循环
//找出第一条没有被访问选择的边
for (;i<edgeVec.size();++i)
{
if (!edgeVec[i].m_bSelected)//如果边没有被选出来
{
minWeight = edgeVec[i].m_iWeightValue; //记录权值
edgeIndex = i; //记录索引
break;
}
}
if (minWeight == 0)
{
return int(-1);
}
//这里i从edgeIndex开始，将剩余的边与第一条边比较权值然后更新minWeight和edgeIndex
for (; i < edgeVec.size(); ++i)
{
if (edgeVec[i].m_bSelected)
{
continue;
}
else//如果边没有被选出来
{
//edgeVec[i].m_iWeightValue比minWeight还要小，就更新minWeight和edgeIndex
if (minWeight > edgeVec[i].m_iWeightValue)
{
minWeight = edgeVec[i].m_iWeightValue;
edgeIndex = i;
}
}
}
return (int)edgeIndex;
}
void CMap::kruskalTree()
{
int value = 0; //存放从邻接矩阵中取出的值
int edgeCount = 0; //记录边的条数
//定义存放顶点集合的数组
vector<vector<int>> nodeSets;
//第一步：取出所有边
vector<Edge> edgeVec;//定义存放边集合的数组
for (size_t i=0;i<m_iCapacity;i++)
{
for (size_t j = i+1; j < m_iCapacity; j++)//相当于遍历了矩阵的上三角
{
getValueFromMatrix(i, j, value);
if (value != 0)
{
Edge edge(i,j,value);
edgeVec.push_back(edge);
}
}
}
//第二步:从所有边中取出组成最小生成树的边
//1.找到算法结束条件，边数小于所求边数时进入循环
while (edgeCount< m_iCapacity - 1)
{
//2.从边集合中找到最小边
int minEdgeIndex = getMinEdge(edgeVec);
edgeVec[minEdgeIndex].m_bSelected = true;
//3.找出最小边连接的点
size_t nodeIndexA = edgeVec[minEdgeIndex].m_iNodeIndexA;
size_t nodeIndexB = edgeVec[minEdgeIndex].m_iNodeIndexB;
bool nodeAIsInSet = false;
bool nodeBIsInSet = false;
//保存A、B的索引
int nodeAInSetLabel = -1;
int nodeBInSetLabel = -1;
//4.找出点所在的点集合
for (size_t i = 0; i < nodeSets.size(); i++)
{
nodeAIsInSet = isInSet(nodeSets[i], nodeIndexA);
if (nodeAIsInSet)
{
nodeAInSetLabel = i;
}
}
for (size_t i = 0; i < nodeSets.size(); i++)
{
nodeBIsInSet = isInSet(nodeSets[i], nodeIndexB);
if (nodeBIsInSet)
{
nodeBInSetLabel = i;
}
}
//5.根据点所在集合的不同做出不同处理
if (nodeAInSetLabel == -1 && nodeBInSetLabel == -1)
{
vector<int> vec;
vec.push_back(nodeIndexA);
vec.push_back(nodeIndexB);
nodeSets.push_back(vec);
}
else if(nodeAInSetLabel == -1 && nodeBInSetLabel != -1)
{
nodeSets[nodeBInSetLabel].push_back(nodeIndexA);
}
else if (nodeAInSetLabel != -1 && nodeBInSetLabel == -1)
{
nodeSets[nodeAInSetLabel].push_back(nodeIndexB);
}
else if (nodeAInSetLabel != -1 &&
nodeBInSetLabel != -1 &&
nodeAInSetLabel != nodeBInSetLabel)
{
mergeNodeSet(nodeSets[nodeAInSetLabel],nodeSets[nodeBInSetLabel]);
for (size_t k=nodeBInSetLabel;k<nodeSets.size()-1;k++)
{
nodeSets[k] = nodeSets[k+1];
}
}
//当前选出来的边形成回路，就放弃掉当前边
else if (nodeAInSetLabel != -1 &&
nodeBInSetLabel != -1 &&
nodeAInSetLabel == nodeBInSetLabel)
{
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, size_t target)
{
for (size_t i = 0; i < nodeSet.size(); i++)
{
if (nodeSet[i] == target)
{
return true;
}
}
return false;
}
void CMap::mergeNodeSet(vector<int> &nodeSetA, const vector<int> &nodeSetB)
{
for (size_t i = 0; i < nodeSetB.size(); i++)
{
nodeSetA.push_back(nodeSetB[i]);
}
}
mian.cpp
#include <iostream>
#include "CMap.h"
using namespace std;
/* A
* / | \
* B -- F -- E
* \ / \ /
* C --- D
*
* A B C D E F
* 0 1 2 3 4 5
*
* A-B 6 A-E 5 A-F 1
* B-C 3 B-F 2
* C-F 8 C-D 7
* D-F 4 D-E 2
* E-F 9
**/
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);
cout<<"prime："<<endl;
pMap->primeTree(0);
cout << endl << endl;
cout << "kruskal：" << endl;
pMap->kruskalTree();
return 0;
}
运行结果
开放原子开发者工作坊旨在鼓励更多人参与开源活动，与志同道合的开发者们相互交流开发经验、分享开发心得、获取前沿技术趋势。工作坊有多种形式的开发者活动，如meetup、训练营等，主打技术交流，干货满满，真诚地邀请各位开发者共同参与！
更多推荐
31
0- 0
已为社区贡献1条内容
所有评论(0)