一、前言在算法中一般都需要把问题抽象成图论问题然后用图论的算法解决问题。图论涉及相当多的算法包括图DFS和BFS、连通性、拓扑排序、最小生成树、最短路径、最大流网络、图的着色问题等等图论算法在计算机科学中扮演着很重要的角色它提供了对很多问题都有效的一种简单而系统的建模方式。很多问题都可以转化为图论问题然后用图论的基本算法加以解决。二、图的定义图graph如上图是一个图G一个图由顶点vertex集V和边edge集E组成即G(V, E)和树类似其顶点又称为结点并且边是有意义的如上图(0,1)称为一条边。上图中黑色的带数字的点就是顶点,可抽象成某个事物或对象。顶点之间的线就是边表示事物与事物之间的关系。需要注意的是在图论中边表示的是顶点之间的逻辑关系粗细长短都无所谓的。包括上面的顶点也一样表示逻辑事物或对象画的时候大小形状都无所谓。顶点vertex的属性度数degree与该顶点相关联的总边数一个图G的总度数d(V)等于总边数2倍2E。当图的边具有方向时一个顶点又分为出度out-degree和入度in-degree出度是以该顶点为起点的边数入度是以该顶点为终点的边数。阶数order图G中顶点集V的大小为G的阶数。边又称为线line或弧arc边(u,v)中表示u和v邻接adjacent(u, v) ∈ E边edge的属性一条边是一个顶点对(u,v)u, v ∈ V按照图的顶点对是否有序顶点对有序的图称为有向图directed graph, digraph此时边(u,v)和(v,u)是两条不同的边顶点对无序的图称为无向图undirected graph此时边(u,v)和(v,u)是两条相同的边无向图可看作一个特殊的有向图。有向边 有向边就是固定这一条边只能从x通往yy通往x则不可以。无向边 : 无向边就是一条边可以从x通往yy也可以通往x。自环边: 一条边的起点终点是一个点。平行边 两个顶点之间存在多条边相连接。有权图 权值就是一条边的长度或代价。无权图 不是边的权值为0而是全都为1。稀疏图: 每个顶点的度数较小的图如下图稠密图: 每个顶点的度数较大的图如下图稀疏图有很少条边或弧边的条数|E|远小于|V|²的图称为稀疏图sparse graph。稠密图有很多条边或弧 (边的条数|E|接近|V|²) 的图称为稠密图dense graph。 简单来说我们假设某个图的点的个数 为 N, 边的个数为 M 当 M N ^ 2 (平方)当边数远小于点的平方时称为 稀疏图当 M ≈ N ^ 2 当边数约等于点的平方时称为 稠密图 如果图为稀疏图的时候我们一般用邻接表储存稠密图的时候一般用邻接矩阵存储。三、图的储存那么该怎么去储存图呢1.邻接矩阵邻接矩阵是二维数据 例如g[ ][ ] 时空间需求为V^2,这种存储方式适合存储稠密图邻接矩阵每一位存的是一条边 行代表的是起始点 ,列代表的是终止点,而里面存的值就是这条边的权值一个点到自己的距离是0到没有直接边连接的点的权值是无穷大需要注意的是有向图与无向图的矩阵不同对于无向图当vi、vj之间由边则a[i][j]a[j][i]1,但是有向图若i指向j,只有a[i][j]1,a[j][i]0邻接矩阵要初始化如下1234567for(inti 1; i n1; i)// n1 为数组第一维大小{for(intj 1; j n2; j)// n2 为数组第一维大小{g[i][j] g[j][i] 0 ;}}也可以借助memset来快速地将一个数组中的所有元素都初始化为0。上面的代码等价于1memset(g, 0,sizeof(g));注意memset只能用来初始化0和 -1并且需要加上头文件cstring。123456cinnm;//n表示点的数量,m表示边的数量for(inti 1;i m; i){//枚举输入边cinxyz;//如上描述dis[x][y] z;//有向边dis[x][y] dis[y][x] z;//无向边}2.邻接表又叫链式前向星其实就是链表。邻接表的思想是对于图中的每一个顶点用一个数组来记录这个点和哪些点相连。如果用邻接矩阵表示稀疏图就会浪费大量内存空间而用链接表则是通过把顶点所能到的顶点的边保存在链表中来表示图。步骤1.用 h 数组保存各个节点能到的第一个节点的编号。开始时h[i] 全部为 -1。2.用 e 数组保存节点编号ne 数组保存 e 数组对应位置的下一个节点所在的索引。3.用 idx 保存下一个 e 数组中可以放入节点位置的索引4.插入边使用的头插法例如插入a-b。首先把b节点存入e数组e[idx] b。然后 b 节点的后继是h[a]ne[idx] h[a]。最后a 的后继更新为 b 节点的编号h[a] idx索引指向下一个可以存储节点的位置idx 。模板如下12345678910111213//邻接表constintN 100010, M N * 2;//无向图n条边时最多2n个idx因为每条边在邻接表中会出现两次inth[N], w[N], e[M], ne[M], idx;//n个链表头e每一个结点的值ne每一个结点的next指针// 添加一条边a-bvoidadd(inta,intb,intc){//e记录当前点的值(地址-值),ne下一点的地址(地址-地址)h记录指向的第一个点的地址(值-地址)e[idx] b, w[idx] c, ne[idx] h[a], h[a] idx ;}// 初始化idx 0;memset(h, -1,sizeofh);3.邻接矩阵与邻接表的优缺点对比空间方面当图的顶点数很多、但是边的数量很少时如果用邻接矩阵我们就需要开一个很大的二维数组最后我们需要存储 n*n 个数。但是用邻接表最后我们存储的数据量只是边数的两倍。效率方面用邻接表存图的最大缺点就是随机访问效率低。比如我们需要询问点 a 是否和点 b 连我们就要遍历G[a]检查这个vector里是否有 b 。而在邻接矩阵中只需要根据G[a][b]就能判断。邻接表可以记录重复边如果两个点之间有多条边用邻接矩阵只能记录一条但是用邻接表就能记录多条。虽然重复的边看起来是多余的但在很多时候对解题来说是必要的。因此我们需要对不同的应用情景选择不同的存图方法。如果是稀疏图顶点很多、边很少一般用邻接表如果是稠密图顶点很少、边很多一般用邻接矩阵。