数据结构之图笔记：图论基础术语以及基础知识略

悠悠 2023-01-19 04:37 78阅读 0赞

**基本概念：**  
**一、顶点（vertex）**  
上图中黑色的带数字的点就是顶点，表示某个事物或对象。由于图的术语没有标准化，因此，称顶点为点、节点、结点、端点等都是可以的。叫什么无所谓，理解是什么才是关键。

**二、边（edge）**  
上图中顶点之间蓝色的线条就是边，表示事物与事物之间的关系。需要注意的是边表示的是顶点之间的逻辑关系，粗细长短都无所谓的。包括上面的顶点也一样，表示逻辑事物或对象，画的时候大小形状都无所谓。

**三、路径/最短路径（path/shortest path）**  
在图上任取两顶点，分别作为起点（start vertex）和终点（end vertex），我们可以规划许多条由起点到终点的路线。不会来来回回绕圈子、不会重复经过同一个点和同一条边的路线，就是一条“路径”。两点之间存在路径，则称这2个顶点是连通的（connected）。  
还是上图的例子，北京->上海->广州，是一条路径，北京->武汉->广州，是另一条路径，北京—>武汉->上海->广州，也是一条路径。而北京->武汉->广州这条路径最短，称为最短路径。  
路径也有权重。路径经过的每一条边，沿路加权重，权重总和就是路径的权重（通常只加边的权重，而不考虑顶点的权重）。在路网中，路径的权重，可以想象成路径的总长度。在有向图中，路径还必须跟随边的方向。  
值得注意的是，一条路径包含了顶点和边，因此路径本身也构成了图结构，只不过是一种特殊的图结构。

**四、环（loop）**  
环，也成为环路，是一个与路径相似的概念。在路径的终点添加一条指向起点的边，就构成一条环路。通俗点说就是绕圈。

--------------------

**定义**

图：记为 G＝( V, E )  
其中：V 是G 的顶点集合，是有穷非空集；E 是G 的边集合，是有穷集。

问：当E(G)为空时，图G存在否？  
答：还存在！但此时图G只有顶点而没有边。

*  有向图：图G中的每条边都是有方向的；
 *  无向图：图G中的每条边都是无方向的；
 *  完全图：图G任意两个顶点都有一条边相连接；

注：如果不考虑顶点到自身的**弧或边**，n 个顶点的无向图有 n(n-1)/2 条边, 称为**无向完全图**，n 个顶点的有向图有n(n-1) 条边, 称为**有向完全图**。  
![在这里插入图片描述][20210507220708180.png_pic_center]

*  带权图：即边上带权的图。其中权是指**每条边可以标上具有某种含义的数值**（即与边相关的数）。带权图也叫做**网**
 *  连通图：在无向图中, 若从顶点v1到顶点v2有**路径**, 则称顶点v1与v2是连通的。如果图中任意一对顶点都是连通的, 则称此图是连通图。非连通图的极大连通子图叫做连通分量。（有路径就行，也就是说两个顶点间接连接也算作连通）
 *  强连通图：在**有向图**中, 若对于每一对顶点vi和vj, **都存在一条从vi到vj和从vj到vi的路径**, 则称此图是强连通图。  
    非强连通图的**极大强连通子图**叫做**强连通分量**。
 *  弱连通图**将有向图的所有的有向边替换为无向边**，所得到的图称为原图的基图。如果一个有向图的基图是连通图，则有向图是弱连通图。
 *  混合图：既有有向边，又有无向边的图。（这是我发现的一个奇怪的图）
 *  回路和环：起点和终点相同。
 *  连通：如果图中结点U、V之间存在一条从U通过若干 条边、点到达V的通路（也就是说可间接，我一直以为是直接链接），则称U、V是连通的
 *  完全图：**每对顶点之间有唯一的一条边相连或想通**。无向图共有：n\*(n-1)/2条边，有向图共有：n\*(n-1)条边
 *  稠密图：一个边数接近完全图的图（我觉得这只是一种概念，毕竟没有标准）
 *  稀疏图：一个边数远远少于完全图的图
 *  子图(subgraph): **边的子集和相关联的点集**
 *  强连通分量：**有向图中任意两点都连通的最大子图**。
 *  结点的度：无向图中与结点相连的边的数目，称为结点的度。有向图中为入度与出度的和。
 *  结点的入度：在有向图中，**以这个结点为终点的有向边的数目**。
 *  结点的出度：在有向图中，**以这个结点为起点的有向边的数目**。

