当一个图为稀疏图时，使用邻接矩阵表示法显然要浪费大量的存储空间。而图的邻接表示法结合了顺序存储和链式存储方法，大大减少了这种不必要的浪费。
邻接表作为图的一种存储方式，在存储稀疏图上相对于邻接矩阵有相当大的空间节省。如一个稀疏图的顶点个个数为n，边数为e。用邻接矩阵存储需要n^2空间，而真正进行存储的只有2e个空间， 剩下的n^2-2e都浪费了。但是对于邻接表来讲，存储空间只需要n+2e个，相对于邻接矩阵减少了很多。邻接表虽然在空间上有很大的优势，但是对于一个有向图，如果需要查找每个顶点的入度就需要遍历整个邻接表，在效率上很低下的。因此才有了逆邻接表的诞生。
• 节点a 的邻接点是节点b 、d ，其邻接点的存储下标为1、3，按照头插法（逆序）将其放入节点a 后面的单链表中；
图结构的元素之间虽然具有“多对多”的关系，但是同样可以采用顺序存储，即使用数组有效地存储图。
设G=(V,E)是n个顶点的图，则G的邻接矩阵用n阶方阵G表示，若(Vi ,Vj )或< Vi ,Vj >属于E(G)，则G[i][j]为1，否则为0。
该文讲述了如何利用邻接表存储图，并使用广度优先搜索算法对图进行遍历。文章首先介绍了邻接表存储图的基本概念，然后定义了广度优先搜索算法的实现。最后，通过一个具体的例子展示了如何使用邻接表存储图和广度优先搜索算法进行图的遍历。
版权声明：本文为博主原创文章，遵循 CC 4.0 BY 版权协议，转载请附上原文出处链接和本声明。
1、用两个数组分别存储数据元素（顶点）的信息和数据元素之间的关系（边或弧）的信息。
对于图中每个顶点 vi，把所有邻接于 vi的顶点（对有向图是将从vi出发的弧的弧头顶点链接在一起）链接成一个带头结点的单链表，将所有头结点顺序存储在一个一维数组中。 例：下面左图G2对应的邻接表如右边所示。
邻接矩阵是不错的存储结构，但是我们发现，对于边数相对于顶点较少的图，这种结构是存在对存储空间的极大浪费的
邻接表的出现是因为图若是稀疏图，用邻接矩阵会造成空间的浪费，毕竟你要开辟一个一维数组和一个二维数组嘛，而且还是大开小用的那种。
由于后续更新「面试专场」的好几篇文章都涉及到 图 这种数据结构，因此打算先普及一下 图 的相关理论支持，如果后面的相关内容有些点不太容易理解，可以查阅此篇文章。本文不建议一口气阅读完毕，可以先浏览一遍，在后续有需要的时候进行查阅即可。
定义：图（Graph）是由顶点的有穷非空集合和顶点之间边的集合组成，通常表示为：G(V,E)，其中，G表示一个图，V是图G中顶点的集合，E是图G中边的集合。
PS：邻接表，存储方法跟树的孩子链表示法相类似，是一种顺序分配和链式分配相结合的存储结构。如这个表头结点所对应的顶点存在相邻顶点，则把相邻顶点依次存放于表头结点所指向的单向链表中。图的邻接表储存方式相对于邻接矩阵比较节约空间，对于邻接矩阵需要分别把顶点和边（顶点之间的关系）用一维数组和二维数组储存起来。而邻接表则是把顶点按照顺序储存到一维数组中，然后再通过链式方式，把有关系的顶点下标链接到后方，咱们先不考虑权重问题，结构体定义简单一点，当然加上权值也不难。下方看图解释。 邻接表 有向图 无向图 逆邻接表 有
举个栗子，大家一定都用过微信，假设你的微信朋友圈中有若干好友：张三、李四、王五、赵六、七大姑、八大姨。
该文介绍了如何通过邻接表存储图的信息，包括顶点信息和边信息。在邻接表中，每个顶点vi对应一个单链表，该链表存储与vi相邻的顶点vj的信息。在图的创建过程中，首先读取顶点信息和边信息，然后根据这些信息创建邻接表。在图的遍历过程中，可以根据邻接表中的指针，逐个访问顶点并对其进行操作。
废江博客 , 版权所有丨如未注明 , 均为原创丨本网站采用BY-NC-SA协议进行授权 转载请注明原文链接：图（总目录）
连通图:在无向图G中，若对任何两个顶点 v、u 都存在从v 到 u 的路径，则称G是连通图。
与"好友"关系不同的是，"粉丝、关注"是一种单向关系，我虽然关注了你，但你不需要同时关注我这个粉丝。
邻接表和邻接矩阵是图的两种常用存储表示方式，用于记录图中任意两个顶点之间的连通关系，包括权值。
前面几篇已经介绍了线性表和树两类数据结构，线性表中的元素是“一对一”的关系，树中的元素是“一对多”的关系，本章所述的图结构中的元素则是“多对多”的关系。图（Graph）是一种复杂的非线性结构，在图结构中，每个元素都可以有零个或多个前驱，也可以有零个或多个后继，也就是说，元素之间的关系是任意的。现实生活中的很多事物都可以抽象为图，例如世界各地接入Internet的计算机通过网线连接在一起，各个城市和城市之间的铁轨等等。
图是非线性数据结构，是一种较线性结构和树结构更为复杂的数据结构，在图结构中数据元素之间的关系可以是任意的，图中任意两个数据元素之间都可能相关。
很久没写过文章了，今天就分享一下大数据中的图数据库Janusgraph的存储模型。希望对想做大数据图存储的粉丝有一定的帮助吧。由于没时间画图，所以图片来源于网络和Janusgraph官网，感谢各位作者的贡献。
图是计算机科学中一种重要的数据结构，用于表示各种关系和网络。在算法高级篇课程中，我们将深入探讨如何有效地表示和存储图，以及如何优化这些表示方法。本文将详细介绍图的基本概念、不同的表示方法，以及如何在 Python 中实现它们。
在数据结构中，树和图可以说是不可或缺的两种数据结构。其中，对于图来说，最重要的算法可以说就是遍历算法。而搜索算法中，最标志性的就是深度优先算法和广度优先算法。
图的基本概念中我们需要掌握的有这么几个概念：无向图、有向图、带权图；顶点（vertex）；边（edge）；度（degree）、出度、入度。下面我们就从无向图开始讲解这几个概念。
设图 A = (V, E) 有 n 个顶点，则图的邻接矩阵是一个二维数组 A.Edgen，定义为：
PS：这篇文章是之前 为什么我没写过「图」相关的算法？的修订版，主要是因为旧文中缺少 visited 数组和 onPath 数组的讨论，这里补上，同时将一些表述改得更准确，文末附带图论进阶算法。
无向图中，顶点对(x, y)是无序的，顶点对(x,y)称为顶点x和顶点y相关联的一条边，这条边没有特定方向，(x, y)和(y，x)是同一条边，比如下图G1和G2为无向图
无论是有向图还是无向图，主要的存储方式都有两种：邻接矩阵和邻接表。前者图的数据顺序存储结构，后者属于图的链接存储结构。
数据结构想必大家都不会陌生，对于一个成熟的程序员而言，熟悉和掌握数据结构和算法也是基本功之一。数据结构本身其实不过是数据按照特点关系进行存储或者组织的集合，特殊的结构在不同的应用场景中往往会带来不一样的处理效率。
与广度优先搜索不同，深度优先搜索（DFS）类似于树的先序遍历。正如其名称中所暗含的意思一样，这种搜索所遵循的搜索策略是尽可能“深”地搜索一个图。它的基本思想如下：首先访问图中某一起始顶点v，然后由v出发，访问与v邻接且未访问的任一顶点W1，再访问与w1邻接且未被访问任一W2，……重复上述过程。当不能再继续向下访问时，依次退回到最近被访问的顶点，若它还有邻接顶点未被访问过，则从该点开始上述搜索过程，直到图中所有顶点均被访问过止。
邻接表的问题：计算有向图的入度非常麻烦（入度：指向自己的数量，出度：指向别人的数量）
V0与V1、V2、V3都有边，因此第0行的1、2、3位置处置1。 Vi与Vj有边，则第i行的第j位置处置1。
No.15期 图在计算机中的存储 Mr. 王：还有一个很重要的问题，就是图在计算机中的表示。虽然我们看到的图边和点等都是非常直观的，可以画成一个圆圈里带一个数字表示顶点，用一条带有数字的线段或者箭头来表示边，但是在计算机中，显然不能用这种方式来存储它。 小可开玩笑地说：要是把图存成图片，那可太占空间了，而且还不容易读取上面的数字。 Mr. 王：是啊，图已经是对现实世界的一个抽象了，在计算机中我们要对其进行进一步的抽象。你想一想，图由哪两部分组成？ 小可：边的集合和顶点的集合。 Mr. 王：在手绘的图中，
在邻接表中，容易求得顶点和边的各种信息，但在邻接表中求两个顶点之间是否存在边，或需要对边执行删除等操作时，需要分别在两个顶点的边表中遍历，效率较低。
图的遍历和树的遍历类似，我们希望从图中某一顶点出发访遍图中其余顶点，且使每一个顶点仅被访问一次，这一过程就叫做图的遍历（Traverse Graph)。 图的遍历方法一般有两种，第一种是深度优先遍历（Depth First Search),也有称为深度优先搜索，简称为DFS。第二种是《广度优先遍历（Breadth First Search)》，也有称为广度优先搜索，简称为BFS。我们在《堆栈与深度优先搜索》中已经较为详细地讲述了深度优先搜索的策略，这里不再赘述。我们也可以把图当作一个迷宫，设定一个起始点
废话不多说，上来撸干货。 我们知道，实现图共有两种常用的方法：邻接矩阵、邻接表法。接下来我们就来一一介绍这两种方法。 实际上，图的存储结构有些复杂，为了方便读者理解，也为了方便笔者的写作，这部分的篇幅会长一些，稍有些啰嗦，还望见谅。
图Graph是由顶点（图中的节点被称为图的顶点）的非空有限集合V与边的集合E（顶点之间的关系）构成的。 若图G中的每一条边都没有方向，则称G为无向图。 若图G中的每一条边都有方向，则称G为有向图。
经常有读者问我「图」这种数据结构，因为我们公众号什么数据结构和算法都写过了，唯独没有专门介绍「图」。
图 数据结构 中 , 每个 结点 是一个 元素 , 可以有 0 个或 多个 相邻元素 , 两个结点 之间的 连接 称为 边 ;
大家好，我是架构君，一个会写代码吟诗的架构师。今天说一说【C#数据结构系列】图[通俗易懂],希望能够帮助大家进步!!!
图是计算机科学中的一种重要数据结构，它是由节点和边组成的集合，用于表示物体之间的关系。本篇博客将重点介绍图的基本概念和表示方法，包括有向图、无向图、带权图的概念，以及邻接矩阵和邻接表两种常用的图表示方法，并通过实例代码演示图的创建和基本操作，每行代码都配有详细的注释。
图的概念介绍得差不多了，大家可以消化消化再继续学习后面的内容。如果没有什么问题的话，我们就继续学习接下来的内容。当然，这还不是最麻烦的地方，因为今天我们只是介绍图的存储结构而已。
含有n个顶点的无向完全图有多少条边？ n×(n-1)/2条边 含有n个顶点的有向完全图有多少条弧？ n×(n-1)条边
解题思路: (1）总思路：在图中任意选取一个顶点开始(题目要求编号为0开始)，访问该顶点，并把该顶点设置为已访问
领取专属 10元无门槛券
手把手带您无忧上云
云服务器
ICP备案
对象存储
即时通信 IM
实时音视频
