数据结构笔记——图的基本概念

深藏阁楼爱情的钟 2023-02-17 05:27 31阅读 0赞

**目录**

一、图的定义

二、图逻辑结构的应用

三、无向图、有向图

四、简单图、多重图

五、顶点的度、入度、出度

六、顶点-顶点的关系描述

七、连通图、强连通图

八、研究图的局部——子图

九、连通分量、强连通分量

十、生成树

十一、生成森林

十二、边的权、带权图/网

十三、带权图的应用举例

十四、几种特殊形态的图

十五、总结

## **一、图的定义** ##

图G由顶点集V和边集E组成，记G=（V,E），其中V（G）表示图G中顶点的有限非空集；E（G）表示图G中顶点之间的关系（边）集合。若V=\{V1,V2....Vn\}，则用|V|表示图G中顶点的个数，也称图G的阶，E=\{（u，v）| u∈V，v∈V\}，用|E|表示图G中边的条数。

**注：线性表可以是空表，树可以是空树，但图不可以是空，即V一定是非空集**

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQwMzEwMTQ4_size_16_color_FFFFFF_t_70][]

## **二、图逻辑结构的应用** ##

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQwMzEwMTQ4_size_16_color_FFFFFF_t_70 1][]![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQwMzEwMTQ4_size_16_color_FFFFFF_t_70 2][]

## **三、无向图、有向图** ##

若E是无向边（简称边）的有限集合时，则图G为无向图。边是顶点的无序对，记为（v,w）或（w,v），其中v、w是顶点。可以说顶点w和顶点v互为邻接点。边（v,w）依附于顶点w和v，或者说边（v,w）和顶点v、w相关联。

G1 = （V1,E1）

V1 = \{A,B,C,D,E\}

E2 = \{（A,B），（B,D），（B,E），（C,D），（C,E），（D,E）\}

![20200612190522593.png][]

若E是有向边（也称弧）的有限集合时，则图G为有向图。弧是顶点的有序对，记为<v,w>，其中v、w是顶点，v称为弧尾，w称为弧头，<v,w>称为从顶点v到顶点w的弧，也称v邻接到w，或w邻接自v。**<v,w>≠<w,v>**

G2 = （V2，E2）

V2 = （A,B,C,D,E）

E2 = \{<A，B>，<A，C>，<A，D>，<A，E>，<B，A>，<B，C>，<B，E>，<C，D>\}

![20200612190935377.png][]

## **四、简单图、多重图** ##

简单图——①不存在重复边；②不存在顶点到自身的边

多重图——图G中某两个节点之间的边数多以一条，又允许顶点通过同一条边和自己关联，则G为多重图。

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQwMzEwMTQ4_size_16_color_FFFFFF_t_70 3][]

## **五、顶点的度、入度、出度** ##

**无向图**

顶点v的度是指依附于该顶点的边的条数，记为TD（v）。在具有n个顶点、e条边的无向图中，![20200612191409859.png][]，即无向图的全部顶点的度的和等于边数的2倍。

![20200612191501551.png][]

**有向图**

入度是以顶点v为终点的有向边的数目，记为ID（v）；

出度是以顶点v为起点的有向边的数据，记为OD（v）。

顶点v的度等于其入度和出度之和，即TD（v） = ID（v） + OD（v）。

在具有n个顶点、e条边的有向图中，![20200612191738189.png][]

![20200612191829704.png][]

## **六、顶点-顶点的关系描述** ##

路径——顶点vp到顶点vq之间的一条路径是指顶点序列vp,vk.....vq

回路——第一个顶点和最后一个顶点相同的路径称为回路或环

简单路径——在路径序列中，顶点不重复出现的路径称为简单路径

简单回路——除第一个顶点和最后一个顶点外，其余顶点不重复出现的回路称为简单回路。

路径长度——路径上边的数目

点到点的距离——从顶点u出发到顶点v的最短路径若存在，则此路径的长度称为从u到v的距离。若从u到v根本不存在路径，则记为无穷。

无向图中，若从顶点v到顶点w有路径存在，则称v和w是连通的

有向图中，若从顶点v到顶点w和从顶点w到顶点v之间都有路径，则称这两个顶点是强连通的