> ![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2Nvb2w5OTc4MQ_size_16_color_FFFFFF_t_70_pic_center]  
> [https://blog.csdn.net/nyist\_yangguang/article/details/113468345][https_blog.csdn.net_nyist_yangguang_article_details_113468345]

**连通图**：仅需从任一顶点出发,进行深度优先搜索或广度优先搜索,便可访问到图中所有顶点。

**非连通图**：则需从多个顶点出发进行搜索,而每一次从 一个新的起始点出发进行搜索过程中得到的顶点访问序列恰为其各个连通分量中的顶点集。

**连通分量**：这些顶点集分别加上所有依附于这些顶点的边,便构成了该非连通图的**连通分量**。

**生成树**：是一个极小连通子图，它含有图中全部顶点，但只有n-1条边。

**生成森林**：由若干棵生成树组成，含全部顶点，但构成这些树的边是最少的。

（需要涉及到树的知识）

*  思考1：若对连通图进行遍历，得到的是什么？  
    ——得到的将是一个极小连通子图，即图的生成树！  
    由深度优先搜索得到的生成树，称为深度优先搜索生成树。  
    由广度优先搜索得到的生成树，称为广度优先搜索生成树。
 *  思考2：若对非连通图进行遍历，得到的是什么？  
    —— 得到的将是各连通分量的生成树，即图的生成森林！

**深度优先搜索生成树算法**  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2Nvb2w5OTc4MQ_size_16_color_FFFFFF_t_70_pic_center 1]

图->生成树（或生成森林）->邻接表

邻接表可以用存储每一个顶点之间的关系，可以表达出生成树（或生成森林）  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2Nvb2w5OTc4MQ_size_16_color_FFFFFF_t_70_pic_center 2]

**邻接表（邻接矩阵）**  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2Nvb2w5OTc4MQ_size_16_color_FFFFFF_t_70_pic_center 3]

我习惯用vector存储邻接表，当然类型是结构体了。这是后话了……

参考：  
[https://blog.csdn.net/saltriver/category\_6506969.html][https_blog.csdn.net_saltriver_category_6506969.html]  
[https://blog.csdn.net/qq\_22238021/article/details/78276420][https_blog.csdn.net_qq_22238021_article_details_78276420]  
[https://blog.csdn.net/saltriver/article/details/54428685][https_blog.csdn.net_saltriver_article_details_54428685]

[20210507220708180.png_pic_center]: /images/20221021/7acca60d7c5645d3a9c2ef74d7d6e008.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2Nvb2w5OTc4MQ_size_16_color_FFFFFF_t_70_pic_center]: /images/20221021/5712e020cb71496bb85c065eb6e8089a.png
[https_blog.csdn.net_nyist_yangguang_article_details_113468345]: https://blog.csdn.net/nyist_yangguang/article/details/113468345
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2Nvb2w5OTc4MQ_size_16_color_FFFFFF_t_70_pic_center 1]: /images/20221021/7c0341b370bc4e5fac1014d884d14a9f.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2Nvb2w5OTc4MQ_size_16_color_FFFFFF_t_70_pic_center 2]: /images/20221021/b3a0c4cfec0d4bb7a264e0d2381f5c96.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2Nvb2w5OTc4MQ_size_16_color_FFFFFF_t_70_pic_center 3]: /images/20221021/a8e55a086b784c7187063ede2ec41441.png
[https_blog.csdn.net_saltriver_category_6506969.html]: https://blog.csdn.net/saltriver/category_6506969.html
[https_blog.csdn.net_qq_22238021_article_details_78276420]: https://blog.csdn.net/qq_22238021/article/details/78276420
[https_blog.csdn.net_saltriver_article_details_54428685]: https://blog.csdn.net/saltriver/article/details/54428685