南京网站公司,seo搜索引擎优化名词解释,制作网站一般多少钱,邯郸市嘉禾网络科技文章目录 1. 图的基本概念1.1 什么是图1.2 有向图和无向图1.3 完全图1.4 邻接顶点1.5 顶点的度1.6 路径1.7 路径长度1.8 简单路径与回路1.9 子图1.10 连通图1.11 强连通图1.12 生成树 2. 图的存储结构2.1 邻接矩阵2.2 邻接矩阵代码实现结构定义构造函数添加边打印图测试 2.3 邻… 文章目录 1. 图的基本概念1.1 什么是图1.2 有向图和无向图1.3 完全图1.4 邻接顶点1.5 顶点的度1.6 路径1.7 路径长度1.8 简单路径与回路1.9 子图1.10 连通图1.11 强连通图1.12 生成树 2. 图的存储结构2.1 邻接矩阵2.2 邻接矩阵代码实现结构定义构造函数添加边打印图测试 2.3 邻接表2.4 邻接表代码实现结构定义构造函数添加边打印图测试 3. 源码3.1 Graph.h3.2 Test.cpp 这篇文章开始我们来学习一种高阶数据结构——图 1. 图的基本概念
1.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条边记作ekek (vivj)或vivj。 1.2 有向图和无向图
图分为有向图和无向图 有向图中顶点对x, y是有序的顶点对xy称为顶点x到顶点y的一条边(弧)x, y和y, x是两条不同的边比如下图G3和G4为有向图 无向图中顶点对(x, y)是无序的顶点对(x,y)称为顶点x和顶点y相关联的一条边这条边没有特定方向(x, y)和(yx)是同一条边比如下图G1和G2为无向图 注意无向边(x, y)等于有向边x, y和y, x。 简单总结一下 图是一种非线性的数据结构用于表示元素之间的关系。它由节点也称为顶点和连接节点的边组成。每个节点可以与其他节点直接或间接连接这些连接关系可以具有方向性有向图或无方向性无向图。因此图可用于表示各种关系如网络、社交关系、地图等并且在计算机科学和现实生活中有广泛的应用。 1.3 完全图 在有n个顶点的无向图中若有n * (n-1)/2条边即任意两个顶点之间有且仅有一条边则称此图为无向完全图比如上图G1 在n个顶点的有向图中若有n * (n-1)条边即任意两个顶点之间有且仅有两条方向相反的边则称此图为有向完全图比如上图G4 1.4 邻接顶点 在无向图中G中若(u, v)是E(G)中的一条边则称u和v互为邻接顶点并称边(u,v)依附于顶点u和v 在有向图G中若u, v是E(G)中的一条边则称顶点u邻接到v顶点v邻接自顶点u并称边u, v与顶点u和顶点v相关联。 1.5 顶点的度 顶点v的度是指与它相关联的边的条数记作deg(v)。 在有向图中顶点的度等于该顶点的入度与出度之和其中顶点v的入度是以v为终点的有向边的条数记作indev(v)顶点v的出度是以v为起始点的有向边的条数记作outdev(v)。因此dev(v) indev(v) outdev(v)。 注意对于无向图顶点的度等于该顶点的入度和出度即dev(v) indev(v) outdev(v)。 1.6 路径 在图G (V E)中若从顶点vi出发有一组边使其可到达顶点vj则称顶点vi到顶点vj的顶点序列为从顶点vi到顶点vj的路径。 比如在上面这个有向图中顶点1到顶点7的路径有 1367 147 可能有多条 1.7 路径长度 对于不带权的图一条路径的路径长度是指该路径上的边的条数对于带权的图一条路径的路径长度是指该路径上各个边权值的总和 1.8 简单路径与回路 若路径上各顶点v1v2v3…vm均不重复则称这样的路径为简单路径。 若路径上第一个顶点v1和最后一个顶点vm重合则称这样的路径为回路或环。 1.9 子图 设图G {V, E}和图G1 {V1E1}若V1属于V且E1属于E则称G1是G的子图即G1的顶点和边都是原图的一部分 1.10 连通图 在无向图中若从顶点v1到顶点v2有路径则称顶点v1与顶点v2是连通的 如果图中任意一对顶点都是连通的则称此图为连通图。 1.11 强连通图 在有向图中若每一对顶点vi和vj之间都存在一条从vi到vj的路径也存在一条从vj到vi的路径则称此图是强连通图 1.12 生成树 无向图中一个连通图的最小连通子图称作该图的生成树。 有n个顶点的连通图的生成树有n个顶点和n-1条边。 比如 2. 图的存储结构
因为图中既有节点又有边(节点与节点之间的关系)因此在图的存储中只需要保存节点和边关系即可。 节点保存比较简单只需要一段连续空间即可那边关系该怎么保存呢
2.1 邻接矩阵
首先我们来学习图的第一种存储结构——邻接矩阵
那邻接矩阵是如何保存图的顶点和边呢 因为节点与节点之间的关系就是连通与否即为0或者1因此邻接矩阵(二维数组)即是先用一个数组将顶点保存然后采用矩阵来表示节点与节点之间的关系边 比如 值为1就表示对应的这两个顶点是连通的为0就表示两个顶点不连通 那其实观察上面的图我们可以发现 无向图的邻接矩阵是对称的第i行(列)元素之和就是顶点i的度边没有权值只存0/1的情况下元素和就是度 有向图的邻接矩阵则不一定是对称的第i行(列)元素之和就是顶点i 的出(入)度边没有权值只存0/1的情况下 另外呢 1. 如果边带有权值并且两个节点之间是连通的上图中的边的关系1/0就用权值代替如果两个顶点不通可以使用无穷大代替后面我们实现的时候就要增加一个表示无穷大的模板参数 2. 用邻接矩阵存储图的优点是能够快速知道两个顶点是否连通取到权值 3. 缺陷是如果顶点比较多边比较少时矩阵中存储了大量的0成为系数矩阵比较浪费空间所以邻接矩阵比较适合存储稠密图边比较多的图不适合存储稀疏图边比较少的图 而且要求两个节点之间的路径不好求 还有求一个顶点相连的顶点有哪些也不好求O(N)这个用后面的邻接表结构存储的话就很好求。 2.2 邻接矩阵代码实现
那下面我们就来实现一下邻接矩阵
结构定义
那我们这里呢还是搞成模板因为顶点的值可以是任意类型那我们的模板都需要给哪些参数呢 这里我们先给了3个模板参数解释一下 V接收顶点vertex的类型W接收权值的类型权值不一定非得是整数,然后我们再给一个非类型模板参数来决定我们要定义的图是有向图还是无向图(比如Directionfalse就是无向图等于true就是有向图)一般用无向图居多所以可以给个缺省值false我们不传默认就是无向图。 那现在图里面要存顶点和边 顶点呢我们就可以用一个vector来存储。 那边我们要如何存呢 上面有提到邻接矩阵是用一个二维数组即矩阵来存储边顶点之间的关系的我们可以再来看一下图 那这里就涉及到一个问题 这里面二维数组的每一个下标是不是都要跟一个顶点进行映射啊。 比如二维数组中某一个元素_vertexs[i][j]是1那就表示下标i和j对应的两个顶点是连通的。 那怎么建立顶点和数组下标的映射呢 我们上一篇文章并查集里面其实就讲了一种方法我们当时说了图里面也会用到。 用一个map就搞定了嘛。 构造函数
然后我们来想一下构造函数可以怎么写? 那我们可以这样搞: 创建一个图对象的时候可以先把顶点存一些给一个顶点的数组就可以然后后面我们可以再增加一个增加边的接口我们可以手动创建边和赋权值。 所以构造函数 就可以这样写 添加边
然后我们来增加一个添加边的接口 那首先我们要获取一下顶点的下标因为我们添加边其实就是在邻接矩阵里面改这两个顶点对应位置的值嘛 可以再封装一个接口 然后AddEdge里面我们就可以获取两个顶点对应的下标然后在邻接矩阵里面添加边 然后添加边这里有一个问题 我们的代码是要同时针对有向图和无向图的如果是无向图的话我们添加一条边比如AB那就完了但是如果是有向图添加AB就是AB如果要添加BA的就需要再添加一次。 所以我们这样写 打印图
然后我们再写一个打印搞些数据测试一波 测试 来测试一下 我们就以这个为例 运行一下 没问题只不过上面图中ij相等的位置打印的是0 2.3 邻接表
邻接表 使用数组存储顶点的集合使用链表存储顶点的关系边。 比如 无向图邻接表存储 一个顶点与哪些顶点相连相连的顶点就存到这个顶点对应的链表中当然如果带权的话也要存上对应边的权值。 每个顶点都有一个对应的链表多条链表用一个指针数组就可以维护起来 注意无向图中同一条边在邻接表中出现了两次。如果想知道顶点vi的度只需要知道顶点vi 对应链表集合中结点的数目即可 有向图邻接表存储 那通过上面的了解其实我们可以得出对于邻接表的存储方式 1. 适合存储稀疏图边比较少的图因为邻接表的话有多少边链表里面就存几个对应的顶点不需要额外的空间而上面邻接矩阵不论边多边少都要开一个N*N的矩阵二维数组边少的时候那就大部分位置都存的是0 2. 方便查找从一个顶点连接出去的边有哪些因为它对应的边链表里面存的就是与这个顶点相连的顶点 3. 但是不方便确定两个顶点是否相连和获取权值要遍历其中一个顶点的边链表查找O(N) 2.4 邻接表代码实现
那我们再来实现一下邻接表。
结构定义
首先来定义一下邻接表的结构 首先对于邻接表来说模板参数这里就不需要MAX_W这个非类型模板参数了。 因为上面邻接矩阵之所以需要是因为矩阵不相连的边矩阵里面对应得位置要存这个值来标识一下但是邻接表我们上面了解了每个顶点连接的边有多少就存多少个顶点不相连的顶点直接是不存的。 然后呢顶点我们还是用一个vector来存还要建立顶点根下标的映射每个顶点要跟指针数组的下标一一对应与邻接矩阵不同的在于这里的边要用链表来存一个顶点与哪些顶点相连相连的顶点就存到这个顶点对应的边链表中。 如果带权的话还要存上权值所以我们可以把边链表封装成一个类 其实就是一个链表的结构因为我们要用链表来存储边嘛 然后图的结构里面 邻接表其实就是一个指针数组嘛每个位置存一个指针指针指向一个链表该位置的下标就映射对应的顶点对应的链表里面存的就是与之相连的顶点以及对应边的权值 构造函数
那下面我们来写一下邻接表结构图的构造函数 逻辑其实根上面邻接矩阵是一样的 添加边
然后添加边 首先还是获取一下边的起始顶点和终止顶点映射的下标 然后添加边的时候 如果是无向图比如添加一个边AB那要在A的链表里面挂B顶点也要在B的链表里面挂A顶点 如果是有向图只在A的链表里面挂B就行了当然有向图的话我们看到上面还分为出边表和入边表但是入边表一般不需要搞我们这里就只存一个出边表有需要的话可以再添加 所以呢添加的逻辑我们这样写 打印图
那我们再来写个打印的函数然后测试一下 这个函数没什么难度就不解释了 测试
然后我们来搞一组数据测试一下 我们这里不传第三个模板参数默认是无向图 看一下结果 没问题 我们也可以试一下有向图 也没问题 3. 源码
3.1 Graph.h
#pragma once//邻接矩阵
namespace matrix
{templateclass V, class W, W MAX_W INT_MAX, bool Direction falseclass Graph{public:Graph(const V* ver, size_t n){//存储顶点并与下标建立映射_vertexs.reserve(n);for (size_t i 0; i n; i){_vertexs.push_back(ver[i]);_indexMap[ver[i]] i;}//给邻接矩阵开空间_matrix.resize(n);for (auto e : _matrix){e.resize(n, MAX_W);}}size_t GetVertexIndex(const V v){auto it _indexMap.find(v);if (it ! _indexMap.end()){return it-second;}else{throw invalid_argument(顶点不存在);return -1;}}void AddEdge(const V src, const V dst, const W w){size_t srci GetVertexIndex(src); size_t dsti GetVertexIndex(dst);_matrix[srci][dsti] w;if (Direction false)//无向图{_matrix[dsti][srci] w;}}void Print(){// 打印顶点和下标映射关系for (size_t i 0; i _vertexs.size(); i){cout _vertexs[i] - i ;}cout endl endl;cout ;for (size_t i 0; i _vertexs.size(); i){cout i ;}cout endl;// 打印矩阵for (size_t i 0; i _matrix.size(); i){cout i ;for (size_t j 0; j _matrix[i].size(); j){if (_matrix[i][j] ! MAX_W)cout _matrix[i][j] ;elsecout # ;}cout endl;}cout endl endl; 打印所有的边//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;//顶点集合mapV, int _indexMap;//顶点和下标建立映射vectorvectorW _matrix;//存储边的矩阵};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();}
}//邻接表
namespace link_table
{templateclass Wstruct Edge{int _dsti;//边的终止顶点下标W _w; //权值EdgeW* _next;Edge(const int dsti, const W w):_dsti(dsti),_w(w),_next(nullptr){}};templateclass V, class W, bool Direction falseclass Graph{typedef EdgeW Edge;public:Graph(const V* ver, size_t n){//存储顶点并与下标建立映射_vertexs.reserve(n);for (size_t i 0; i n; i){_vertexs.push_back(ver[i]);_indexMap[ver[i]] i;}//给邻接表开空间_tables.resize(n, nullptr);}size_t GetVertexIndex(const V v){auto it _indexMap.find(v);if (it ! _indexMap.end()){return it-second;}else{throw invalid_argument(顶点不存在);return -1;}}void AddEdge(const V src, const V dst, const W w){size_t srci GetVertexIndex(src);size_t dsti GetVertexIndex(dst);//src-dstEdge* eg new Edge(dsti, w);eg-_next _tables[srci];_tables[srci] eg;//如果是无向图再添加反向边dst-srcif (Direction false){Edge* eg new Edge(srci, w);eg-_next _tables[dsti];_tables[dsti] eg;}}void Print(){// 打印顶点for (size_t i 0; i _vertexs.size(); i){cout [ i ] - _vertexs[i] endl;}cout endl;//遍历打印每个顶点的边链表for (size_t i 0; i _tables.size(); i){cout _vertexs[i] [ i ]-;Edge* cur _tables[i];while (cur){cout [ _vertexs[cur-_dsti] : cur-_dsti : cur-_w ]-;cur cur-_next;}cout nullptr endl;}}private:vectorV _vertexs;//顶点集合mapV, int _indexMap;//顶点和下标建立映射vectorEdge* _tables; // 邻接表};void TestGraph(){string a[] { 张三, 李四, 王五, 赵六 };Graphstring, int, true g1(a, 4);g1.AddEdge(张三, 李四, 100);g1.AddEdge(张三, 王五, 200);g1.AddEdge(王五, 赵六, 30);g1.Print();}
}3.2 Test.cpp
#define _CRT_SECURE_NO_WARNINGS#include iostream
using namespace std;
#include vector
#include map
#include string
#include Graph.hint main()
{//matrix::TestGraph();link_table::TestGraph();return 0;
}