![2020061219255879.png][]![20200612192602751.png][]

## **七、连通图、强连通图** ##

若图G中任意两个顶点都是连通的，则称图G为连通图，否则称为非连通图。

![20200612192934470.png][]

**常见考点：**

对于n个顶点的无向图G

①若G是连通图，则最少有n-1条边

②若G是非连通图，则最多可能有![20200612192816783.png][]条边。

若图中任何一对顶点都是强连通的，则称此图为强连通图。

![20200612193028762.png][]

**常见考点：**

对于n个顶点的有向图G

若G是强连通图，则最少有n条边（形成回路）

## **八、研究图的局部——子图** ##

设有两个图G=（V，E） =和G' =（V'，E'），若V'是V的子集，且E'是E的子集，则称G'是G的子图。

若有满足V（G'） = V（G）的子图G'，则称其为G的生成子图。

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQwMzEwMTQ4_size_16_color_FFFFFF_t_70 4][]

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQwMzEwMTQ4_size_16_color_FFFFFF_t_70 5][]

**注：并非任意挑几个点、几条边都能构成子图**

## **九、连通分量、强连通分量** ##

极大连通子图——子图必须连通，且包含尽可能多的顶点和边

无向图中的极大连通子图称为连通分量

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQwMzEwMTQ4_size_16_color_FFFFFF_t_70 6][]

极大强连通子图——子图必须强连通，同时保留尽可能多的边

有向图中的极大强连通子图称为有向图的强连通分量

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQwMzEwMTQ4_size_16_color_FFFFFF_t_70 7][]

## **十、生成树** ##

极小连通子图——边尽可能的少，但要保持连通

连通图的生成树是包含图中全部顶点的一个极小连通子图

若图中顶点树为n，则它的生成树含有n - 1条边。对生成树而言，若砍去它的一条边，则会变成非连通图，若加上一条边则会形成一个回路。

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQwMzEwMTQ4_size_16_color_FFFFFF_t_70 8][]

## **十一、生成森林** ##

在非连通图中，连通分量的生成树构成了非连通图的生成森林。

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQwMzEwMTQ4_size_16_color_FFFFFF_t_70 9][]

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQwMzEwMTQ4_size_16_color_FFFFFF_t_70 10][]

## **十二、边的权、带权图/网** ##

边的权——在一个图中，每条边都可以标上具有某种含义的数值，该数值称为该边的权值。

带权图/网——边上带有权值的图称为带权图，也称网。

带权路径长度——当图是带权图时，一条路径上所有边的权值之和，称为该路径的带权路径长度

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQwMzEwMTQ4_size_16_color_FFFFFF_t_70 11][]![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQwMzEwMTQ4_size_16_color_FFFFFF_t_70 12][]

## **十三、带权图的应用举例** ##

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQwMzEwMTQ4_size_16_color_FFFFFF_t_70 13][]

## **十四、几种特殊形态的图** ##

无向完全图——无向图中任意两个顶点之间都存在边

若无向图的顶点树|V| = n,则![20200612195049924.png][]

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQwMzEwMTQ4_size_16_color_FFFFFF_t_70 14][]

有向完全图——有向图中任意两个顶点之间都存在方向相反的两条弧

若有向图的顶点树|V| = n，则![20200612195136301.png][]

![20200612195154563.png][]

稀疏图——边数很少的图

稠密图——边数很多的图

树——不存在回路，且连通的无向图

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQwMzEwMTQ4_size_16_color_FFFFFF_t_70 15][]

有向图——一个顶点的入度为0，其余顶点的入度均为1的有向图

![20200612195348433.png][]

**常见考点**

n个顶点的树，必有n-1条边

n个顶点的图，若|E| > n - 1 ，则一定有回路

