图与图的基本术语

深碍√TFBOYSˉ_ 2023-02-11 10:27 16阅读 0赞

## 一、图的定义 ##

**图G**由两个集合V和E组成，记为G=(V,E),其中V是**顶点**的**有穷非空集合**，E是V中**顶点偶对**的**有穷集合**。  
通俗理解：V是顶点的集合（不能为空），E是边的集合（可以为空）。  
**有向图**：若边集E为有向边，则图为有向图，<x,y> x为有向边的始点（也称为弧尾），y 为有向边的终点（也称为弧头）；  
**无向图**：若边集E为无向边，则图为无向图，（x,y) 与（y,x)是同一条边；

## 二、图的基本术语 ##

**1、子图**：  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2dldHNfcw_size_16_color_FFFFFF_t_70]  
**2、无向完全图**：对于无向图，若有n(n-1)/2条边，则称为无向完全图；  
**有向完全图**：对于有向图，若有n(n-1)条弧，则称为有向完全图；  
**3、权和网**：每条边上可以标上具有某种含义的数值，该数值称为该边上的权，带权的图称为网。  
**4、邻接点**：对于无向图，如果图的边（v,v’)属于E，则称v与v’互为邻接点。  
**5、度、入度和出度**：顶点的度指的是与顶点相关联的边的数目。对于有向图，指向该顶点的有向边的数目为入度，从该顶点指出的有向边的数目称为该顶点的出度。  
**6、路径长度**：一条路径上经过的边或弧的长度；  
**7、回路或环**：第一个顶点和最后一个顶点相同的路径长度称为回路或环;  
**8、简单路径、简单回路或简单环**：序列中顶点不重复出现的路径称为简单路径；除第一个顶点和最后一个顶点外，其余顶点不重复出现的回路，称为简单回路或简单环；

## 三、图的存储结构 ##

**1、邻接矩阵**

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2dldHNfcw_size_16_color_FFFFFF_t_70 1]  
**2、邻接表**  
![在这里插入图片描述][20200614211949327.png]  
邻接表的优缺点：  
（优点）  
1、便于增加和删除顶点；  
2、便于统计边的数目，按顶点表顺序扫描所有边表可得到边的数目，时间复杂度为O(n+e);  
3、空间效率高；  
（缺点）  
1、不便于判断顶点之间是否有边  
2、不便于计算有向图各个顶点的度  
**3、十字链表**  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2dldHNfcw_size_16_color_FFFFFF_t_70 2]  
**4、邻接多重表**  
邻接多重表是无向图的另一种链式存储结构

## 四、图的遍历 ##

**1、深度优先搜索**  
（1）从图中某个顶点v出发，开始访问；  
（2）找出刚访问过的顶点的第一个未被访问的邻接点，访问该顶点。以该顶点为新顶点，重复次步骤，直到刚访问过的顶点没有未被访问过的邻接点为止；  
（3）返回前一个访问过的且仍旧有未被访问过的邻接点的顶点，找出该顶点的下一个未被访问过的邻接点，访问该节点；  
（4）重复步骤（2）和（3），直到图中所有顶点都被访问过，搜索结果。  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2dldHNfcw_size_16_color_FFFFFF_t_70 3]  
**2、广度优先搜索**  
（1)从图中某个顶点出发，开始访问；  
（2）依次访问v的各个未曾访问过的邻接点；  
（3）分别从这些邻接点出发依次访问它们的邻接点，并使“先被访问的顶点的邻接点”先于“后被访问的顶点的邻接点”被访问。  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2dldHNfcw_size_16_color_FFFFFF_t_70 4]

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2dldHNfcw_size_16_color_FFFFFF_t_70]: https://img-blog.csdnimg.cn/20200524154354426.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2dldHNfcw==,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2dldHNfcw_size_16_color_FFFFFF_t_70 1]: https://img-blog.csdnimg.cn/20200614210617587.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2dldHNfcw==,size_16,color_FFFFFF,t_70
[20200614211949327.png]: https://img-blog.csdnimg.cn/20200614211949327.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2dldHNfcw_size_16_color_FFFFFF_t_70 2]: https://img-blog.csdnimg.cn/2020061421484042.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2dldHNfcw==,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2dldHNfcw_size_16_color_FFFFFF_t_70 3]: https://img-blog.csdnimg.cn/20200614220515593.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2dldHNfcw==,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2dldHNfcw_size_16_color_FFFFFF_t_70 4]: https://img-blog.csdnimg.cn/20200614221500555.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2dldHNfcw==,size_16,color_FFFFFF,t_70