图--邻接矩阵、邻接表、BFS、DFS、Kruskal、Prime
- 一、图的概述
- 1、概述（纯理论部分）
- 2、邻接矩阵（实现一个添加边的图）
- （1）思路介绍
- （2）代码部分
- （3）测试部分
- 3、邻接表（只实现出度表）
- （1）思路介绍
- （2）代码部分
- （3）测试部分
- 二、图的遍历
- 1、图的广度优先遍历
- （1）简介
- （2）代码
- （3）测试用例及测试结果
- （4）面试问答题
- i、题目描述
- ii、思路
- iii、代码
- iv、测试结果
- 2、图的深度优先遍历
- （1）简介
- （2）代码
- （3）测试用例及测试结果
- 3、致命问题：假如说是图本身就不联通，那么DFS和BFS怎么办？
- 三、图的最小生成树
- 1、概念
- 2、Kruskal算法
- （1）简介
- （2）代码实现
- （3）测试用例及测试结果
- 3、prime算法
- （1）简介
- （2）代码
- （3）测试用例及测试结果
一、图的概述
1、概述（纯理论部分）
图是由顶点集合及顶点间的关系组成的一种数据结构：G = (V， E)，其中：
顶点集合V = {x|x属于某个数据对象集}是有穷非空集合；
E = {(x,y)|x,y属于V}或者E = {<x, y>|x,y属于V && Path(x, y)}是顶点间关系的有穷集合，也叫做边的集合。
(x, y)表示x到y的一条双向通路，即(x, y)是无方向的；Path(x, y)表示从x到y的一条单向通路，即Path(x, y)是有方向的。
顶点和边：图中结点称为顶点，第i个顶点记作vi。两个顶点vi和vj相关联称作顶点vi和顶点vj之间有一条边，图中的第k条边记作ek，ek = (vi，vj)或<vi，vj>。
有向图和无向图：在有向图中，顶点对<x, y>是有序的，顶点对<x，y>称为顶点x到顶点y的一条边(弧)，<x, y>和<y, x>是两条不同的边，比如下图G3和G4为有向图。在无向图中，顶点对(x, y)是无序的，顶点对(x,y)称为顶点x和顶点y相关联的一条边，这条边没有特定方向，(x, y)和(y，x)是同一条边，比如下图G1和G2为无向图。注意：无向边(x, y)等于有向边<x, y>和<y, x>。
完全图：在有n个顶点的无向图中，若有n * (n-1)/2条边，即任意两个顶点之间有且仅有一条边，则称此图为无向完全图，比如上图G1；在n个顶点的有向图中，若有n * (n-1)条边，即任意两个顶点之间有且仅有方向相反的边，则称此图为有向完全图，比如上图G4。
邻接顶点：在无向图中G中，若(u, v)是E(G)中的一条边，则称u和v互为邻接顶点，并称边(u,v)依附于顶点u和v；在有向图G中，若<u, v>是E(G)中的一条边，则称顶点u邻接到v，顶点v邻接自顶点u，并称边<u, v>与顶点u和顶点v相关联。
顶点的度：顶点v的度是指与它相关联的边的条数，记作deg(v)。在有向图中，顶点的度等于该顶点的入度与出度之和，其中顶点v的入度是以v为终点的有向边的条数，记作indev(v);顶点v的出度是以v为起始点的有向边的条数，记作outdev(v)。因此：dev(v) = indev(v) + outdev(v)。注
意：对于无向图，顶点的度等于该顶点的入度和出度，即dev(v) = indev(v) = outdev(v)。
路径：在图G = (V， E)中，若从顶点vi出发有一组边使其可到达顶点vj，则称顶点vi到顶点vj的顶点序列为从顶点vi到顶点vj的路径。
路径长度：对于不带权的图，一条路径的路径长度是指该路径上的边的条数；对于带权的图，一条路径的路径长度是指该路径上各个边权值的总和。
2、邻接矩阵（实现一个添加边的图）
（1）思路介绍
我们既然要实现有边有顶点的图，那么必然我们需要先创建一个顶点的集合，顶点和坐标的映射关系以及邻接矩阵的。
我们首先需要实现的是构造函数用的是手动添加边，也就是将我们的顶点集合和邻接矩阵进行扩容至相对应的大小，并且用顶点和坐标的映射关系在进行扩容的过程中进行添加。其次我们就需要添加边了，也就是我们先要得到边的下标（这里直接用顶点和下标关系这个成员函数进行返回即可），无向图就加两次，有向图只用加当前的边即可。最后进行测试即可。
（2）代码部分
// Graph.h
#pragma once
#include <iostream>
#include <vector>
#include <map>
namespace matrix
{
template<class V, class W, W MAX_W = INT_MAX, bool Direct = false>
class Graph
{
private:
std::vector<V> _vertex; // 顶点集合
std::map<V, int> _indexMap; // 顶点映射下标关系
std::vector<std::vector<W>> _matrix; // 邻接矩阵
public:
// 手动添加边
Graph(const V* a, size_t n) // 边和大小
{
_vertex.reserve(n); // 先将顶点扩大到n个大小
for (size_t i = 0; i < n; i++)
{
_vertex.push_back(a[i]); // 插入这条边
_indexMap[a[i]] = i; // 映射关系
}
_matrix.resize(n); // 先将这第一行给设置n个大小
for (int i = 0; i < _matrix.size(); i++)
{
_matrix[i].resize(n, MAX_W); // 之后的每一行都进行扩容
}
}
// 得到顶点下标
size_t GetIndex(const V& v)
{
auto it = _indexMap.find(v);
if (it != _indexMap.end())
{
return it->second;
}
else
{
return -1;
}
}
// 添加边
void AddEdge(const V& src, const V& dst, const W& w)
{
size_t srci = GetIndex(src);
size_t dsti = GetIndex(dst);
_matrix[srci][dsti] = w;
// 无向图（要添加两次）
if (Direct == false)
{
_matrix[dsti][srci] = w;
}
// return ;
}
// 打印
void Print()
{
// 先打印顶点
for (int i = 0; i < _vertex.size(); i++)
{
std::cout << "[" << i << "]" << _vertex[i] << std::endl;
}
std::cout << std::endl;
// 再打印矩阵
// 横坐标
std::cout << " ";
for (int i = 0; i < _matrix.size(); i++)
{
std::cout << i << " ";
}
std::cout << std::endl;
for (int i = 0; i < _matrix.size(); i++)
{
std::cout << i << " ";
for (int j = 0; j < _matrix[i].size(); j++)
{
if (_matrix[i][j] == MAX_W)
{
std::cout << "* ";
}
else
{
std::cout << _matrix[i][j] << " ";
}
}
std::cout << std::endl;
}
std::cout << std::endl;
}
};
void TestGraph1()
{
Graph<char, int, INT_MAX, true> g("0123", 4);
g.AddEdge('0', '1', 1);
g.AddEdge('0', '3', 4);
g.AddEdge('1', '3', 2);
g.AddEdge('1', '2', 9);
g.AddEdge('2', '3', 8);
g.AddEdge('2', '1', 5);
g.AddEdge('2', '0', 3);
g.AddEdge('3', '2', 6);
g.Print();
}
}
（3）测试部分
3、邻接表（只实现出度表）
（1）思路介绍
（2）代码部分
namespace link_table
{
template<class W>
struct Edge
{
int _dsti; // 出度的目标点
W _w; // 权值
Edge<W>* _next; // 链接下一个指针
Edge(int dsti, const W& w)
: _dsti(dsti)
, _w(w)
, _next(nullptr)
{}
};
template<class V, class W, bool Direct = false>
class Graph
{
typedef Edge<W> Edge;
private:
std::vector<V> _vertex; // 顶点集合
std::map<V, int> _indexMap; // 顶点映射下标关系
std::vector<Edge*> _tables; // 邻接表--类似哈希表
public:
// 手动添加边
Graph(const V* a, size_t n) // 边和大小
{
_vertex.reserve(n); // 先将顶点扩大到n个大小
for (size_t i = 0; i < n; i++)
{
_vertex.push_back(a[i]); // 插入这条边
_indexMap[a[i]] = i; // 映射关系
}
_tables.resize(n, nullptr);
}
// 得到顶点下标
size_t GetIndex(const V& v)
{
auto it = _indexMap.find(v);
if (it != _indexMap.end())
{
return it->second;
}
else
{
return -1;
}
}
// 添加边
void AddEdge(const V& src, const V& dst, const W& w)
{
size_t srci = GetIndex(src);
size_t dsti = GetIndex(dst);
Edge* eg = new Edge(dsti, w); // 先new一个结点
eg->_next = _tables[srci];
_tables[srci] = eg;
// 对于无向图来讲
if (Direct == false)
{
Edge* eg = new Edge(srci, w); // 先new一个结点
eg->_next = _tables[dsti];
_tables[dsti] = eg;
}
}
// 打印
void Print()
{
// 先打印顶点
for (int i = 0; i < _vertex.size(); i++)
{
std::cout << "[" << i << "]" << _vertex[i] << std::endl;
}
std::cout << std::endl;
for (int i = 0; i < _tables.size(); i++)
{
std::cout << _vertex[i] << "[" << i << "]->";
Edge* cur = _tables[i];
while (cur)
{
std::cout << _vertex[cur->_dsti] << "[" << cur->_dsti << "]" << "w:" << cur->_w << "->";
cur = cur->_next;
}
std::cout << "nullptr" << std::endl;
}
std::cout << std::endl;
}
};
void TestGraph1()
{
std::string a[] = { "张三", "李四", "王五", "赵六" };
Graph<std::string, int, false> g1(a, 4);
g1.AddEdge("张三", "李四", 100);
g1.AddEdge("张三", "王五", 200);
g1.AddEdge("王五", "赵六", 30);
/*Graph<char, int, true> g("0123", 4);
g.AddEdge('0', '1', 1);
g.AddEdge('0', '3', 4);
g.AddEdge('1', '3', 2);
g.AddEdge('1', '2', 9);
g.AddEdge('2', '3', 8);
g.AddEdge('2', '1', 5);
g.AddEdge('2', '0', 3);
g.AddEdge('3', '2', 6);*/
g1.Print();
}
}
（3）测试部分
有向图：
无向图：
二、图的遍历
1、图的广度优先遍历
（1）简介
首先先明白一下下面的概念性的问题，不过多赘述，直接看简介即可
我们先利用两个具象的图，来进行创建两个队列，一个队列用来进行进入和弹出，另一个数组用来记录是否被访问过了，防止重复访问。
（2）代码
// BFS遍历
void GraphBFS(const V& v)
{
size_t srci = GetIndex(v);
// 创建一个队列（BFS深度优先遍历）和一个vector数组（用来判断是否是已经被访问过了）
std::queue<int> q;
std::vector<bool> visited(_vertex.size(), false);
q.push(srci); // 先push进一个队列中
visited[srci] = true;
while (!q.empty())
{
int front = q.front(); // 先取出对列头
q.pop(); // 弹出头
std::cout << front << _vertex[front] << std::endl;
// 遍历一下这个数组当不等于MAX_W的就是链接的，那么就将它们push进队列中
for (int i = 0; i < _vertex.size(); i++)
{
if (_matrix[front][i] != MAX_W) // 那一列的数值不等于MAX_W的话就push并标记
{
if (visited[i] == false)
{
q.push(i);
visited[i] = true;
}
}
}
}
std::cout << std::endl;
}
（3）测试用例及测试结果
void TestGraphDBFS()
{
std::string a[] = { "张三", "李四", "王五", "赵六", "周七" };
Graph<std::string, int> g1(a, sizeof(a) / sizeof(std::string));
g1.AddEdge("张三", "李四", 100);
g1.AddEdge("张三", "王五", 200);
g1.AddEdge("王五", "赵六", 30);
g1.AddEdge("王五", "周七", 30);
g1.Print();
g1.GraphBFS("张三");
}
（4）面试问答题
i、题目描述
ii、思路
一度好友那么就是我们用一个LevelSize来控制一下每层我们进去的个数即可。
iii、代码
// BFS遍历
void GraphBFS(const V& v)
{
size_t srci = GetIndex(v);
// 创建一个队列（BFS深度优先遍历）和一个vector数组（用来判断是否是已经被访问过了）
std::queue<int> q;
std::vector<bool> visited(_vertex.size(), false);
int LevelSize = 1; // 控制每次出的个数
q.push(srci); // 先push进一个队列中
visited[srci] = true;
while (!q.empty())
{
for (int i = 0; i < LevelSize; i++)
{
int front = q.front(); // 先取出对列头
q.pop(); // 弹出头
std::cout << front << _vertex[front] << " ";
// 遍历一下这个数组当不等于MAX_W的就是链接的，那么就将它们push进队列中
for (int i = 0; i < _vertex.size(); i++)
{
if (_matrix[front][i] != MAX_W) // 那一列的数值不等于MAX_W的话就push并标记
{
if (visited[i] == false)
{
q.push(i);
visited[i] = true;
}
}
}
}
std::cout << std::endl;
LevelSize = q.size();
}
std::cout << std::endl;
}
iv、测试结果
2、图的深度优先遍历
（1）简介
一句话来概括：一条路走到黑，走不通了再回溯，直到回溯到第一个点发现第一个点都没的往外走了则结束！
（2）代码
// 深度遍历子函数
void _GraphDFS(size_t srci, std::vector<bool>& visited)
{
std::cout << srci << _vertex[srci] << std::endl;
visited[srci] = true;
for (size_t i = 0; i < _vertex.size(); i++)
{
if (_matrix[srci][i] != MAX_W && visited[i] == false)
{
_GraphDFS(i, visited);
}
}
}
// 深度遍历--用递归解决
void GraphDFS(const V& src)
{
size_t srci = GetIndex(src);
std::vector<bool> visited(_vertex.size(), false);
_GraphDFS(srci, visited);
}
（3）测试用例及测试结果
void TestGraph1()
{
Graph<char, int, INT_MAX, true> g("0123", 4);
g.AddEdge('0', '1', 1);
g.AddEdge('0', '3', 4);
g.AddEdge('1', '3', 2);
g.AddEdge('1', '2', 9);
g.AddEdge('2', '3', 8);
g.AddEdge('2', '1', 5);
g.AddEdge('2', '0', 3);
g.AddEdge('3', '2', 6);
g.Print();
}
void TestGraphDBFS()
{
std::string a[] = { "张三", "李四", "王五", "赵六", "周七" };
Graph<std::string, int> g1(a, sizeof(a) / sizeof(std::string));
g1.AddEdge("张三", "李四", 100);
g1.AddEdge("张三", "王五", 200);
g1.AddEdge("王五", "赵六", 30);
g1.AddEdge("王五", "周七", 30);
g1.Print();
g1.GraphBFS("张三");
g1.GraphDFS("张三");
}
3、致命问题：假如说是图本身就不联通，那么DFS和BFS怎么办？
如下图所示，假如说是下面这种情况，上面已有的代码中FHI肯定是没有办法被遍历到的！
还记得我们有一个vector<bool>数组吗？我们只需要在DFS和BFS结束后了遍历一遍这个数组，false的值再输出不就好了吗？
DFS新增（BFS新增的也是一样的）：
测试用例：
三、图的最小生成树
1、概念
连通图：在无向图中，若从顶点v1到顶点v2有路径，则称顶点v1与顶点v2是连通的。如果图中任意一对顶点都是连通的，则称此图为连通图。
强连通图：在有向图中，若在每一对顶点vi和vj之间都存在一条从vi到vj的路径，也存在一条从vj到vi的路径，则称此图是强连通图。
生成树：一个连通图的最小连通子图称作该图的生成树。有n个顶点的连通图的生成树有n个顶点和n-1条边。
最小生成树：构成生成树这些边加起来的权值是最小的。
连通图中的每一棵生成树，都是原图的一个极大无环子图，即：从其中删去任何一条边，生成树就不在连通；反之，在其中引入任何一条新边，都会形成一条回路。若连通图由n个顶点组成，则其生成树必含n个顶点和n-1条边。
因此构造最小生成树的准则有三条：
- 只能使用图中的边来构造最小生成树
- 只能使用恰好n-1条边来连接图中的n个顶点
- 选用的n-1条边不能构成回路
核心算法思想：贪心算法。
2、Kruskal算法
（1）简介
任给一个有n个顶点的连通网络N={V,E}，
首先构造一个由这n个顶点组成、不含任何边的图G={V,NULL}，其中每个顶点自成一个连通分量，其次不断从E中取出权值最小的一条边(若有多条任取其一)，若该边的两个顶点来自不同的连通分量，则将此边加入到G中。如此重复，直到所有顶点在同一个连通分量上为止。
大白话就是每次都选最小的边呗，那么我们用一个优先级队列（由小到大排列即可），并且我们为了控制不构成回路的话我们就用我们前面写的并查集，每次取出来一个数的时候就放到同一个并查集中，假如说下一个要取的目标和源数不在这个集合中，那么就不联通就可以添加进最小生成树中。
（2）代码实现
// 先构成一条边
struct Edge
{
size_t _srci;
size_t _dsti;
W _w;
Edge(size_t srci, size_t dsti, const W& w)
: _srci(srci)
, _dsti(dsti)
, _w(w)
{}
// 重载大于函数
bool operator>(const Edge& e) const
{
return _w > e._w;
}
};
// Kruskal算法
W Kruskal(Self& minTree)
{
先初始化一下minTree
size_t n = _vertex.size();
minTree._vertex = _vertex;
minTree._indexMap = _indexMap;
minTree._matrix.resize(n);
for (size_t i = 0; i < n; i++)
{
minTree._matrix[i].resize(n, MAX_W);
}
// 设置一个优先级队列
std::priority_queue<Edge, std::vector<Edge>, std::greater<Edge>> minque;
// 一个一个先都存放进去
for (size_t i = 0; i < n; i++)
{
for (size_t j = 0; j < n; j++)
{
if (i < j && _matrix[i][j] != MAX_W) // i<j是因为保证只存放矩阵一半，保证没有重复
{
minque.push(Edge(i, j, _matrix[i][j]));
}
}
}
// 接下来用来实现算法逻辑，也就是找最小的边加进去同时
// 满足不能在同一个并查集中，也就是先存放到并查集中
// 构建一个并查集
UnionFindSet ufs(n);
// 选出n条边用来和后面的prime算法做比较
int size = 0;
W totalW = W(); // 权值
while (!minque.empty()) // 优先级对列不为空的时候
{
Edge min = minque.top(); // 先把最小的这条边给取出来
minque.pop(); // 弹出
if (!ufs.IsSet(min._srci, min._dsti)) // 判断是不是在一个集合中
{
std::cout << _vertex[min._srci] << "->" << _vertex[min._dsti] << ":" << min._w << std::endl;
minTree._AddEdge(min._srci, min._srci, min._w);
ufs.Union(min._srci, min._dsti);
++size;
totalW += min._w;
}
else
{
std::cout << "构成回路：";
std::cout << _vertex[min._srci] << "->" << _vertex[min._dsti] << ":" << min._w << std::endl;
}
}
if (size == n - 1)
{
return totalW;
}
else
{
return W();
}
//return 0;
}
（3）测试用例及测试结果
void TestGraphMinTree()
{
const char* str = "abcdefghi";
Graph<char, int> g(str, strlen(str));
g.AddEdge('a', 'b', 4);
g.AddEdge('a', 'h', 8);
g.AddEdge('a', 'h', 9);
g.AddEdge('b', 'c', 8);
g.AddEdge('b', 'h', 11);
g.AddEdge('c', 'i', 2);
g.AddEdge('c', 'f', 4);
g.AddEdge('c', 'd', 7);
g.AddEdge('d', 'f', 14);
g.AddEdge('d', 'e', 9);
g.AddEdge('e', 'f', 10);
g.AddEdge('f', 'g', 2);
g.AddEdge('g', 'h', 1);
g.AddEdge('g', 'i', 6);
g.AddEdge('h', 'i', 7);
Graph<char, int> kminTree;
std::cout << "Kruskal:" << g.Kruskal(kminTree) << std::endl;
kminTree.Print();
}
下面是代码需要更改的地方：
测试结果：
3、prime算法
（1）简介
大白话就是加点法，我们在X集合中不断加入最小的边，再Y集合中不断删去已经加入的目标点，那么就不会变成环状了，我们使用一个优先级队列进行维护每次取最小的，只需要判断是不是构成环即可。
所用到的算法思想是：贪心策略。
（2）代码
// Prime算法
W Prim(Self& minTree, const W& src)
{
size_t srci = GetIndex(src);
size_t n = _vertex.size();
minTree._vertex = _vertex;
minTree._indexMap = _indexMap;
minTree._matrix.resize(n);
for (size_t i = 0; i < n; ++i)
{
minTree._matrix[i].resize(n, MAX_W);
}
// 定义两个vector数组
std::vector<bool> X(n, false);
std::vector<bool> Y(n, true);
X[srci] = true; // X集合中的该坐标位置为真 -- 表明从该集合添加
Y[srci] = false; // Y集合中的该坐标位置为假 -- 表明从该集合中删除掉
// 从X->Y集合中连接的边里面选出最小的边
std::priority_queue<Edge, std::vector<Edge>, std::greater<Edge>> minque;
// 遍历一下数组将这个srci添加进去
for (int i = 0; i < n; i++)
{
if (_matrix[srci][i] != MAX_W)
{
minque.push(Edge(srci, i, _matrix[srci][i]));
}
}
// 开始进行prime算法
W totalW = W(); // 权值
size_t size = 0; // 用来记录是否到n-1了
while (!minque.empty())
{
// 取出最小的那个元素
Edge min = minque.top();
minque.pop();
// 判断是否为环 -- 即判断是否是在X这个集合当中
// 最小边的目标点是否是在X集合中
if (X[min._dsti] == true)
{
std::cout << "形成环：";
std::cout << _vertex[min._srci] << "->" << _vertex[min._dsti] << ":" << min._w << std::endl;
}
else
{
minTree._AddEdge(min._srci, min._dsti, min._w);
std::cout << _vertex[min._srci] << "->" << _vertex[min._dsti] << ":" << min._w << std::endl;
X[min._dsti] = true; // 表示已经加到prime刚好遍历的边当中了
Y[min._dsti] = false; // 表明这个Y元素中的边已经被取消掉了
++size;
totalW += min._w;
if (size == n - 1)
{
break;
}
for (size_t i = 0; i < n; i++)
{
if (Y[i] && _matrix[min._dsti][i] != MAX_W)
{
minque.push(Edge(min._dsti, i, _matrix[min._dsti][i]));
}
}
}
}
if (size == n - 1) return totalW;
else return W();
}
（3）测试用例及测试结果
void TestGraphMinTree()
{
const char* str = "abcdefghi";
Graph<char, int> g(str, strlen(str));
g.AddEdge('a', 'b', 4);
g.AddEdge('a', 'h', 8);
g.AddEdge('b', 'c', 8);
g.AddEdge('b', 'h', 11);
g.AddEdge('c', 'i', 2);
g.AddEdge('c', 'f', 4);
g.AddEdge('c', 'd', 7);
g.AddEdge('d', 'f', 14);
g.AddEdge('d', 'e', 9);
g.AddEdge('e', 'f', 10);
g.AddEdge('f', 'g', 2);
g.AddEdge('g', 'h', 1);
g.AddEdge('g', 'i', 6);
g.AddEdge('h', 'i', 7);
/*Graph<char, int> kminTree;
std::cout << "Kruskal:" << g.Kruskal(kminTree) << std::endl;
kminTree.Print();*/
Graph<char, int> pminTree;
std::cout << "Prime:" << g.Prim(pminTree, 'a') << std::endl;
pminTree.Print();
}
