随着学习的深入，我们的知识面也在不断地扩展和丰富。树结构是不是把大家搞糊涂了？相信我，学完图之后，你会觉得二叉树简直太简单了。其实我们说的树也是图的一种特殊形式。图的概念还记得我们在学习树的第一篇文章中看到的关于树的图片吗？当时我们说图c不是树，而是图。为什么？从树的定义可以看出，树只能有一个根节点，层级之间不能有任何联系，可以有多个子节点。图不需要遵守这些规则。图的特点是节点可以相互关联。比如下图就是一张图片。上图中b图有箭头，a图的连线没有箭头。像这样有明确方向的图片称为有向图片。没有箭头的图，即没有方向的图，称为无向图。我们先把目光移到图a-1上，其实它只是旋转了图a。每个人都能看到吗？如果忽略节点4和1之间的连接，则它是一棵树。是不是和我们上面树图中的图c的概念一致。图官方比较正式的定义是：图（Graph）G由两个集合V和E组成，记为G=(V,E)，其中V是顶点的有限非空集，E是一个V中的顶点一组有限的顶点对称为边。在有向图中，连接两点的线段，从起始节点到指向节点，可以表示为。和是两条不同的边，也称为弧。根据图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边，而是走<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)Generativeforest：在一个断开图中，每个连通的分量都可以生成一个连通的生成树，这样构成整个断开图的生成森林是不是看完就晕了？没关系，我们在后面的学习中会经常用到这些术语，这还不是最全面的。您可以借助参考书目等学习资料，更深入地学习和理解与图相关的术语。总结图的概念介绍的差不多了，大家可以消化一下，继续学习后面的内容。这仅仅是个开始。很多同学会觉得这个东西比起树形结构提升了很多。别怕，学完下面的知识，即使你还没有搞清楚图相关的内容，想必你对树结构也有了更深的理解。为什么？树其实就是没有环路的图，它们的遍历是通过深度或者广度来实现的，只是图比较复杂。你现在对未来充满希望吗？学习往往是一个循序渐进的过程。当前的知识和过去的知识总是相关的。别想太多，一步一步来吧！参考资料：《数据结构》第2版，闫伟民《数据结构》第2版，陈越《数据结构高分笔记》2020版，天琴考研各媒体平台均可搜索【硬核项目经理】