## **十五、总结** ##

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQwMzEwMTQ4_size_16_color_FFFFFF_t_70 16][]

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQwMzEwMTQ4_size_16_color_FFFFFF_t_70]: https://img-blog.csdnimg.cn/20200612185911150.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQwMzEwMTQ4,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQwMzEwMTQ4_size_16_color_FFFFFF_t_70 1]: https://img-blog.csdnimg.cn/2020061219010420.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQwMzEwMTQ4,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQwMzEwMTQ4_size_16_color_FFFFFF_t_70 2]: https://img-blog.csdnimg.cn/20200612190122469.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQwMzEwMTQ4,size_16,color_FFFFFF,t_70
[20200612190522593.png]: https://img-blog.csdnimg.cn/20200612190522593.png
[20200612190935377.png]: https://img-blog.csdnimg.cn/20200612190935377.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQwMzEwMTQ4_size_16_color_FFFFFF_t_70 3]: https://img-blog.csdnimg.cn/20200612191231735.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQwMzEwMTQ4,size_16,color_FFFFFF,t_70
[20200612191409859.png]: https://img-blog.csdnimg.cn/20200612191409859.png
[20200612191501551.png]: https://img-blog.csdnimg.cn/20200612191501551.png
[20200612191738189.png]: https://img-blog.csdnimg.cn/20200612191738189.png
[20200612191829704.png]: https://img-blog.csdnimg.cn/20200612191829704.png
[2020061219255879.png]: https://img-blog.csdnimg.cn/2020061219255879.png
[20200612192602751.png]: https://img-blog.csdnimg.cn/20200612192602751.png
[20200612192934470.png]: https://img-blog.csdnimg.cn/20200612192934470.png
[20200612192816783.png]: https://img-blog.csdnimg.cn/20200612192816783.png
[20200612193028762.png]: https://img-blog.csdnimg.cn/20200612193028762.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQwMzEwMTQ4_size_16_color_FFFFFF_t_70 4]: https://img-blog.csdnimg.cn/20200612193512216.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQwMzEwMTQ4,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQwMzEwMTQ4_size_16_color_FFFFFF_t_70 5]: https://img-blog.csdnimg.cn/20200612193607767.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQwMzEwMTQ4,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQwMzEwMTQ4_size_16_color_FFFFFF_t_70 6]: https://img-blog.csdnimg.cn/20200612193856785.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQwMzEwMTQ4,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQwMzEwMTQ4_size_16_color_FFFFFF_t_70 7]: https://img-blog.csdnimg.cn/20200612194055178.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQwMzEwMTQ4,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQwMzEwMTQ4_size_16_color_FFFFFF_t_70 8]: https://img-blog.csdnimg.cn/20200612194458752.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQwMzEwMTQ4,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQwMzEwMTQ4_size_16_color_FFFFFF_t_70 9]: https://img-blog.csdnimg.cn/20200612194601178.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQwMzEwMTQ4,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQwMzEwMTQ4_size_16_color_FFFFFF_t_70 10]: https://img-blog.csdnimg.cn/20200612194607623.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQwMzEwMTQ4,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQwMzEwMTQ4_size_16_color_FFFFFF_t_70 11]: https://img-blog.csdnimg.cn/20200612194833271.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQwMzEwMTQ4,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQwMzEwMTQ4_size_16_color_FFFFFF_t_70 12]: https://img-blog.csdnimg.cn/20200612194849106.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQwMzEwMTQ4,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQwMzEwMTQ4_size_16_color_FFFFFF_t_70 13]: https://img-blog.csdnimg.cn/20200612194924127.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQwMzEwMTQ4,size_16,color_FFFFFF,t_70
[20200612195049924.png]: https://img-blog.csdnimg.cn/20200612195049924.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQwMzEwMTQ4_size_16_color_FFFFFF_t_70 14]: https://img-blog.csdnimg.cn/20200612195059906.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQwMzEwMTQ4,size_16,color_FFFFFF,t_70
[20200612195136301.png]: https://img-blog.csdnimg.cn/20200612195136301.png
[20200612195154563.png]: https://img-blog.csdnimg.cn/20200612195154563.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQwMzEwMTQ4_size_16_color_FFFFFF_t_70 15]: https://img-blog.csdnimg.cn/20200612195343607.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQwMzEwMTQ4,size_16,color_FFFFFF,t_70
[20200612195348433.png]: https://img-blog.csdnimg.cn/20200612195348433.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQwMzEwMTQ4_size_16_color_FFFFFF_t_70 16]: https://img-blog.csdnimg.cn/20200612195541410.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQwMzEwMTQ4,size_16,color_FFFFFF,t_70