【数据结构】之图的定义

ゝ一纸荒年。 2023-02-22 05:28 22阅读 0赞

### 文章目录 ###

*   *  定义
     *  各种图定义
     *  图的顶点与边间关系
     *  连通图

## 定义 ##

**图（Graph）是由顶点的有穷非空集合和顶点之间边的集合组成，通常表示为：G（V,E），其中G表示一个图，V是图G中顶点的集合，E是图G中边的集合。**

注意点：

*  线性表中我们把数据元素叫做元素，树中将数据元素叫结点，**在图中数据元素称之为顶点（Vertxt）。**
 *  线性表中可以没有数据元素，称为空表。树中可以没有结点，叫做空树。那么对于图呢？**在图结构中，不允许没有顶点。在定义中，若V是顶点的集合，则强调了顶点集合V有穷非空。**
 *  线性表中，相邻的数据元素之间具有线性关系，树结构中，相邻两层的结点具有层次关系，**在图中，任意两个顶点之间都可能有关系，顶点之间的逻辑关系用边来表示。边集可以是空的。**

## 各种图定义 ##

**无向边：若顶点Vi到Vj之间的边没有方向，则称这条边为无向边（Edge），用无序偶对（VI,Vj）来表示。如果图中任意两个顶点之间的边都是无向边，则称该图为无向图（Undirected graphs）**。图1-1就是一个无向图，由于是没有方向的，连接顶点A与D的边，可以表示成无序对（A,D）也可以写成（D,A）。  
![在这里插入图片描述][20200702093732424.png_pic_center]

图1-1  
对于图1-1的无向图G来说，G=（V 1,\{E 1\}），其中顶点集合V 1=\{A,B,C,D\};边集合E 1=\{(A,B),(B,C),(C,D),(D,A)(A,C)\}

**有向边：若从顶点Vi到Vj的边有方向，则称条边为有向边，也称为弧（Arc）。**  
用有序偶<Vi,Vj>来表示，Vi称为弧尾（Tail），Vj称为弧头（Head）。如果图中任意两个顶点之间的边都是有向边，则称该图有向图（Directed graphs）。图1-2就是有向图。**连接顶点A到D的有向边就是弧，A是弧尾，D是弧头，<A,D>表示弧，注意不能写成<D,A>。**  
![在这里插入图片描述][20200702095044734.png_pic_center]

图1-2  
对于图1-2中的有向图来说，G=（V 2,\{E 2\}），其中顶点集合V 2=\{A，B，C，D\};弧集合E 2=\{<A,D><B,A><C,A>,<B,C>\}。  
**无向边用（）表示，有向边使用<>表示。  
在图中，若不存在顶点到其自身的边，且同一条边不重复出现，则称这样的图为简单图。**  
在无向图中，如果任意两个顶点之间存在边，则称该图为无向完全图。含有n个顶点的无向完全图有n（n-1）/2条边。如图1-3就是一个无向完全图，因为每个顶点都要除它以外的顶点连线，顶点A与顶点BCD连线，共有四个顶点，自然是4\*3，但由于顶点A与顶点B连线后，计算B与A连线就是重复，因此要整体除以2，共有6条边。  
![在这里插入图片描述][20200702112752949.png_pic_center] 图1-3

**在有向图中，如果任意两个顶点之间都存在方向弧尾相反的两条弧。则称该图为有向完全图。含有n个顶点的有向完全图有n（n-1）条边，** 如图1-4所示。  
![在这里插入图片描述][20200702113405416.png_pic_center]

图1-4  
从这里也可以得出一个结论，对于具有n 个顶点和e条边数的图无向图0=<e=<n(n-1)/2，有向图0=<e=<n(n-1)。

\*\*有很少条边或弧的图称为稀疏图，反之为稠密图。\*\*这里的稀疏和稠密是模糊的概念，都是相对而言的。比如我去火车站那天，人数差不多5万人，我个人感觉人数太多，可以用稠密来形容。可后来听说，那天人数只有10万左右，5万人是多么的稀疏啊。

有些图的边或者弧具有与他相关的数字，这种与**图的边或弧相关的数叫做权（Weight）**。这些权可以表示从一个顶点到顶一个顶点的距离或耗费。**这种带权的图通常称为网（Network）**。图1-5就是一张带权的图，即标识中国四大城市的直线距离的网，此图中的权就是两地的距离。  
![在这里插入图片描述][20200702114610602.png_pic_center]

图1-5

## 图的顶点与边间关系 ##

**对于无向图G=(V,\{E\})，如果边(v,v’)∈E，则称顶点v和v’互为邻接点（Adjacent），即v和v’相邻接，边(v,v’)依附（incident）于顶点v和v’，或者说(v,v’)与顶点v和v’相关联。顶点v的度（Degree）是和v相关联的边的数目，记为TD(v)**

