图解图论核心：从基础到邻接矩阵，邻接表实现

keyipatience:个人主页作者简介C/C后端开发学习者专栏传送门《c》《linux》《c高阶数据结构》《c数据结构与算法》⭐️patience is key in life图图的基础知识1.图G(V,E)由两部分组成V顶点集一堆点不能为空E边集点和点之间的连线代表点之间的关系2.无向图 vs 有向图无向图G1、G2边不带箭头(x,y)和(y,x)是同一条边双向互通。有向图G3、G4边带箭头x,y和y,x是两条不一样的边方向不能反过来。3.完全图无向完全图n个点任意两点之间都有一条边总边数公式n(n-1)/2;--(G1)有向完全图n个点任意两点之间互相有一对反向的边,总边数公式n(n-1);--(G2)4.邻接顶点无向图有边直接相连的两个点互为邻接点。有向图边u,vu 指向 v → u 邻接到 vv 邻接自 u。5.顶点的度无向图度deg(v) 和这个点相连的边的数量。有向图出度outdeg从这个点出发的边数量入度indeg指向这个点的边数量总度入度出度握手定理图中所有顶点度数之和 边数 × 26.路径 路径长度路径从起点顺着边走到终点经过的顶点序列。不带权图路径长度 这条路上边的条数带权图边上有数字权值路径长度 路上所有边权值相加权值边附带的信息可以代表距离、时间、成本。例子图里的交通网络图边上数字就是路程施工进度图数字代表工期。7.简单路径 回路环简单路径路径里所有顶点都不重复回路环路径起点和终点是同一个点。8.子图原图G(V,E)新图G1(V1,E1)只要满足V1是原图顶点的子集E1是原图边的子集G1就是G的子图。可以少点、少边但不能出现原图没有的点或者边。9.连通图无向图 强连通图有向图无向连通图任意两个顶点之间都能找到路径走通。强连通图有向图任意一对点(u、v)既能从u走到v也能从v走回u双向互通。10.生成树必须包含原图全部 n 个顶点点一个不能少边是原图里的边但只保留最少数量保证所有点连通即可边数n 个顶点 → n−1 条边2就是1的生成树最小生成树 (MST)所有生成树里边权总和最小的那一棵。邻接矩阵核心思想用二维数组矩阵存顶点之间有没有边矩阵edge[i][j]代表顶点i到顶点j的连接情况。邻接矩阵类型1.无向图 G11无向图邻接矩阵一定对称edge[i][j] edge[j][i]2edge[i][j]1i 和 j 之间有边等于 0没有边2.有向图 G2矩阵不一定对称边有方向edge[A][B]1代表 A→Bedge[B][A]1代表 B→A二者相互独立。3.带权图两点连通矩阵填权值两点不连通填无穷大∞自己到自己填 0一步步实现邻接矩阵1.模板参数templateclass V,class W,W MAX_W,bool Directionfalse1V顶点的数据类型顶点存什么比如string/char2W边的权重类型int、double3MAX_W代表不存在边的权重值无穷大4Directionfalse默认无向图传 true 就是有向图邻接矩阵核心_matrix[i][j]代表顶点 i → 顶点 j 的边权重等于 MAX_W 代表没有这条边2.私有成员vectorV_vertexs; // 保存所有顶点 vector vectorW_matrix; // 邻接矩阵二维数组 mapV,int_indexmap; // 顶点 - 下标 的映射比如顶点A映射到0号下标3.构造函数Graph(const V* vertexs, int n) { _vertexs.assign(vertexs, vertexs n); for (int i 0; i n; i) { _indexmap[_vertexs[i]] i; } _matrix.assign(n, vectorW(n, MAX_W)); }1把传入顶点数组放到_vertexs2循环建立顶点名 → 数组下标map好处用户传顶点比如a不用自己记数字下标类内部自动转成矩阵索引3创建n*n的二维矩阵全部初始化为MAX_W默认无边4.GetVertexIndexint GetVertexIndex(const V v) { auto ret _indexmap.find(v); if (ret _indexmap.end())return -1; else return ret-second; }输入顶点返回它在矩阵里的下标找不到返回 - 1。4._AddEdgevoid _AddEdge(int srci, int dsti,const Ww) { _matrix[srci][dsti] w; if (Direction false)_matrix[dsti][srci] w;//无向图要建立2条 }1srci起点下标dsti终点下标2有向图只设置matrix[srci][dsti]w单向边3无向图默认同时设置matrix[dsti][srci]w双向边5.AddEdgevoid AddEdge(const V src, const V dst, const W w) { int srci GetVertexIndex(src); int dsti GetVertexIndex(dst); _AddEdge(srci, dsti, w); }对外使用直接传顶点名字不用管下标内部自动转下标调用_AddEdge。 示例g.AddEdge(A,B,5)6.Printvoid Print() { //3 部分打印 // 1. 打印顶点和下标映射关系 for (int i 0; i _vertexs.size(); i) { cout _vertexs[i] - i ; } cout endl; cout endl; cout ;//空二格 for (int i 0; i _vertexs.size(); i) { cout i ; } cout endl; // 2. 打印邻接矩阵 for (int i 0; i _matrix.size(); i) { cout i ; for (int j 0; j _matrix[i].size(); j) { if (_matrix[i][j] ! MAX_W) cout _matrix[i][j] ; else cout # ; } cout endl; } cout endl endl; // 3. 打印所有的边注意:打印边的循环 ij如果是有向图时有向边会漏掉不能直接复用,需要去掉 for (size_t i 0; i _matrix.size(); i) { for (size_t j 0; j _matrix[i].size(); j) { if (i j _matrix[i][j] ! MAX_W) { cout _vertexs[i] - _vertexs[j] : _matrix[i][j] endl; } } } }完整代码templateclass V,class W,W MAX_W,bool Directionfalse class Graph { public: Graph(){} Graph(const V* vertexs, int n) { _vertexs.assign(vertexs, vertexs n);//assign(初始迭代器结束迭代器 for (int i 0; i n; i) { _indexmap[_vertexs[i]] i;//建立映射 } _matrix.assign(n, vectorW(n, MAX_W)); } int GetVertexIndex(const V v) { auto ret _indexmap.find(v); if (ret _indexmap.end())return -1; else return ret-second; } void _AddEdge(int srci, int dsti,const Ww) { _matrix[srci][dsti] w; if (Direction false)_matrix[dsti][srci] w;//无向图要建立2条 } void AddEdge(const V src, const V dst, const W w) { int srci GetVertexIndex(src); int dsti GetVertexIndex(dst); _matrix[srci][dsti] w; if (Direction false)_matrix[dsti][srci] w;//无向图要建立2条 } void Print() { //3部分打印 // 1. 打印顶点和下标映射关系 for (int i 0; i _vertexs.size(); i) { cout _vertexs[i] - i ; } cout endl; cout endl; cout ;//空二格 for (int i 0; i _vertexs.size(); i) { cout i ; } cout endl; // 2. 打印邻接矩阵 for (int i 0; i _matrix.size(); i) { cout i ; for (int j 0; j _matrix[i].size(); j) { if (_matrix[i][j] ! MAX_W) cout _matrix[i][j] ; else cout # ; } cout endl; } cout endl endl; // 3. 打印所有的边注意:打印边的循环 ij如果是有向图时有向边会漏掉不能直接复用,需要去掉 for (size_t i 0; i _matrix.size(); i) { for (size_t j 0; j _matrix[i].size(); j) { if (i j _matrix[i][j] ! MAX_W) { cout _vertexs[i] - _vertexs[j] : _matrix[i][j] endl; } } } } private: vectorV_vertexs; vector vectorW_matrix; mapV,int_indexmap; };测试用例void TestGraph() { Graphchar, 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(); }结果邻接表链表版邻接表邻接表使用数组表示顶点的集合使用链表表示边的关系。邻接表类型1. 无向图邻接表存储2.有向图邻接表存储实际我们实现的时候不用分别实现入边表和出边表2个表普通邻接表只存【出边】一条就够不需要额外再单独开一张表专门存入边。并且绝大多数算法DFS、BFS、Dijkstra、拓扑排序只需要遍历一个点所有往外走的边只需要出边表只用_linktable就足够。一步步实现邻接表1.Edge 边结构体单链表节点templateclass W struct Edge { int _dsti; // 目标顶点的下标重点不是顶点值是在_vertexs里的索引 W _w; // 边权 EdgeW* next; // 指向下一条边的指针邻接表是单链表 EdgeW(const int dsti-1,const WwW()) :_dsti(dsti) ,_w(w) ,next(nullptr) { } };2. Graph 类成员变量privatevectorV _vertexs; // 顶点数组 mapV, int _indexmap; // key:顶点值Vvalue:顶点下标i,顶点和下标映射 vectorEdge* _linktable; // 邻接表数组每个元素是边链表头指针eg 顶点A(0), B(1), C(2)_linktable[0]是顶点 A 的边链表头存 A 所有出去的边_linktable[1]是顶点 B 的边链表头3.构造函数Graph(const V* vertexs, int n) { _vertexs.assign(vertexs, vertexs n); for (int i 0; i n; i) { _indexmap[_vertexs[i]] i; // 顶点值映射到下标 } _linktable.assign(n, nullptr); // n个顶点n条空链表初始都是nullptr }4.GetVertexIndexint GetVertexIndex(const V v) { auto ret _indexmap.find(v); if (ret _indexmap.end())return -1; else return ret-second; }5.AddEdge 添加边核心区分有向 / 无向void AddEdge(const V src, const V dst, const Ww) { int srci GetVertexIndex(src); //源顶点下标 int dsti GetVertexIndex(dst); //目标顶点下标 // 头插法新建边插到srci对应的链表头部 Edge* newedge new Edge(dsti,w); newedge-next _linktable[srci]; _linktable[srci] newedge; // Directionfalse 无向图双向都要加边 if (Direction false) { Edge* newedge2 new Edge(srci, w); newedge2-next _linktable[dsti]; _linktable[dsti] newedge2; } }6.Printvoid Print() { // 第一部分打印【顶点编号和名字】 for (size_t i 0; i _vertexs.size(); i) { cout [ i ] - _vertexs[i] endl; } cout endl; // 第二部分遍历邻接表 _linktables for (size_t i 0; i _linktable.size(); i) { // 打印起点顶点名字[下标] cout _vertexs[i] [ i ] -; // cur拿到这个顶点对应的边链表头指针 Edge* cur _linktable[i]; while (cur) { // cur-_dsti目标顶点下标 // _vertexs[cur-_dsti]目标顶点名字 cout _vertexs[cur-_dsti] [ cur-_dsti ] cur-_w -; cur cur-_next; } cout nullptr endl; } }完整代码namespace LinkTable { templateclass W struct Edge { //不需要srci int _dsti; W _w; EdgeW* next; EdgeW(const int dsti -1,const W wW()) :_dsti(dsti) , _w(w) , next(nullptr) { } }; templateclass V, class W, bool Direction false class Graph { public: typedef EdgeW Edge; Graph(const V* vertexs, int n) { _vertexs.assign(vertexs, vertexs n);//assign(初始迭代器结束迭代器 for (int i 0; i n; i) { _indexmap[_vertexs[i]] i;//建立映射 } _linktable.assign(n, nullptr); } int GetVertexIndex(const V v) { auto ret _indexmap.find(v); if (ret _indexmap.end())return -1; else return ret-second; } void AddEdge(const V src, const V dst, const W w) { int srci GetVertexIndex(src); //源顶点下标 int dsti GetVertexIndex(dst); //目标顶点下标 // 头插法新建边插到srci对应的链表头部 Edge* newedge new Edge(dsti, w); newedge-next _linktable[srci]; _linktable[srci] newedge; // Directionfalse 无向图双向都要加边 if (Direction false) { Edge* newedge2 new Edge(srci, w); newedge2-next _linktable[dsti]; _linktable[dsti] newedge2; } } void Print() { // 第一部分打印【顶点编号和名字】 for (size_t i 0; i _vertexs.size(); i) { cout [ i ] - _vertexs[i] endl; } cout endl; // 第二部分遍历邻接表 _linktable for (size_t i 0; i _linktable.size(); i) { // 打印起点顶点名字[下标] cout _vertexs[i] [ i ] -; // cur拿到这个顶点对应的边链表头指针 Edge* cur _linktable[i]; while (cur) { // cur-_dsti目标顶点下标 // _vertexs[cur-_dsti]目标顶点名字 cout _vertexs[cur-_dsti] [ cur-_dsti ] cur-_w -; cur cur-next; } cout nullptr endl; } } private: vectorV_vertexs; mapV, int_indexmap; vectorEdge*_linktable; };测试例子void TestGraph() { string a[] { 张三, 李四, 王五, 赵六 }; Graphstring, int g1(a, 4); g1.AddEdge(张三, 李四, 100); g1.AddEdge(张三, 王五, 200); g1.AddEdge(王五, 赵六, 30); g1.Print(); }结果具体过程下标0 张三1 李四2 王五3 赵六0.最开始_linktable[0]: null _linktable[1]: null _linktable[2]: null _linktable[3]: null1.AddEdge (张三李四100)给 0 号张三链表加 E1 (目标 1权重 100)给 1 号李四链表加 E2 (目标 0权重 100)_linktable[0]: E1(1,100) → null _linktable[1]: E2(0,100) → null _linktable[2]: null _linktable[3]: null2.AddEdge (张三王五200)给 0 号张三链表头插E3 (目标 2权重 200)E3 连在 E1 前面给 2 号王五链表加 E4 (目标 0权重 200)_linktable[0]: E3(2,200) → E1(1,100) → null _linktable[1]: E2(0,100) → null _linktable[2]: E4(0,200) → null _linktable[3]: null3.AddEdge (王五赵六30)给 2 号王五链表头插E5 (目标 3权重 30)E5 连在 E4 前面给 3 号赵六链表加 E6 (目标 2权重 30)最终_linktable[0]: E3(2,200) → E1(1,100) → null _linktable[1]: E2(0,100) → null _linktable[2]: E5(3,30) → E4(0,200) → null _linktable[3]: E6(2,30) → null邻接矩阵和邻接表对比邻接矩阵查边超快遍历邻点慢稠密图用顶点一多空间爆炸。邻接表遍历邻点超快查两点之间边慢稀疏图用节省大量内存。边少 稀疏边满 稠密。egn1000 个顶点邻接矩阵要开 1000×1000 100 万空间就算只有 10 条边也要占用这么多内存邻接表只存这 10 条边内存开销很小对比项邻接矩阵邻接表存储结构二维数组matrix[i][j]matrix[i][j]存 i→j 边权MAX_W 代表无边vectorEdge*链表数组每个数组元素就是一个链表空间复杂度O(n2)只和顶点数有关和边无关O(nE)顶点 实际边边越少越省空间适合图稠密图边很多稀疏图边很少查询 i,j 两点有没有边直接matrix[i][j]O(1)需要遍历 i 的邻接链表最坏O(n)遍历一个顶点的所有邻边要循环全部 n 个点O(n)直接遍历链表出边数量很快新增边O(1)直接赋值O(1)尾插节点删除边O(1)直接赋值 MAX_W需要遍历链表找到该边慢DFS和BFS以邻接矩阵实现BFS:void BFS(const V v) { cout BFS:; int srci GetVertexIndex(v); if (srci -1) { cout 顶点不存在 endl; return; } vectorboolvis(_vertexs.size(), false); queueintq;//存下标 q.push(srci); vis[srci] true; while (q.size()) { int front q.front(); q.pop(); cout _vertexs[front] ; for (int i 0; i _vertexs.size(); i)//把和相邻的全部找出来 { if (_matrix[front][i]!MAX_W !vis[i]) { q.push(i); vis[i] true; } } } cout endl; }DFSvoid DFS(const Vv) { cout DFS:; int srci GetVertexIndex(v); if (srci -1) { cout 顶点不存在 endl; return; } vectorboolvis(_vertexs.size(),false); _dfs(srci, vis); } void _dfs(int srci, vectorbool vis)//引用vis相当于全局 { cout _vertexs[srci] ; vis[srci] true; for (int i 0; i _vertexs.size(); i) { if (_matrix[srci][i] ! MAX_W !vis[i]) { _dfs(i, vis); } } }