文章目录

• • 图的概念
  • • • 图(graph)
      • 有向图(directed graph)
      • 无向图(undirected graph)
      • 加权图(weighted graph)
      • 无向完全图(undirected complete graph)
      • 有向完全图(directed complete graph)
      • 子图(subgraph)
      • 稀疏图与稠密图
      • 度
      • 路径与回路
      • 连通图与连通分量
      • 强连通图与强连通分量
      • 生成树
  • 图的存储结构
  • • 1.邻接矩阵
    • • 1.1概念
      • 1.2结构
      • 1.3 操作
      • • 添加顶点AddVertex
        • 添加边弧AddEdge
        • 删除顶点DelVertex
        • 删除边弧DelEdge
      • 1.4特点
    • 2.邻接表
    • • 2.1概念
      • 2.2结构
      • 2.3操作
      • • 添加顶点AddVertex
        • 添加边弧AddEdge
        • 删除顶点DelVertex
        • 删除边弧DelEdge
      • 2.4特点
  • 源代码

图的概念

图(graph)

是由顶点的非空集合V和边或者弧的集合E组成的, 表示为G=(V,E). 以后将用V(G)和E(G)分别表示图G的顶点集合与边/弧集合.

有向图(directed graph)

若图中顶点对是有序的, 即边是有方向的,边集E(G)为有向边的集合, 则图G称为有向图. 一般将边称为弧(arc), 以有序对表示一条从顶点u出发到达顶点v的弧, 其中: u称为弧尾或者起点, v称为弧头或者终点. 在有向图中, 和是不一样的.

无向图(undirected graph)

若图中顶点对是无序的, 即边是无方向的, 边集E(G)为无向边的集合, 则图G称为无向图. 以无序对(u,v)表示u和v之间存在一条无向边. 在无向边中边是对称的, (u,v)和(v,u)表示同一条边.

加权图(weighted graph)

边/弧被赋予一个权值的图称为加权图. 如果图是有向的, 称为加权有向图, 如果是无向的, 称为加权无向图.

无向完全图(undirected complete graph)

在一个无向图中, 如果任意两个顶点都有一条边直接相连, 则称该图为无向完全图. 具有n个顶点的无向图,边的条数范围为[0, n(n-1)/2]. 无向完全图具有n(n-1)/2条边.

有向完全图(directed complete graph)

在一个有向图中, 如果任意一个顶点都有一条弧直接到达其他顶点, 则称该图为有向完全图. 具有n个顶点的有向图, 弧的条数范围[0, n(n-1)]. 有向完全图具有n(n-1)条弧.

子图(subgraph)

设有两个图G和G~, 且满足条件V(G~)是V(G)的子集, V(G~)⊆V(G), 且E(G~)是E(G)的子集, E(G~)⊆E(G), 则称G~是G的子图.

• A,B,C,D都是G的子图.

稀疏图与稠密图

有很少的边或者弧的图称为稀疏图, 反之称为稠密图.

度

图G中, 与顶点v相关联的边的数目, 称为顶点v的度. 有向图中顶点v的度是其入度和出度之和.

• 入度: 有向图中进入某一顶点的边数, 称为该顶点的入度.
• 出度: 有向图中离开某一顶点的边数, 称为该顶点的出度.
• 图中顶点的度数之和是边数的两倍.

路径与回路

