原文地址：https://www.cloudcrossing.xyz/post/32/
PS：以下顶点也成节点。
图的基本概念
如果给图的每条边规定一个方向，那么得到的图称为有向图。在有向图中，与一个节点相关联的边有出边和入边之分。相反，边没有方向的图称为无向图。
一个图有顶点和弧（边）组成，其中一个弧有弧头和弧尾（如上图所示）。有的弧还带有权值。顶点的度是指和该顶点相连的边的条数。特别是对于有向图来说，顶点的出边条数称为该顶点的出度，顶点的入边条数称为该项点的入度。
顶点 v1 和顶点 v3 之间存在一条边，我们称顶点 v1 和 v3 互为邻接点。
在一个无向图 G 中，两个顶点之间有路径相连，则称他们是连通的。如果 G 是有向图，那么连接两个顶点的路径中所有的边都必须同向。如果图中任意两点都是连通的，那么图被称作连通图。如果此图是有向图，则称为强连通图（注意：需要双向都有路径）。
完全图是一个简单的无向图，其中每对不同的顶点之间都恰连有一条边相连。
子图是图论的基本概念之一，指节点集和边集分别是某一图的节点集的子集和边集的子集的图。如果连通图的一个子图是一棵包含的所有顶点的树，则该子图称为G的生成树。
图的存储方式
邻接矩阵—数组存储
邻接矩阵**是表示顶点之间相邻关系的矩阵。顶点的表示一般由顶点索引和顶点数据组成。下面分别是有向图和无向图邻接矩阵。
对于邻接矩阵，我们可以用int型的二维数组进行如下表示。
对于邻接矩阵的顶点和图，我们可以使用如下的方式进行表示。
邻接表—链式存储
邻接表是图的一种最主要存储结构，用来描述图上的每一个点。对图的每个顶点建立一个容器（n个顶点建立n个容器），第 i 个容器中的结点包含顶点 Vi 的所有邻接顶点。
邻接表的顶点由顶点索引、顶点数据、出弧链表表头指针组成。弧由弧头顶点索引、弧数据和下一条弧指针。其中出弧链表表头指针指向弧链表。
十字链表—链式存储
邻接多重表—链式存储（无向图）
图的遍历
深度优先搜索
深度优先搜索：
- 假设给定图G的初态是所有顶点均未曾访问过。在G中任选一顶点v为初始出发点(源点)，则深度优先遍历可定义如下：首先访问出发点v，并将其标记为已访问过；然后依次从v出发搜索v的每个邻接点w。若w未曾访问过，则以w为新的出发点继续进行深度优先遍历，直至图中所有和源点v有路径相通的顶点(亦称为从源点可达的顶点)均已被访问为止。若此时图中仍有未访问的顶点，则另选一个尚未访问的顶点作为新的源点重复上述过程，直至图中所有顶点均已被访问为止。
广度优先搜索
广度优先搜索：
- 1、从图中某个顶点V0出发，并访问此顶点；
- 2、从V0出发，访问V0的各个未曾访问的邻接点W1，W2，…,Wk;然后,依次从W1,W2,…,Wk出发访问各自未被访问的邻接点；
- 3、重复步骤2，直到全部顶点都被访问为止。
最小生成树
普利姆算法
第一步
第二步
第三步
第四步
第五步
克鲁斯卡尔算法
第一步
第二步
第三步
第四步
第五步
图的编码
深度优先遍历和广度优先遍历
首先来定义节点类，新建Node.h，Node.cpp。
#Node.h
class Node
{
public:
Node(char data = 0);
char m_cData;
bool m_bIsVisited; //当前节点是否被访问的标志。true表示访问过
};
#Node.cpp
#include "stdafx.h"
#include "Node.h"
Node::Node(char data)
{
m_cData = data;
m_bIsVisited = false;
}
节点类有两个成员变量，一个是节点数据m_cData（默认值为0），一个是访问标志m_bIsVisited（true表示访问过，初始化为false）。
接着设计图类Cmap，新建Cmap.h和Cmap.cpp。
#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 depthFitstTraverse(int nodeIndex); //深度优先遍历
void breadthFitstTraverse(int nodeIndex); //广度优先遍历
private:
bool getValueFromMatrix(int row, int col, int &val); //从矩阵中获取权值
void breadthFitstTraverseImpl(vector<int> preVec); //从广度优先遍历实现函数
private:
int m_iCapacity; //途中最多可以容纳的定点数
int m_iNodeCount; //已经添加节点个数
Node *m_pNodeArray; //用来存放节点数组
int *m_pMatrix; //用来存放邻接矩阵
};
#Cmap.cpp
#include "stdafx.h"
#include "vector"
#include "iostream"
#include "Cmap.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];
//memset(m_pMatrix, 0, m_iCapacity * m_iCapacity * sizeof(int));
//void *memset(void *s, int ch, size_t n);
//函数解释：将s中当前位置后面的n个字节 （typedef unsigned int size_t ）用 ch 替换并返回 s 。
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;
}
void Cmap::printMatrix()
{
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;
}
}
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::depthFitstTraverse(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
{
depthFitstTraverse(i);
}
}
else
{
//如果没有去向索引为 i 的顶点的弧，则循环继续
continue;
}
}
}
//广度优先遍历
void Cmap::breadthFitstTraverse(int nodeIndex)
{
cout << m_pNodeArray[nodeIndex].m_cData << " ";
m_pNodeArray[nodeIndex].m_bIsVisited = true;
vector<int> curVec; //当前数组
curVec.push_back(nodeIndex); //压入数组
breadthFitstTraverseImpl(curVec);
}
//广度优先遍历 进一步
void Cmap::breadthFitstTraverseImpl(vector<int> preVec)
{
int value = 0;
vector<int> curVec; //保存当前这一层所有节点
for (int j = 0; j < (int)preVec.size(); j++) //preVec.size():上一层节点数
{
for (int i = 0; i < m_iCapacity; i++) //判断上一层节点与其他点是否有连接
{
getValueFromMatrix(preVec[j], i, value);
if (value != 0)
{
if (m_pNodeArray[i].m_bIsVisited)
{
continue;
}
else //如果有连接，置为已访问、输出并保存到当前这一层的curVec
{
cout << m_pNodeArray[i].m_cData << " ";
m_pNodeArray[i].m_bIsVisited = true;
curVec.push_back(i);
}
}
}
}
if (curVec.empty()) //判断本层是否存在被访问过的点
{
return;
}
else //本层访问过的点的个数不为0，下一层可能还有节点与本层的节点相连接
{
breadthFitstTraverseImpl(curVec);
}
}
图类一共有四个成员变量，int型的m_iCapacity表示图中最多可以容纳的顶点数，int型的m_pMatrix表示已经添加顶点个数，顶点类指针m_pNodeArray用来指向顶点数组，int型指针m_pMatrix指向邻接矩阵。
构造函数传入一个参数，图的容量（可以容纳顶点的个数）。m_iNodeCount置为0表示当前已经加入的顶点个数。创建的顶点类m_pNodeArray用来存放顶点。创建的int一维数组m_pMatrix用来表示邻接矩阵（大小为m_iCapacity * m_iCapacity）。除此之外，我们还要将邻接矩阵内的元素置为0。
析构函数用来释放存放顶点的顶点类和邻接矩阵数组。
bool Cmap::addNode(Node *pNode)添加顶点函数传入的参数为要插入的顶点类指针pNode。首先判断pNode指向是否为NULL，然后将顶点数组的当前位置m_iNodeCount的顶点的数据赋值为pNode->m_cData，最后不要忘记m_iNodeCount++。
接着来将重置顶点函数void Cmap::resetNode()，这个函数主要用来将图内所有顶点的访问状态置为为访问过，也就是将m_pNodeArray所有的元素的m_bIsVisited赋值为false。
bool Cmap::setValueToMatrixForDirectedGraph(int row, int col, int val)为有向图设置邻接矩阵函数传入三个参数，分别是矩阵的行和列，以及矩阵元素的初值（默认值为1，表示两个顶点之间有连接即边）。首先判断传入的行和列是否合法，接着将邻接矩阵m_pMatrix对应位置的元素置为1。
- 因为这里是用一维矩阵表示的（demo里面展示出来是个二维矩阵），行数从上而下为0-7（以demo中例子为依据），列数从左至右为0-7。邻接矩阵存储是按照行从左至右、从上至下初始化的。但实质上是一维数组，故而索引（下标）为row*capacity+col。比如demo中的3行3列，实际上在数组中其存储在下标为3*8+3的位置。
bool Cmap::setValueToMatrixForUndirectedGraph(int row, int col, int val)为无向图设置邻接矩阵函数也传入三个参数分别是矩阵的行和列，以及矩阵元素的初值（默认值为1）。首先也要判断传入参数的合法性。因为是无向图，其邻接矩阵对称，所以我们要进行两次邻接矩阵元素的赋值。
void Cmap::printMatrix()打印邻接矩阵函数直接使用两个for循环打印矩阵的每个元素（打印完每一行之后控制换行）。
bool Cmap::getValueFromMatrix(int row, int col, int &val)取邻接矩阵中指定位置的权值函数，传入的参数有三，行、列、以及存放权值的变量 val 。首先判断传入参数的合法性，最后将指定位置的值赋值给val。
void Cmap::depthFitstTraverse(int nodeIndex)深度优先遍历函数传入的参数为开始遍历顶点的索引。首先创建一个初值为0的int变量value用来存放邻接矩阵的元素的值，接着打印当前位置（索引为nodeIndex）的数据，并置为已访问状态。然后通过遍历邻接矩阵判断是否与其他顶点有连接，在每一次循环中，先取出当前位置为起点，其他位置为终点的元素值存放到value中，并判断value是否为0，即是否存在与当前位置的顶点相连接的其他点。如果有则继续判断该点是否被访问过，访问过则跳过本次循环；没有访问过则迭代，继续调用本函数，传入的参数为本次循环的顶点 i 。如果value为0，即没有去向索引为 i 的顶点的弧，则循环继续。
void Cmap::breadthFitstTraverse(int nodeIndex)广度优先遍历函数传入的参数也为开始遍历顶点的索引。首先也是打印当前位置（索引为nodeIndex）的数据并置为已访问状态。然后创建一个能够存放任意类型的动态数组（这里我们定义为int容器）curVec来表示当前这一层的数组，然后将当前位置的顶点存入数组中。接着调用进一步的广度优先遍历函数breadthFitstTraverseImpl(curVec)。这个函数的解释如下。
void Cmap::breadthFitstTraverseImpl(vector<int> preVec)传入的参数为上一个函数创建的动态数组preVec（即curVec，这里表示为上一层数组）。首先创建一个初值为0的int变量value用来存放邻接矩阵的元素的值。接着定义新的int动态数组curVec来存放当前这一层所有顶点。然后遍历上一层所有顶点，在上一层每个顶点的循环中，遍历所有顶点，判断上一层节点与其他点是否有连接。将取出来的value进行判断是否为0，如果不为0，则继续判断是否被访问，访问了continue，没访问则表示上一层和当前这一层的 i 顶点有连接，将 i 顶点置为已访问、输出并保存到当前这一层的curVec。遍历完上一层的顶点数组preVec之后，判断本层数组curVec是否为空，如果为空跳出，否则表示本层访问过的点的个数不为0，下一层可能还有节点与本层的节点相连接，继续迭代本函数，传入参数为本层数组curVec。
新建测试demo.cpp
#demo.cpp
#include "stdafx.h"
#include "iostream"
#include "Cmap.h"
using namespace std;
/*
A
/ \
B D
/ \ / \
C F G - H
\ /
E
*/
/*
A B C D E F G H
A 0 1 0 1 0 0 0 0
B 1 0 1 0 0 1 0 0
C 0 1 0 0 1 0 0 0
D 1 0 0 0 0 0 1 1
E 0 0 1 0 0 1 0 0
F 0 1 0 0 1 0 0 0
G 0 0 0 1 0 0 0 1
H 0 0 0 1 0 0 1 0
*/
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->depthFitstTraverse(1);
cout << endl;
pMap->resetNode();
pMap->breadthFitstTraverse(1);
cout << endl;
system("pause");
return 0;
}
运行结果为：
最小生成树
【普利姆算法】：从单一顶点开始，普里姆算法按照以下步骤逐步扩大树中所含顶点的数目，直到遍及连通图的所有顶点。
- 1、输入：一个加权连通图，其中顶点集合为V，边集合为E；
- 2、初始化：Vnew = {x}，其中x为集合V中的任一节点（起始点），Enew = {}；
- 3、重复下列操作，直到Vnew = V：
- （1）在集合E中选取权值最小的边（u, v），其中u为集合Vnew中的元素，而v则是V中没有加入Vnew的顶点（如果存在有多条满足前述条件即具有相同权值的边，则可任意选取其中之一）；
- （2）将v加入集合Vnew中，将（u, v）加入集合Enew中；
- 4、输出：使用集合Vnew和Enew来描述所得到的最小生成树。
【克鲁斯卡尔算法】：先构造一个只含 n 个顶点、而边集为空的子图，把子图中各个顶点看成各棵树上的根结点，之后，从网的边集 E 中选取一条权值最小的边，若该条边的两个顶点分属不同的树，则将其加入子图，即把两棵树合成一棵树，反之，若该条边的两个顶点已落在同一棵树上，则不可取，而应该取下一条权值最小的边再试之。依次类推，直到森林中只有一棵树，也即子图中含有 n-1 条边为止。
首先我们需要一个存放边的类，新建Edge.h和Edge.cpp
#Edge.h
class Edge
{
public:
Edge(int m_iNodeIndexA = 0, int m_iNodeIndexB = 0, int m_iWeightValue = 0);
int m_iNodeIndexA;
int m_iNodeIndexB;
int m_iWeightValue;
bool m_bSelected;
};
#Edge.cpp
#include "stdafx.h"
#include "Edge.h"
Edge::Edge(int nodeIndexA, int nodeIndexB, int weightValue)
{
m_iNodeIndexA = nodeIndexA;
m_iNodeIndexB = nodeIndexB;
m_iWeightValue = weightValue;
m_bSelected = false;
}
边类有四个成员变量，分别是int的m_iNodeIndexA（边的A顶点，默认值为0）、m_iNodeIndexB（边的B顶点，默认值为0）、m_iWeightValue（边的权值，默认值为0）以及bool的m_bSelected（访问标志，默认值为false）。
接着新建Cmap_tree.h和Cmap.cpp。
#Cmap_tree.h
#include "Node.h"
#include "Edge.h"
#include "vector"
using namespace std;
class Cmap_tree
{
public:
Cmap_tree(int capacity);
~Cmap_tree();
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 depthFitstTraverse(int nodeIndex); //深度优先遍历
void breadthFitstTraverse(int nodeIndex); //广度优先遍历
void primTree(int nodeIndex); //普利姆生成树
void kruskalTree(); //克鲁斯卡尔算法生成树
private:
bool getValueFromMatrix(int row, int col, int &val); //从矩阵中获取权值
void breadthFitstTraverseImpl(vector<int> preVec); //从广度优先遍历实现函数
int getMinEdge(vector<Edge> edgeVec); //获取最小边
bool isInSet(vector<int> nodeSet, int target); //判断顶点是否在点集合中
void mergeNodeSet(vector<int> &nodeSetA, vector<int> nodeSetB); //合并两个顶点集合
private:
int m_iCapacity; //途中最多可以容纳的定点数
int m_iNodeCount; //已经添加节点个数
Node *m_pNodeArray; //用来存放节点数组
int *m_pMatrix; //用来存放邻接矩阵
Edge *m_pEdge; //用来存放最小生成树的边
};
#Cmap.cpp
#include "stdafx.h"
#include "vector"
#include "iostream"
#include "Cmap_tree.h"
using namespace std;
Cmap_tree::Cmap_tree(int capacity)
{
m_iCapacity = capacity;
m_iNodeCount = 0;
m_pNodeArray = new Node[m_iCapacity];
m_pMatrix = new int[m_iCapacity * m_iCapacity];
//memset(m_pMatrix, 0, m_iCapacity * m_iCapacity * sizeof(int));
//void *memset(void *s, int ch, size_t n);
//函数解释：将s中当前位置后面的n个字节 （typedef unsigned int size_t ）用 ch 替换并返回 s 。
for (int i = 0; i < m_iCapacity * m_iCapacity; i++)
{
m_pMatrix[i] = 0;
}
m_pEdge = new Edge[m_iCapacity - 1]; //边是顶点个数-1
}
Cmap_tree::~Cmap_tree()
{
delete[]m_pNodeArray;
delete[]m_pMatrix;
delete[]m_pEdge;
}
bool Cmap_tree::addNode(Node *pNode)
{
if (pNode == NULL)
{
return false;
}
m_pNodeArray[m_iNodeCount].m_cData = pNode->m_cData;
m_iNodeCount++;
return true;
}
void Cmap_tree::resetNode()
{
for (int i = 0; i < m_iNodeCount; i++)
{
m_pNodeArray[i].m_bIsVisited = false;
}
}
bool Cmap_tree::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_tree::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;
}
void Cmap_tree::printMatrix()
{
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;
}
}
bool Cmap_tree::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_tree::depthFitstTraverse(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
{
depthFitstTraverse(i);
}
}
else
{
//如果没有去向索引为 i 的顶点的弧，则循环继续
continue;
}
}
}
//广度优先遍历
void Cmap_tree::breadthFitstTraverse(int nodeIndex)
{
cout << m_pNodeArray[nodeIndex].m_cData << " ";
m_pNodeArray[nodeIndex].m_bIsVisited = true;
vector<int> curVec; //当前数组
curVec.push_back(nodeIndex); //压入数组
breadthFitstTraverseImpl(curVec);
}
//广度优先遍历 进一步
void Cmap_tree::breadthFitstTraverseImpl(vector<int> preVec)
{
int value = 0;
vector<int> curVec; //保存当前这一层所有节点
for (int j = 0; j < (int)preVec.size(); j++) //preVec.size():上一层节点数
{
for (int i = 0; i < m_iCapacity; i++) //判断上一层节点与其他点是否有连接
{
getValueFromMatrix(preVec[j], i, value);
if (value != 0)
{
if (m_pNodeArray[i].m_bIsVisited)
{
continue;
}
else //如果有连接，置为已访问、输出并保存到当前这一层的curVec
{
cout << m_pNodeArray[i].m_cData << " ";
m_pNodeArray[i].m_bIsVisited = true;
curVec.push_back(i);
}
}
}
}
if (curVec.empty()) //判断本层是否存在被访问过的点
{
return;
}
else //本层访问过的点的个数不为0，下一层可能还有节点与本层的节点相连接
{
breadthFitstTraverseImpl(curVec);
}
}
//普利姆生成树
void Cmap_tree::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;
while (edgeCount < m_iCapacity - 1) //算法结束条件
{
int temp = nodeVec.back(); //保存nodeVec最尾部的变量，不能直接把nodeIndex赋值，不然这个循环temp一直不变，都是nodeIndex
for (int i = 0; i < m_iCapacity; i++) //寻找与temp节点连接的所有边
{
getValueFromMatrix(temp, i, value);
if (value != 0) //判断是否有连接的边
{
if (m_pNodeArray[i].m_bIsVisited) //判断当前的点是否被访问
{
continue;
}
else
{
Edge edge(temp, i, value); //通过相连接的两个点和权值创建一个边的对象
edgeVec.push_back(edge); //将边放入备选边集合中（不放重复的边）
}
}
}
//所有与temp相连接的边都被放入备选边集合中了
//从备选边集合中找出最小的边的
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); //保证下一次循环时temp为下一个点
m_pNodeArray[nextNodeIndex].m_bIsVisited = true;
cout << m_pNodeArray[nextNodeIndex].m_cData << endl;
}
}
int Cmap_tree::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_tree::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.找到算法结束条件
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 nodeAInSetLable = -1;
int nodeBInSetLable = -1;
//4.找出点所在的点集合
for (int i = 0; i < (int)nodeSets.size(); i++) //在存放节点集合的数组寻找A点在哪一个集合
{
nodeAIsInSet = isInSet(nodeSets[i], nodeAIndex); //在存放节点集合的数组nodeSets的第i个数组中寻找A点
if (nodeAIsInSet)
{
nodeAInSetLable = i; //找出A点所在集合的索引
}
}
for (int i = 0; i < (int)nodeSets.size(); i++) //在存放节点集合的数组寻找B点在哪一个集合
{
nodeBIsInSet = isInSet(nodeSets[i], nodeBIndex); //在存放节点集合的数组nodeSets的第i个数组中寻找B点
if (nodeBIsInSet)
{
nodeBInSetLable = i; //找出B点所在集合的索引
}
}
//5.根据点所在集合的不同做出不同处理
if (nodeAInSetLable == -1 && nodeBInSetLable == -1) //A点和B点都不在已有的节点集合中，所以AB两个点要放在一个全新的集合中
{
vector<int> vec;
vec.push_back(nodeAIndex);
vec.push_back(nodeBIndex);
nodeSets.push_back(vec);
}
else if (nodeAInSetLable == -1 && nodeBInSetLable != -1) //A点不在已有的节点集合中，B点归属某一集合，所以将A点放在B点的集合里边
{
nodeSets[nodeBInSetLable].push_back(nodeAIndex);
}
else if (nodeAInSetLable != -1 && nodeBInSetLable == -1) //B点不在已有的节点集合中，A点归属某一集合，所以将B点放在A点的集合里边
{
nodeSets[nodeAInSetLable].push_back(nodeBIndex);
}
else if (nodeAInSetLable != -1 && nodeBInSetLable != -1 && nodeAInSetLable != nodeBInSetLable) //A点和B点都在已有的节点集合中（两个不同的集合），所以要合并两个集合
{
mergeNodeSet(nodeSets[nodeAInSetLable], nodeSets[nodeBInSetLable]); //合并到第一个参数的集合中，即A的集合
for (int k = nodeBInSetLable; k < (int)nodeSets.size() - 1; k++) //删除B的集合
{
nodeSets[k] = nodeSets[k + 1];
}
}
else if (nodeAInSetLable != -1 && nodeBInSetLable != -1 && nodeAInSetLable == nodeBInSetLable) //A点和B点都在已有的节点集合中（同一个集合），所以直接跳过本次循环
{
continue;
}
m_pEdge[edgeCount] = edgeVec[minEdgeIndex]; //将寻找到的最小边放到最小生成树的边集合中
edgeCount++;
cout << edgeVec[minEdgeIndex].m_iNodeIndexA << "--" << edgeVec[minEdgeIndex].m_iNodeIndexB << " ";
cout << edgeVec[minEdgeIndex].m_iWeightValue << endl;
}
}
//判断顶点是否在点集合中
bool Cmap_tree::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_tree::mergeNodeSet(vector<int> &nodeSetA, vector<int> nodeSetB)
{
for (int i = 0; i < (int)nodeSetB.size(); i++)
{
nodeSetA.push_back(nodeSetB[i]);
}
}
和Cmap.h相比，Cmap_tree.h多了下面这几个成员函数和成员变量：
- public:void primTree(int nodeIndex)普利姆算法生成树
- public:void kruskalTree()克鲁斯卡尔算法生成树
- private:int getMinEdge(vector<Edge> edgeVec)获取最小边
- private:bool isInSet(vector<int> nodeSet, int target)判断顶点是否在点集合中
- private:void mergeNodeSet(vector<int> &nodeSetA, vector<int> nodeSetB)合并两个顶点集合
- private:Edge *m_pEdge用来存放最小生成树的边
首先，我们来说说Cmap_tree相比Cmap，新增加的成员变量边类m_pEdge是用来存放最小生成树的边的。
接着来说说void primTree(int nodeIndex)普利姆算法生成树函数传入的参数为最小生成树的起点的索引首先创建一个初值为0的int的value来保存边的权值，初值为0的int的edgeCount来保存边的个数，int动态数组nodeVec存放点的集合（索引），Edge动态数组edgeVec存放备选边的集合。接着打印一下当前顶点，然后将当前顶点（起点）存入nodeVec，并将其访问标志置为true。再接着我们while循环的结束条件为edgeCount<m_iCapacity - 1（边是点的个数减1），在每一次循环里，我们都将nodeVec最尾部的变量保存在整型temp（不能直接把nodeIndex赋值给temp，不然这个循环temp一直不变，都是nodeIndex）。在这之后（还在while循环内），遍历所有顶点，寻找与temp节点连接的所有边，先取出邻接矩阵相应位置的value，判断value是否为0（即是否有边），如果有边，再判断连接的另一个点是否被访问，如果没有，则通过相连接的两个点和权值创建一个边的对象edge，再将边edge放入备选边集合中（不会放重复的边）。遍历结束之后，所有与temp相连接的边都被放入备选边集合中了。然后在从备选边中选取最小的边，将其置为已访问，打印边和权值，保存到最小生成树m_pEdge，edgeCount++。最后找到与当前最小边所连接的下一个点，存入nodeVec（保证下一次循环时temp为下一个点），置为已访问并输出，接着进入while的下一个循环，直到edgeCount < m_iCapacity - 1。
接着来说说我们上一个函数用到的int getMinEdge(vector<Edge> edgeVec)获取最小边函数，其传入的参数为边类动态数组edgeVec（即备选边集合）。首先创建一个初值为0的整型minWeight来保存最小边的权值，初值为0整型edgeIndex存储顶点索引，初值为0整型 i （for循环用）。然后遍历edgeVec，找出第一条没有被访问的边，在每一次循环中，首先判断当前边是否被选中，如果没有则将当前边的权值赋值给minWeight，当前边的索引赋值给edgeIndex，跳出循环。接着判断minWeight是否为0（所有边都被访问过），如果是返回-1。如果不是，从上次循环结束时的 i 继续遍历edgeVec，如果当前边没有被访问过，判断其权值与minWeight的大小，选最小。遍历结束之后，返回的即为最小边的索引。
void kruskalTree()克鲁斯卡尔算法。
- 1、首先创建一个初值为0的整型value存放边的权值，初值为0的int的edgeCount来保存边的个数，存放int动态数组的动态数组nodeSets用来存放不同的顶点数组，存放Edge类的动态数组edgeVec。接着遍历邻接矩阵上三角，将取出所有边保存到edgeVec。
- 2、接着从所有边中不断取出最小边组成生成树的边。
- （1）while循环的结束条件为edgeCount < m_iCapacity -1。
- （2）在每一次循环中，首先从边集合edgeVec中找到最小边的索引存放到整型minEdgeIndex，并置为已访问。
- （3）然后找到最小边的两个端点的索引nodeAIndex、nodeBIndex，定义两个初值为false的布尔变量nodeAIsInSet、nodeBIsInSet来表示端点是否在指定集合中，两个初值为-1的整型变量nodeAInSetLable、nodeBInSetLable来表示两个端点所在集合的索引。
- （4）接着找出点所在的集合，首先遍历nodeSets寻找A点所在集合，在每一个循环中，利用isInSet函数在存放顶点集合的数组nodeSets的第i个数组中寻找A点，如果找到了就将A点所在集合的索引赋值给nodeAInSetLable。同样接着再遍历nodeSets找到寻找B点所在集合。
- （5）根据点所在集合的不同做出不同处理。
- 【a】如果nodeAInSetLable == -1 && nodeBInSetLable == -1，即A点和B点都不在已有的节点集合中，所以AB两个点要放在一个全新的集合中。创建一个存放int的动态数组vec，将A和B的索引存入vec，将vec存入vec。
- 【b】如果nodeAInSetLable == -1 && nodeBInSetLable != -1，即A点不在已有的节点集合中，B点归属某一集合，所以将A点放在B点的集合里边。将A的索引存入nodeSets中B所在的集合，也就是第nodeBInSetLable个集合。
- 【c】如果nodeAInSetLable != -1 && nodeBInSetLable == -1，即B点不在已有的节点集合中，A点归属某一集合，所以将B点放在A点的集合里边。将B的索引存入nodeSets中A所在的集合，也就是第nodeAInSetLable个集合。
- 【d】如果nodeAInSetLable != -1 && nodeBInSetLable != -1 && nodeAInSetLable != nodeBInSetLable，即A点和B点都在已有的节点集合中（两个不同的集合），所以要合并两个集合。利用mergeNodeSet函数将B所在的集合合并到A所在的集合。别忘记把B所在的集合删除，在nodeSets中将B所在的集合后边的所有集合往前移动一个位置。
- 【e】如果nodeAInSetLable != -1 && nodeBInSetLable != -1 && nodeAInSetLable == nodeBInSetLable，即A点和B点都在已有的节点集合中（同一个集合），所以直接跳过本次循环。
- （6）将寻找到的最小边放到最小生成树的边集合中，edgeCount++。输出最小边的两个端点和权值继续下一次的while循环。
bool isInSet(vector<int> nodeSet, int target)判断顶点是否在点集合中函数传入的参数一个是int的动态数组nodeSet，一个是目标顶点的索引target。直接遍历nodeSet，判断target是否在nodeSet中，如果在则返回ture。
void mergeNodeSet(vector<int> &nodeSetA, vector<int> nodeSetB)合并两个顶点集合函数传入的第一个参数为最后留下来的数组nodeSetA的引用，第二个为被吞并的数组nodeSetB。直接遍历nodeSetB，将其的元素保存到nodeSetA中。
最后，来个demo_tree.cpp测试一下。
#demo_tree.cpp
#include "stdafx.h"
#include "iostream"
#include "Cmap_tree.h"
using namespace std;
/*
A
/ \
B- -F--D
\ / \ /
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_tree *pMap = new Cmap_tree(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;
}
运行结果如下：
基本结束啦，所有的代码都上传到 github 了。
网友评论