数据结构-图概念--快来看看嘛

灰太狼 2023-03-13 06:09 18阅读 0赞

https://blog.csdn.net/qq\_35644234/article/details/57083107

## 简介： ##

图的应用是很广的，在离散数学中就有了图的基本概念和数学逻辑上的介绍，图在计算机科学中也是无处不在的，例如网络，图，神经网络深度学习以及最近很火的知识图谱等都离不开图的数据结构。可以去看看**neo4j**这个图数据库，可视化效果老好看了！！！

## 定义： ##

无论多么复杂的图都是由**顶点**和**边**构成的。  
  采用形式化的定义，图G（Graph）由两个集合V（Vertex）和 E（Edge）组成，记为G=(V,E)，其中V是顶点的有限集合，记为V(G)，E是连接V中两个不同顶点（顶点对）的边的有限集合，记为E(G)。 图的基本概念  
**看个例子：**  
  一个图G1=(V1，E1)，其中：V1=\{0，1，2，3，4\} E1=\{(0,1)，(1,2)，(2,3)，(3,4)，(2,4)，(0,3)\}另一个图G2=(V2，E2)，其中：V2=\{0，1，2，3，4\} E2=\{<0,1>，<1,2>，<1,3>，<2,4>，<0,4>，<4,3>，< 3,2>\} 画出这两个图的逻辑结构。  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzY3MzE1Ng_size_16_color_FFFFFF_t_70]  
可以看到有向图和无向图，<>表示的是序偶；

## 图的术语： ##

**（1）有向图和无向图**  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzY3MzE1Ng_size_16_color_FFFFFF_t_70 1]  
**（2）端点和相邻点**  
**（3）度、入度和出度**  
 顶点v的度记为D(v)。对于无向图，每个顶点的度定义为以该  
顶点为一个端点的边数。  
对于有向图，顶点v的度分为入度和出度，入度是以该顶点为  
终点的入边数目；出度是以该顶点为起点的出边数目，该顶点的  
度等于其入度和出度之和。  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzY3MzE1Ng_size_16_color_FFFFFF_t_70 2]

**（4）子图**  
 设有两个图G=(V,E)和G’=(V’,E’)，若V’是V的子集，即V’ 属于V，且E’为E的子集，即E’ 属于E，则称G’是G的子图。  
**（5）完全无向图**  
 对于无向图，若具有n(n-1)/2条边，则称之为完全无向图。  
例如，图7.2(a)是完全无向图G3，这里n=4，边数为6。  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzY3MzE1Ng_size_16_color_FFFFFF_t_70 3]

**（6）完全无向图和完全有向图**  
 对于有向图，若具有n(n-1)条边，则称之为完全有向图。  
例如，图7.2(b)是完全有向图G4，这里n=4，边数为12。  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzY3MzE1Ng_size_16_color_FFFFFF_t_70 4]  
**（7）稀疏图和稠密图**  
 边数较少（边数e<<nlog2n，其中n为顶点数）的图称为稀疏  
图。边总较多的图称为稠密图。  
**（8）路径和路径长度**  
 在一个图G中，从顶点i到顶点j的一条路径是一个顶点序列i=i0、i1、…、im=j，若是无向图，则(ik-1,ik)∈E(G)， （1≤k≤m），若该图是有向图，则<ik-1,ik>∈E(G)， （1≤k≤m），其中顶点i称为该路径的开始点，顶点j称为该路径的结束点。路径长度是指一条路径上经过的边的数目。

**（9）连通、连通图和连通分量**  
 在无向图G中，若从顶点i到顶点j有路径，则称顶点i和j是连通的。若图G中任意两个顶点都是连通的，则称G为连通图，否则为非连通图。无向图G中极大连通子图称为G的连通分量。  
 例如，图7.1(a)的连通分量就是自身，因为该图是连通图。  
**（10）强连通图和强连通分量**  
 在有向图G中，若任意两个顶点i和j都是连通的，即从顶点i 到j和从顶点j到i都存在路径，则称该图是强连通图(任意两点都是可达的)。  
有向图G中极大强连通子图称为G的强连通分量。

**（11）权和网**  
 在一个图中，每条边可以标上具有某种含义的数值，该数值称为该边的权。边上带权的图称为带权图，也称为网。 图7.4中的图G5就是一个带权图。本书中规定所有边的权均为非负数。  
**神经网络！！！**  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzY3MzE1Ng_size_16_color_FFFFFF_t_70 5]

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzY3MzE1Ng_size_16_color_FFFFFF_t_70]: /images/20230312/2046959e53db4b86b6dca74ebdd4a879.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzY3MzE1Ng_size_16_color_FFFFFF_t_70 1]: /images/20230312/521d498126dd4d4f8190b4751ff9805d.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzY3MzE1Ng_size_16_color_FFFFFF_t_70 2]: /images/20230312/36b30009b808436db13b0da8ec0ba114.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzY3MzE1Ng_size_16_color_FFFFFF_t_70 3]: /images/20230312/dd6410cce0764d35b4d2ee17d0377b76.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzY3MzE1Ng_size_16_color_FFFFFF_t_70 4]: /images/20230312/c95b3b9b39a34830ba0d56fa9d655bae.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzY3MzE1Ng_size_16_color_FFFFFF_t_70 5]: /images/20230312/c4a93b7a8b844a70a964bb5e7b2abc3b.png