随着学习的深刻，咱们的常识也在一直的扩大丰盛。树结构有没有让大家蒙圈呢？置信我，学完图当前你就会感觉二叉树几乎是简略得没法说了。其实咱们说所的树，也是图的一种非凡模式。

图的概念

还记得咱们学习树的第一篇文章时看到的那张对于树的图片吗？

在过后，咱们就说过，图 c 不是一颗树，而是一个图。为什么呢？从树的定义咱们能够看出，树只能有一个根结点，平级之间不能有分割，能够有多个子结点。而图就不必恪守这些规定，图的特点就是结点之间都能够相互有分割。比方下图这样的都是图。

在下面所画的图中，图 b 是的箭头的，而 图 a 的连接线是没有箭头的，像这样有明确的方向的指向的图就叫做 有向图。而没有箭头的，也就是没有方向指向的图就叫作 无向图。

咱们先将眼光移到 图 a -1，其实它就是把 图 a 旋转了一下。大家能看进去了吗？如果疏忽掉结点 4 和 1 之间的连线，那么它就是一颗树。是不是和咱们下面对于树的图中的 图 c 的概念统一了。

对于图的比拟正式的官网定义是：

图（Graph）G 由两个汇合 V 和 E 组成，记为 G=(V, E)，其中 V 是顶点的有穷非空集合，E 是 V 中顶点的有穷汇合，这些顶点偶对称为边。

在 有向图 中，连贯两点的那个线段，从开始的结点到指向的那个结点能够记为 <x, y>。<x, y> 和 <y, x> 是两个不同的边，也能够叫作 弧。依据 图 a，咱们能够看到这个图中有 <1, 2>、<2, 1>、<1, 3>、<3, 1>、<1, 4>、<4, 1>、<3, 4>、<4, 3> 这几条边。而 图 b 中，因为它是有向图，所以它的边只有 <1, 2>、<1, 3>、<3, 4>、<4, 1> 这四条。

是不是感觉在看下面的图片的时候还比拟清晰，一看这个定义就一脸懵逼了？像这种定义，如果你是须要考试的同学，那就还是要背下来的。如果只是像我一起想以学习利用或者理解为主的话，就不必去死记硬背了。V 就是结点，E 就是这些这些结点之间的关系，两个顶点之间的关系，也就是图上的那些连贯结点的线段就是边。

OK，这三个最最根底的概念搞明确了，咱们就持续学习其它的和图无关的那一大车术语！

图的相干术语

首先，咱们用 n 来示意图中顶点的数目，用 e 来示意边的数目，记住这两个代号。

• （1）子图：假如有两个图 G=(V, E) 和 G^‘=(V^‘, E^‘) 如果 V^‘ 蕴含于 V 且 E^‘ 蕴含于 E，则称 G ^‘ 为 G 的子图

上图中左边的那些子图都是属于原图的子图，能够看出子图能够产生十分多的状态，有向图 也是雷同的概念，不过绝对于 无向图 来说，有向图可能生成的子图更少一些，因为它的边是有方向的。

• (2) 无向齐全图和有向齐全图：对于无向图，若具备 n(n-1)/2 条边，就是无向齐全图。对于有向图，若具备 n(n-1) 条孤，就称为有向齐全图。（参考齐全二叉树）

其实齐全图的概念就是图中所有相邻的结点都有边可能连结在一起。

对于 有向图 来说，虽说边是有方向的，当然咱们也能够定义一个来回的方向，比方 <1, 2> 和 <2, 1>，在有向图中咱们就要画上两个相同方向的箭头示意能够从 1 到 2 也能够从 2 到 1。而 无向图 中则是用一个边来代替这两个边的概念了，自身的那一条没有箭头方向的边就是双向的。

• (3) 稠密图和浓密图：有很少条边或孤（如 e <nlog₂n）的图称为稠密图，反之称为浓密图
• (4) 权和网：在理论利用中，每条边或孤能够标上具备某种意义的值，就像地图上的间隔一样，这些数值就称为权。带权的图就能够称为网

最上方的的图片上 图 a -2 和 图 b -1 的边上的数字代表的就是权重。这两张图就能够称为网图。权重的概念咱们前面在讲相干的算法时会学习到，从这两张图中，咱们其实就能够很显著的看出，如果要从 结点 1 走到 结点 4 的话，并不是间接走 <1, 4> 这条边，而是走 <1, 3>、<3, 4> 这条路线更快些。

• (5) 邻接点：两个有边的结点就是邻接点
• (6) 度、入度和出度：顶点 v 的度就是指和 v 相关联的边的数目。对于有向图来说，箭头指向其它结点的就是出度，指向本人的就是入度

还是持续来看 图 b。结点 1 有两个出度，一个入度。这个貌似不必解释太多了吧。

• (7) 门路和门路长度：从某一个顶点到另一个顶点所通过的所有顶点就是门路。如果是有向图，那么它的门路就是依照箭头的方向。门路长度就是一条门路上通过的边或孤的数量
• (8) 回路或环：第一个顶点和最初一个顶点雷同的门路称为回路或环
• (9) 连通、连通图和连通重量：如果某两个结点之间是有门路的，就称这两个结点是连通的。如果整个图中所有的结点都能够是相互连通的，则这个图就是连通图。连通重量就是无向图非连通图中的极大连通子图。

包含前面的三个概念也在这张图中一并给出了。在 无向图 中，连通重量就等于极大连通子图，在这个图中，咱们有两个连通重量。

• (10) 极大连通子图：连通子图所能含有的最大结点数，如果再减少一个结点那么这个子图就不是连通图了
• (11) 生成树：一个极小连通子图，它含有图中全副的顶点，但只有足以形成一颗树的 n-1 条边，这样的连通子图就是连通图的生成树

其实就是通过一条门路，可能让图中所有的结点串联起来。在连通重量的图中，咱们就依据两个连通重量生成了两个最小生成树。它们的 连通重量 1 的生成树的结点并不一定非要是这种构造，咱们能够让 结点 4 在 结点 2 下，这取决于咱们如何遍从来生成这颗最小生成树。

最下面咱们的 图 a 的最小生成树其实就能够是 图 a -1 去掉那条红色虚线。当然，也能够让 结点 4 也在 结点 1 上面，同样也是取决于咱们的程序要如何遍历图来生成什么样的树。

• (12) 生成森林：在非连通图中，每一个连通重量都能够生成一个连通生成树，这样就形成了整个非连通图的生成森林

是不是看完之后昏头昏脑了？没关系，这些术语咱们在前面的学习中将会常常用到，而且这还不是最全面的。大家能够依据参考书目和其它学习材料来对图的相干术语进行更加深刻的学习和了解。

总结

图的概念介绍得差不多了，大家能够消化消化再持续学习前面的内容。这只是个开始，不少同学会不会感觉这玩意比照 树 构造一下子又晋升了好多。不必怕，在学习完前面的常识后，即便你临时还没有搞明确 图 相干的内容，但你肯定对 树 构造的了解会更加深刻了。为什么呢？树 其实就是没有回路的图，它们的遍历无外乎都是通过深度或者广度来实现的，只是图更简单一点而已。这下是不是感觉将来还是有点心愿的啦？学习，往往是一个渐进的过程，以后的常识和过来的常识总会有所关联的，先不必想太多，一步一步的虚浮走上来吧！

参考资料：

《数据结构》第二版，严蔚敏

《数据结构》第二版，陈越

《数据结构高分笔记》2020 版，天勤考研

各自媒体平台均可搜寻【硬核项目经理】