我要评论
1. 前言
相信在大学中学过离散数学这门课的同学一定对图比较熟悉. 为了照顾没有学习过图的同学,本系列文章会当作无基础来讲解
本章重点:
2. 图的基本概念
图是由顶点集合,以及边集合组成的一种数据结构: g = (v,e).
概念很抽象,可以简化为下图:
3. 关于图的专业名词
完全图:在有n个顶点的无向图中，若有n * (n-1)/2条边，即任意两个顶点之间有且仅有一条边,则称此图为无向完全图. 上图的g1就是无向完全图, g4为有向完全图邻接顶点:若顶点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)。
路径:若顶点a可以到达顶点b, 则从a到b经过的所有顶点就是a到b的路径. 对于不带权图,路径长度等于边数之和,带权图则是权值之和
简单路径与回路:一条路径中如果没有重复的点,那么就是简单路径,有重复的点证明有回路连通图:连通图：在无向图中，若从顶点v1到顶点v2有路径，则称顶点v1与顶点v2是连通的。如果图中任意一对顶点都是连通的，则称此图为连通图
4. 图的存储结构
因为图中既有节点，又有边(节点与节点之间的关系)，因此，在图的存储中，只需要保存：节点和边关系即可。节点保存比较简单，只需要一个数组存储即可，那边关系该怎么保存呢？
图的存储结构分为:
- 邻接矩阵
- 邻接表
4.1 邻接矩阵
因为节点与节点之间的关系就是连通与否，即为0或者1，因此邻接矩阵(二维数组)即是：先用一个数组将定点保存，然后采用矩阵来表示节点与节点之间的关系. 如一个图有n个顶点, 那么就开辟一个n×n的二维数组. 数组下标(i,j)位置存储的值代表,顶点i到j是否有边,用0/1表示.
如果边带有权值，并且两个节点之间是连通的，上图中的边的关系就用权值代替，如果两个顶点不通，则使用无穷大代替
4.2 邻接表
邻接表: 用数组表示顶点的集合,用链表表示边的关系
无向图邻接表存储:
a,b,c,d的下标分别是0,1,2,3.所以a顶点有两个相邻的顶点b和c. 链表中存的就是1,2
有向图邻接表存储:
4.3 优缺点分析
5. 图的模拟实现
首先, 使用邻接矩阵版本的图, 需要一个一维数组来存储顶点的集合, 需要一个二维数组来存储边的集合. 除此之外, 由于我们全程使用的是顶点的下标, 所以还需要一个map来存储顶点下标和顶点的值的对应关系.
框架代码:
template<class v, class w, w max_w = int_max, bool direction = false>
class graph
{
public:
//图的创建方法: 1. io输入(不方便测试) 2. 样例写在文件中,读取文件 3. 手动添加边
graph(const v* a,size_t n)
{
_vertex.reserve(n);
for (int i = 0; i < n; i++)
{
_vertex.push_back(a[i]);
_index[a[i]] = i;
}
_edge.resize(n);
for (int i = 0; i < n; i++)
_edge[i].resize(n, max_w);
}
private:
vector<v> _vertex; //图的顶点集合
vector<vector<w>> _edge;//图的边的集合
unordered_map<v, int> _index;//存储顶点和它映射到vector的下标的关系
};
完整的代码:
//邻接矩阵版本
template<class v, class w, w max_w = int_max, bool direction = false>
class graph
{
public:
//图的创建方法: 1. io输入(不方便测试) 2. 样例写在文件中,读取文件 3. 手动添加边
graph(const v* a,size_t n)
{
_vertex.reserve(n);
for (int i = 0; i < n; i++)
{
_vertex.push_back(a[i]);
_index[a[i]] = i;
}
_edge.resize(n);
for (int i = 0; i < n; i++)
_edge[i].resize(n, max_w);
}
//找到顶点对应的下标
size_t getindex(const v& v)
{
if (_index.find(v) == _index.end())
{
cout << "要添加的边的顶点不存在" << endl;
return -1;
}
return _index[v];
}
void addedge(const v& src, const v& dest, const w& w)//向图中添加边(源点,目标点,以及权值)
{
size_t srci = getindex(src);
size_t desti = getindex(dest);
_edge[srci][desti] = w;
if (direction == false)
_edge[desti][srci] = w;
}
void print()
{
//打印顶点
for (int i = 0; i < _edge[0].size(); i++)
cout << "[" << i << "]" << "->" << _vertex[i] << endl;
cout << endl;
//打印矩阵
for (int i = 0; i < _edge[0].size(); i++)
{
for (int j = 0; j < _edge[0].size(); j++)
{
if (_edge[i][j] == max_w)
cout << "* ";
else cout << _edge[i][j] << " ";
}
cout << endl;
}
cout << endl;
}
private:
vector<v> _vertex; //图的顶点集合
vector<vector<w>> _edge;//图的边的集合
unordered_map<v, int> _index;//存储顶点和它映射到vector的下标的关系
};
void testgraph()
{
graph<char, int, -1, 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();
}
6. 总结以及拓展
其实模拟实现图的意义并不是简单的实现添加边的函数. 而是为了后面关于图的各种算法做铺垫. 图的学习难度会越来越大, 加油吧, 少年.
发表评论