【数据结构】图的定义及其概念(一)

待我称王封你为后i 2021-09-21 06:42 751阅读 0赞

## 图主要知识 ##

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzIxNzk0Mg_size_16_color_FFFFFF_t_70_pic_center]

## 图的一些概念 ##

### 什么是图 ###

图是由顶点集合V和边集E组成的集合，记作G=（V，E）。  
注意: G中的顶点是有限非空集合. 线性表可以为非空表, 树也可以是空树, 但图不可以是空图. 即图中不能一个顶点也没有.

### 有向图/无向图 ###

组成图G的E为有向边是, 此时图称为**有向图**.  
假如有两个顶点v1,v2, 此时可记作<v1,v2>, v1可以称作边的头, v2可以称作边的尾.

当两个点互相可达, 可以认为这两个点之间有一条无向边. 由无向边E组成的图G称为**无向图**.  
假如有两个顶点v1,v2, 此时可记作(v1,v2).  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzIxNzk0Mg_size_16_color_FFFFFF_t_70_pic_center 1]

### 简单图/多重图 ###

简单图:

*  不存在重复边(两点间只有一条边)
 *  不存在自身(顶点V)到自身的边

多重图和简单图是相对的. 即, 有重复边或者存在自身(顶点)到自身的边.平常遇到的几乎都是简单图.  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzIxNzk0Mg_size_16_color_FFFFFF_t_70_pic_center 2]

### 完全图 ###

对于任意一个无向图边的数量范围(|E|)是0~n(n-1)/2, 当无向图有n(n-1)/2条边是乘务完全图.  
简单来说就是任意两个点之间均有边.  
![在这里插入图片描述][20200421185109758.png_pic_center]

### 子图 ###

若  V ′ ⊆ V V' \\subseteq V V′⊆V且  E ′ ⊆ E E' \\subseteq E E′⊆E, 此时 G ′ ⊆ G G' \\subseteq G G′⊆G, 称 G ′ G' G′是G的子图. 即当顶点和边都是另一个图的子集时, 这个图可以称为另一个图的子集.  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzIxNzk0Mg_size_16_color_FFFFFF_t_70_pic_center 3]

### 连通/连通图 ###

在图像图中, 如果两个点之间存在路径, 就称这两个点是**连通的**;  
若图中任意两个点之间都存在路径, 那么可以将这个图称之为**连通图**, 否则称为**非连通图**

常见的连通图:

*  环
 *  链  
    ![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzIxNzk0Mg_size_16_color_FFFFFF_t_70_pic_center 4]

### 强连通图/强连通分分量 ###

在有向图中, 若从一个顶点到另一个顶点相互都有路径, 就称这两个点是连通的, 若图中任意两点都是连通的, 就称图是**连通图**.  
在有向图中的连通子图称之为**连通分量**, 而有向图中的连通子图称之为**强连通分量**.  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzIxNzk0Mg_size_16_color_FFFFFF_t_70_pic_center 5]  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzIxNzk0Mg_size_16_color_FFFFFF_t_70_pic_center 6]  
本文完.

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

> **想了解作者更多，请移步我的个人网站，欢迎交流、留言~**  
> **极客技术空间：[https://elltor.com/][https_elltor.com]**

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzIxNzk0Mg_size_16_color_FFFFFF_t_70_pic_center]: /images/20210920/d727e82e61a248779d1051459e4a9de7.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzIxNzk0Mg_size_16_color_FFFFFF_t_70_pic_center 1]: /images/20210920/41165f0113d6437096913cd0b3097180.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzIxNzk0Mg_size_16_color_FFFFFF_t_70_pic_center 2]: /images/20210920/3ed1c18d6ec440e4bba407d3a4172012.png
[20200421185109758.png_pic_center]: /images/20210920/76976d2c522844e2b7e747cda9741ac4.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzIxNzk0Mg_size_16_color_FFFFFF_t_70_pic_center 3]: /images/20210920/7e111552618e40dcb3d8ee1a0a3cbf0d.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzIxNzk0Mg_size_16_color_FFFFFF_t_70_pic_center 4]: /images/20210920/ed61616c85344d1d8c523e11bd45eebd.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzIxNzk0Mg_size_16_color_FFFFFF_t_70_pic_center 5]: /images/20210920/f230223dbce74f35a8fb9495c04f29e4.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzIxNzk0Mg_size_16_color_FFFFFF_t_70_pic_center 6]: /images/20210920/b56c4ec79f08451c8a0812afd1955ba6.png
[https_elltor.com]: https://elltor.com/