• 路径(path): 在无向图G中, 若存在一个从顶点v₁到v_n的顶点序列v₁,v₂,…v_n满足(v_i,v_i+1)∈E(1<=i1到顶点v_n存在一条路径.

• 路径长度(path length): 是指该路径上经过边或者弧的数目. 对于加权图, 路径长度是指该路径中各边权值之和.

• 回路/环(cycle): 若一条路径上的第一个顶点和最后一个顶点相同, 则该路径称为回路或者环.

• 简单路径: 若一条路径上所有的顶点均不重复, 则该路径称为简单路径.

• 简单回路/环: 除第一个顶点与最后一个顶点之外, 其余顶点均不重复出现的回路, 称为简单回路或者简单环.

连通图与连通分量

连通图: 在无向图G中, 若从u到v(u!=v)存在路径, 则称u到v是连通的. 若V(G)中的每一对不同顶点u和v都连通, 则称G是连通图.

连通分量: 无向图G中的极大连通子图称为图G的连通分量.

强连通图与强连通分量

强连通图: 在有向图G中, 若对于V(G)中的每一对不同的顶点u v, 都存在从u到v及v到u的路径, 则称该G是强连通图.

强连通分量: 有向图G中极大强连通子图称为图G的强连通分量.

生成树

生成树: 是连通图的极小连通子图, 它含有图中全部n个顶点, 但只有足以构成一棵树的n-1条边. 在生成树中再添加一条边之后, 必然会形成回路/环.

• 生成树不唯一.

图的存储结构

1.邻接矩阵

1.1概念

• 无向图:

1. 无向图的邻接矩阵一定是对称矩阵, 因此无向图可以压缩存储.
2. 第i行(或者第i列)非零元素个数, 表示顶点v_i的度.

• 有向图:

1. 有向图的邻接矩阵不一定是对称的.
2. 第i行非零元素个数, 表示顶点v_i的出度.
3. 第i列非零元素的个数, 表示顶点v_i的入度.

• 加权图

1.2结构

• _vertexSet : 存储顶点,下标找顶点.
• _vertexIndex : 顶点与下标的映射, 顶点找下标.

如果获取某顶点在邻接矩阵的下标？？？

1. 将存储顶点的一维数组遍历一遍: 时间复杂度O(n).
2. 将顶点和对应的下标存储在红黑树(平衡二叉树)中: 时间复杂度O(log₂n).
3. 将顶点和对应的下标存储在哈希表中: 时间复杂度O(1).

使用第一种方案时间效率低下，使用第三种方案虽然时间效率很高，但是所需空间过大，因为我们采用的邻接矩阵的空间开销已经很大了，所以选择采用第二种方案来进行获取某顶点在邻接矩阵的下标。

• _matrix : 邻接矩阵, 顶点之间的权值.

namespace AdjacentMatrix
{// V:顶点类型 W:权值类型 W_MAX:表示不相连 Directed:无向图与有向图的标识 templateclass Graph{private:std::vector _vertexSet;std::map _vertexIndex;std::vector> _matrix;}
}

1.3 操作

添加顶点AddVertex

		bool AddVertex(const V& v){// 顶点存在不需要继续增加if (GetVertexIndex(v) != -1)return false;_vertexSet.push_back(v);_vertexIndex.insert(std::make_pair(v, _vertexSet.size() - 1));// 先在原有的行上一列for (int i = 0; i < _matrix.size(); i++){_matrix[i].push_back(W_MAX);}// 增加一行_matrix.push_back(std::vector(_vertexSet.size(), W_MAX));return true;}

添加边弧AddEdge

		bool AddEdge(const V& src, const V& dst,const W& weight){int srci = GetVertexIndex(src);int dsti = GetVertexIndex(dst);// 顶点不在图中,添加边失败if (srci == -1 || dsti == -1)return false;_matrix[srci][dsti] = weight;// 如果为无向图,则需要再添加一条dst->src的边if (!Directed){_matrix[dsti][srci] = weight;}return true;}

删除顶点DelVertex

		bool DelVertex(const V& v){int vi = GetVertexIndex(v);// 顶点不在图中,无需删除if (vi == -1)return false;auto pos = std::find(_vertexSet.begin() + vi, _vertexSet.end(), v);if (pos != _vertexSet.end()){_vertexSet.erase(pos);}else{return false;}// 删除该顶点在矩阵中对应的行auto ret = std::find(_matrix.begin()+vi, _matrix.end(), _matrix[vi]);if (ret != _matrix.end()){_matrix.erase(ret);}else{return false;}// 删除该顶点在矩阵中对应的列for (int i = 0; i < _matrix.size(); i++){auto it= std::find(_matrix[i].begin() + vi, _matrix[i].end(), _matrix[i][vi]);if (it != _matrix[i].end()){_matrix[i].erase(it);}else{return false;}}// 顶点与下标的关系需要重新映射std::map tree;for (int i = 0; i < _vertexSet.size(); i++){tree.emplace(_vertexSet[i], i);}_vertexIndex.swap(tree);return true;}

删除边弧DelEdge

		bool DelEdge(const V& src, const V& dst){int srci = GetVertexIndex(src);int dsti = GetVertexIndex(dst);// 顶点不在图中,删除边失败if (srci == -1 || dsti == -1)return false;_matrix[srci][dsti] = W_MAX;if (!Directed){_matrix[dsti][srci] = W_MAX;}return true;}

1.4特点

1. 图的邻接矩阵表示是唯一的.
2. 含有n个顶点的图, 其邻接矩阵的空间代价都是O(n²), 与图的顶点数相关, 与边数无关.
3. 优点: 判断任意两点之间是否有边仅消耗O(1)时间.
4. 缺点: 即使图中的边数很少, 也需O(n²)空间复杂度, 占用空间太大, 存取数据耗费O(n²)的时间, 消耗时间太久.

2.邻接表

2.1概念

• 邻接表: 是将图的顶点的顺序存储结构和各顶点的邻接点的链式存储结构相结合的存储方式.
• 边表: 在邻接表表示法中, 为图中每一个顶点建立一个单链表, 每一个单链表上附设一个头结点.
• 顶点表: 每一个链表设立一个头结点, 头结点有两个域, 数据域vertex存储顶点信息, 指针域firstEdge则指向顶点v_i的第一个邻接点.

	templatestruct EdgeNode{EdgeNode* _next;int _to;W _weight;EdgeNode(int to,const W& weight):_next(nullptr),_to(to),_weight(weight){}};templatestruct VertexNode{V _vertex;EdgeNode* _firstEdge;VertexNode(const V& vertex):_vertex(vertex),_firstEdge(nullptr){}};templateclass Graph{private:std::vector> _table;std::unordered_map _vertexIndex;};

1. 无向图

对于无向图, 第i个顶点的度为第i个链表的结点数.

对于有向图, 第i个顶点的出度是第i个链表的结点数, 求第i个顶点的入度需要遍历整个邻接表.

2.2结构

• _vertexSet : 存储顶点.
• _vertexIndex : 顶点与下标的映射关系.
• _table : 出度顶点表.
• Edge : 相连的顶点边.

namespace AdjacentList
{templatestruct Edge{	int _dsti; // 终点顶点的下标W _weight; // 边的权值struct Edge* _next; // 下一个结点的指针Edge(int dsti, const W& weight):_dsti(dsti),_weight(weight),_next(nullptr){}};templateclass Graph{using Edge = Edge;private:std::vector _vertexSet; // 顶点的集合std::map _vertexIndex; // 顶点映射下标std::vector _table; // 出度顶点表}
}

2.3操作

添加顶点AddVertex

1. 顶点已经在图中, 无需再添加.
2. 将顶点v直接加入到_vertexSet中.
3. 再将该顶点与该顶点对应的下标加入到_vertexIndex.
4. _table也相应加入.

		bool AddVertex(const V& v){if (GetVertexIndex(v) != -1)return false;_vertexSet.push_back(v);_vertexIndex.insert(std::make_pair(v, _vertexSet.size() - 1));_table.push_back(nullptr);return true;}

添加边弧AddEdge

		bool AddEdge(const V& src, const V& dst, const W& weight){int srci = GetVertexIndex(src);int dsti = GetVertexIndex(dst);// 顶点不在图中,添加边失败if (srci == -1 || dsti == -1)return false;Edge* edge = new Edge(dsti, weight);// 头插edge->_next = _table[srci];_table[srci] = edge;// 无向图if (!Directed){edge = new Edge(srci, weight);edge->_next = _table[dsti];_table[dsti] = edge;}return true;}

删除顶点DelVertex

		bool DelVertex(const V& v){int vi = GetVertexIndex(v);// 顶点不在图中,无需删除if (vi == -1)return false;// 将所有与v顶点有关的边删除for (int i = 0; i < _vertexSet.size(); i++){DelEdge(_vertexSet[vi], _vertexSet[i]);}auto pos = std::find(_vertexSet.begin(), _vertexSet.end(), v);if (pos == _vertexSet.end()){return false;}_vertexSet.erase(pos);auto ret = std::find(_table.begin()+vi, _table.end(), nullptr);if (ret == _table.end()){return false;}_table.erase(ret);// 顶点与下标的关系需要重新映射std::map tree;for (int i = 0; i < _vertexSet.size(); i++){tree.emplace(_vertexSet[i], i);}_vertexIndex.swap(tree);return true;}

删除边弧DelEdge

		bool DelEdge(const V& src, const V& dst){int srci = GetVertexIndex(src);int dsti = GetVertexIndex(dst);// 顶点不在图中,删除边失败if (srci == -1 || dsti == -1)return false;// 与单链表的删除相似Edge* prev = nullptr;Edge* curr = _table[srci];while (curr != nullptr){if (curr->_dsti == dsti){if (prev == nullptr){_table[srci] = curr->_next;}else{prev->_next = curr->_next;}delete curr;break;}prev = curr;curr = curr->_next;}if (!Directed){prev = nullptr;curr = _table[dsti];while (curr != nullptr){if (curr->_dsti == srci){if (prev == nullptr){_table[dsti] = curr->_next;}else{prev->_next = curr->_next;}delete curr;break;}prev = curr;curr = curr->_next;}}return true;}

2.4特点

邻接表是图的标准存储方方式, 图的邻接表表示不唯一.

优点: 空间=顶点数+边弧数, 处理时间也是顶点数+边弧数, 即为O(V+E). 在边稀疏的情况下, 用邻接表存储图比用邻接矩阵存储图更节约空间.

缺点: 确定u 与 v 是否有边, 最坏消耗O(n)时间. 无向图同一条边会表示两次, 有向图中寻找某顶点的入度边, 比较费时间.

源代码

[源码地址](three20221229/three20221229 · yx_零叁/C与C++ - 码云 - 开源中国 (gitee.com))