在有向图和无向图中，如果节点之间无权值或者权值相等，那么dfs和bfs时常出现在日常算法中。不仅如此，dfs，bfs不仅仅能够解决图论的问题，在其他问题的搜索上也是最基础(但是策略不同)的两种经典算法。
术语表： 多重图：将含有平行边的图称为多重图。 简单图：将没有平行边和自环的图称为简单图。 相邻：当两个顶点通过一条边相连时，称这两个顶点相邻，并称这条边依附于这两个顶点。 度数：一个顶点的度数即依附于它的边的总数。 简单路径：是一条没有重复顶点的路径。 简单环：是一条（除了起点和终点必须相同外）没有相同顶点的环。 路径或环的长度：其中所包含的边数。（有权无向图则为边的权重和） 连通图：从任一顶点能够达到另一个任意顶点。 无向图的API： public class Graph Graph(int V)
图是一种非线性数据结构， 由【顶点Vertex】 和 【边Edge】组成。我们可以将图G抽象地表示为一组顶点V 和一组边 E 地集合。
图Graph是由顶点（图中的节点被称为图的顶点）的非空有限集合V与边的集合E（顶点之间的关系）构成的。 若图G中的每一条边都没有方向，则称G为无向图。 若图G中的每一条边都有方向，则称G为有向图。
图的广度优先搜索（Breadth-First Search，简称BFS）是一种用于遍历和搜索图的算法。它从图中的一个顶点开始，逐层地遍历其相邻顶点，并保持一个队列来存储待访问的顶点。BFS算法的核心思想是先访问离起始顶点最近的顶点，在此基础上逐层向外扩展，直到遍历完所有的顶点。
PS：这篇文章是之前 为什么我没写过「图」相关的算法？的修订版，主要是因为旧文中缺少 visited 数组和 onPath 数组的讨论，这里补上，同时将一些表述改得更准确，文末附带图论进阶算法。
邻接矩阵是不错的存储结构，但是我们发现，对于边数相对于顶点较少的图，这种结构是存在对存储空间的极大浪费的
图是计算机科学中的一种重要数据结构，它是由节点和边组成的集合，用于表示物体之间的关系。本篇博客将重点介绍图的基本概念和表示方法，包括有向图、无向图、带权图的概念，以及邻接矩阵和邻接表两种常用的图表示方法，并通过实例代码演示图的创建和基本操作，每行代码都配有详细的注释。
图 数据结构 中 , 每个 结点 是一个 元素 , 可以有 0 个或 多个 相邻元素 , 两个结点 之间的 连接 称为 边 ;
与"好友"关系不同的是，"粉丝、关注"是一种单向关系，我虽然关注了你，但你不需要同时关注我这个粉丝。
实现图的深度优先搜索（Depth-First Search, DFS）和拓扑排序是图论中重要的算法。在Java中，我们可以使用邻接表或邻接矩阵表示图，并利用递归或栈来实现深度优先搜索算法。下面将详细介绍如何使用Java实现图的深度优先搜索和拓扑排序算法。
大家好，我是架构君，一个会写代码吟诗的架构师。今天说一说【C#数据结构系列】图[通俗易懂],希望能够帮助大家进步!!!
在我们生活中，每天使用的微信等社交软件，我们的好友关系网也能被形象成一种图结构，如图，图能表示各种丰富的关系结构
数据结构是计算机科学中的一个重要概念，它描述了数据之间的组织方式和关系，以及对这些数据的访问和操作。常见的数据结构有：数组、链表、栈、队列、哈希表、树、堆和图。
前面几篇已经介绍了线性表和树两类数据结构，线性表中的元素是“一对一”的关系，树中的元素是“一对多”的关系，本章所述的图结构中的元素则是“多对多”的关系。图（Graph）是一种复杂的非线性结构，在图结构中，每个元素都可以有零个或多个前驱，也可以有零个或多个后继，也就是说，元素之间的关系是任意的。现实生活中的很多事物都可以抽象为图，例如世界各地接入Internet的计算机通过网线连接在一起，各个城市和城市之间的铁轨等等。
其实在上一篇介绍树结构的时候，已经有了一些算法的相关内容介入。而在图这种数据结构下，会有更多有关图的算法，比如广度优先搜索，深度优先搜索最短路径算法等等。这是我们要介绍的最后一个数据结构。同时也是本系列最为复杂的一个。那么我们先来简单介绍一下，什么是图？ 一、图的概念 简单说，图就是网络结构的抽象模型，图是一组由边连接的节点（或顶点）。任何二元关系都可以用图来表示。比如我们的地图，地铁线路图等。都是图的实际应用。 接着我们看看图的一些相关概念和术语。 一个图G = (V,E)由以下元素组成：
无论是有向图还是无向图，主要的存储方式都有两种：邻接矩阵和邻接表。前者图的数据顺序存储结构，后者属于图的链接存储结构。
当一个图为稀疏图时，使用邻接矩阵表示法显然要浪费大量的存储空间。而图的邻接表示法结合了顺序存储和链式存储方法，大大减少了这种不必要的浪费。
邻接表的问题：计算有向图的入度非常麻烦（入度：指向自己的数量，出度：指向别人的数量）
图的遍历与树的遍历基本类似，但要注意两个不同： 1. 图中可能有环路，因此可能会导致死循环； 2. 一个图可能由多个独立的子图构成，因此一条路径走到头后要重新选择尚未遍历的起点。 图的邻接表数据结构请参见：图的邻接表示法Java版 宽度优先遍历 思路 选择一个尚未访问的起点，依次访问它的相邻结点； 若相邻结点还有相邻结点的话，再依次访问尚未访问的相邻结点；直到以该结点为起点的这条路径上所有的结点都已访问； 再选择一个尚未访问的结点作为起点，重复上述操作，直到所有结点都已访问为止； 代码实现 /*
设G=(V,E)是n个顶点的图，则G的邻接矩阵用n阶方阵G表示，若(Vi ,Vj )或< Vi ,Vj >属于E(G)，则G[i][j]为1，否则为0。
其实在上一篇介绍树结构的时候，已经有了一些算法的相关内容介入。而在图这种数据结构下，会有更多有关图的算法，比如广度优先搜索，深度优先搜索最短路径算法等等。这是我们要介绍的最后一个数据结构。同时也是本系列最为复杂的一个。那么我们先来简单介绍一下，什么是图？
该文讲述了如何利用邻接表存储图，并使用广度优先搜索算法对图进行遍历。文章首先介绍了邻接表存储图的基本概念，然后定义了广度优先搜索算法的实现。最后，通过一个具体的例子展示了如何使用邻接表存储图和广度优先搜索算法进行图的遍历。
经常有读者问我「图」这种数据结构，因为我们公众号什么数据结构和算法都写过了，唯独没有专门介绍「图」。
在前面，我写过一篇Java的深浅拷贝，那是基于对象的拷贝，但放眼数据结构与算法中，你有考虑过怎么拷贝一个图吗？(无向图)
对于图中每个顶点 vi，把所有邻接于 vi的顶点（对有向图是将从vi出发的弧的弧头顶点链接在一起）链接成一个带头结点的单链表，将所有头结点顺序存储在一个一维数组中。 例：下面左图G2对应的邻接表如右边所示。
图是一种非线性数据结构，它由节点（也称为顶点）和连接这些节点的边组成。图可以用来表示各种关系和连接，比如网络拓扑、社交网络、地图等等。图的节点可以包含任意类型的数据，而边则表示节点之间的关系。图有两种常见的表示方法：邻接矩阵和邻接表。
版权声明：本文为博主原创文章，遵循 CC 4.0 BY 版权协议，转载请附上原文出处链接和本声明。
图是非线性数据结构，是一种较线性结构和树结构更为复杂的数据结构，在图结构中数据元素之间的关系可以是任意的，图中任意两个数据元素之间都可能相关。
邻接表作为图的一种存储方式，在存储稀疏图上相对于邻接矩阵有相当大的空间节省。如一个稀疏图的顶点个个数为n，边数为e。用邻接矩阵存储需要n^2空间，而真正进行存储的只有2e个空间， 剩下的n^2-2e都浪费了。但是对于邻接表来讲，存储空间只需要n+2e个，相对于邻接矩阵减少了很多。邻接表虽然在空间上有很大的优势，但是对于一个有向图，如果需要查找每个顶点的入度就需要遍历整个邻接表，在效率上很低下的。因此才有了逆邻接表的诞生。
图结构的元素之间虽然具有“多对多”的关系，但是同样可以采用顺序存储，即使用数组有效地存储图。
深度优先遍历是一种优先走到底、无路可走再回头的遍历方式。具体地，从某个顶点出发，访问当前顶点的某个邻接顶点，直到走到尽头时返回，再继续走到尽头并返回，以此类推，直至所有顶点遍历完成。
废江博客 , 版权所有丨如未注明 , 均为原创丨本网站采用BY-NC-SA协议进行授权 转载请注明原文链接：图的遍历及应用
你问一个人听过哪些算法，那么深度优先搜索(dfs)和宽度优先搜索(bfs)那肯定在其中，很多小老弟学会dfs和bfs就觉得好像懂算法了，无所不能，确实如此，学会dfs和bfs暴力搜索枚举确实利用计算机超强计算大部分都能求的一份解，学会dfs和bfs去暴力杯混分是一个非常不错的选择！
邻接表的出现是因为图若是稀疏图，用邻接矩阵会造成空间的浪费，毕竟你要开辟一个一维数组和一个二维数组嘛，而且还是大开小用的那种。
举个栗子，大家一定都用过微信，假设你的微信朋友圈中有若干好友：张三、李四、王五、赵六、七大姑、八大姨。
由于后续更新「面试专场」的好几篇文章都涉及到 图 这种数据结构，因此打算先普及一下 图 的相关理论支持，如果后面的相关内容有些点不太容易理解，可以查阅此篇文章。本文不建议一口气阅读完毕，可以先浏览一遍，在后续有需要的时候进行查阅即可。
无向图中，顶点对(x, y)是无序的，顶点对(x,y)称为顶点x和顶点y相关联的一条边，这条边没有特定方向，(x, y)和(y，x)是同一条边，比如下图G1和G2为无向图
连通图:在无向图G中，若对任何两个顶点 v、u 都存在从v 到 u 的路径，则称G是连通图。
V0与V1、V2、V3都有边，因此第0行的1、2、3位置处置1。 Vi与Vj有边，则第i行的第j位置处置1。
1、用两个数组分别存储数据元素（顶点）的信息和数据元素之间的关系（边或弧）的信息。
• 节点a 的邻接点是节点b 、d ，其邻接点的存储下标为1、3，按照头插法（逆序）将其放入节点a 后面的单链表中；
定义：图（Graph）是由顶点的有穷非空集合和顶点之间边的集合组成，通常表示为：G(V,E)，其中，G表示一个图，V是图G中顶点的集合，E是图G中边的集合。
废江博客 , 版权所有丨如未注明 , 均为原创丨本网站采用BY-NC-SA协议进行授权 转载请注明原文链接：图（总目录）
图是计算机科学中一种重要的数据结构，用于表示各种关系和网络。在算法高级篇课程中，我们将深入探讨如何有效地表示和存储图，以及如何优化这些表示方法。本文将详细介绍图的基本概念、不同的表示方法，以及如何在 Python 中实现它们。
上回说到，LIL 通过把稀疏矩阵看成是有序稀疏向量组，通过对稀疏向量组中的稀疏向量进行压缩存储来达到压缩存储稀疏矩阵的目的。这一回从图数据结构开始！
PS：邻接表，存储方法跟树的孩子链表示法相类似，是一种顺序分配和链式分配相结合的存储结构。如这个表头结点所对应的顶点存在相邻顶点，则把相邻顶点依次存放于表头结点所指向的单向链表中。图的邻接表储存方式相对于邻接矩阵比较节约空间，对于邻接矩阵需要分别把顶点和边（顶点之间的关系）用一维数组和二维数组储存起来。而邻接表则是把顶点按照顺序储存到一维数组中，然后再通过链式方式，把有关系的顶点下标链接到后方，咱们先不考虑权重问题，结构体定义简单一点，当然加上权值也不难。下方看图解释。 邻接表 有向图 无向图 逆邻接表 有
领取专属 10元无门槛券
手把手带您无忧上云
云服务器
ICP备案
对象存储
即时通信 IM
实时音视频