**对于有向图G=(V,\{E\})，如果弧<v,v’>∈E，则称顶点v邻接到顶点v’，顶点v’邻接自顶点v。弧<v,v’>和顶点v,v’相关联，以顶点为头的弧的数目称为v的入度（InDegree），记为ID(v)，以v为尾的弧的数目称为v的出度（OutDegree），记为OD(v)；顶点v的度为TD(v)=ID(v)+OD(v)**

**路径的长度是路径上的边或弧的数目**

**第一个顶点到最后一个顶点相同的路径称为回路或环（Cycle），序列中顶点不重复出现的路径称为简单路径，除了第一个顶点和最后一个顶点外，其余顶点不重复出现的回路，称为简单回路或简单环，如下图1-6左图为简单环，右图不是简单环**

![在这里插入图片描述][20200702120453847.png_pic_center]

图1-6

## 连通图 ##

**在无向图G中，如果从顶点v到顶点v’有路径，则称v和v’是连通的，如果对于图中任意两个顶点vi、vj∈E，vi和vj都是连通的，则称G是连通图（Connected Graph）**。如1-7中的图1 他的顶点A到顶点B，C,D都是连通的。但显然顶点A与顶点E或F就无路径，因此不能算是连通图。而图2，顶点A,B,C,D相互都是连通的。所以他本身是连通图。

无向图中的极大连通子图称为连通分量，它强调：

*  要是子图
 *  子图要是连通的
 *  连通子图含有极大顶点数
 *  具有极大顶点数的连通子图包含依附于这些顶点的所有边

![在这里插入图片描述][20200702120705367.png_pic_center]![在这里插入图片描述][20200702121801579.png_pic_center]

图1-7  图1-7中的图1是一个无向非连通图，但是他有两个连通分量，即图2和图3、而图4，尽管是图1的子图，但是他却不满足连通子图的极大顶点数（图2满足），因此他不是图1的无向图的连通分量。

\*\*在有向图G中，如果对于每一对vi、vj∈V、vi≠vj，从vi到vj和从vj到vi都存在路径，则称G是强连通图。有向图中的极大强连通子图称做有向图的强连通分量，\*\*如下图1-8所示，左图并不是强连通图，右图是强连通图，且是左图的极大强连通子图，即是左图的强连通分量。  
![在这里插入图片描述][2020070212274578.png_pic_center]

图1-8  
**一个连通图的生成树是一个极小的连通子图，它含有图中全部的n个顶点，但只有足以构成一棵树的n-1条边**，如下图1-9所示。  
![在这里插入图片描述][20200702122931563.png_pic_center] 图1-9  
图1是一个普通图，但显然不是生成树，当去掉两边构成环的边后，比如图2或图3，就满足n个顶点n-1条边且连通的定义了。他们都是一棵生成树，从这里也可以知道，如果一个图有n个顶点和小于n-1条边，则是非连通图，如果他多于n-1条边，必定构成一个环，因为这条边使它依附的那两个顶点之间有了第二条路径。图2和图3，随便加哪两顶点的边都将构成环，不过有n-1条边并不一定是生成树，比如图4。

**如果一个有向图恰有一个顶点的入度为0（根结点），其余顶点的入度均为1，则是一棵有向树。一个有向图的生成森林由若干棵有向树组成，含有图中全部顶点，但只有足以构成若干棵不相交的有向树的弧，如下图1-10**  
![在这里插入图片描述][20200702124825224.png_pic_center]

图1-10

[20200702093732424.png_pic_center]: https://img-blog.csdnimg.cn/20200702093732424.png#pic_center
[20200702095044734.png_pic_center]: https://img-blog.csdnimg.cn/20200702095044734.png#pic_center
[20200702112752949.png_pic_center]: https://img-blog.csdnimg.cn/20200702112752949.png#pic_center
[20200702113405416.png_pic_center]: https://img-blog.csdnimg.cn/20200702113405416.png#pic_center
[20200702114610602.png_pic_center]: https://img-blog.csdnimg.cn/20200702114610602.png#pic_center
[20200702120453847.png_pic_center]: https://img-blog.csdnimg.cn/20200702120453847.png#pic_center
[20200702120705367.png_pic_center]: https://img-blog.csdnimg.cn/20200702120705367.png#pic_center
[20200702121801579.png_pic_center]: https://img-blog.csdnimg.cn/20200702121801579.png#pic_center
[2020070212274578.png_pic_center]: https://img-blog.csdnimg.cn/2020070212274578.png#pic_center
[20200702122931563.png_pic_center]: https://img-blog.csdnimg.cn/20200702122931563.png#pic_center
[20200702124825224.png_pic_center]: https://img-blog.csdnimg.cn/20200702124825224.png#pic_center