图的概念和定义

Love The Way You Lie 2022-04-03 03:08 325阅读 0赞

## 1 定义 ##

图是由顶点的**有穷非空集合**和顶点之间边的集合组成，表示为G（V,E），其中G表示一个图，V是图G中顶点的集合，E是图G中边的集合。  
![在这里插入图片描述][20181220101616119.png]

若顶点vi到vj之间的边没有方向，则这条边为**无向边**，表示为（vi，vj）或（vj，vi），反之为**有向边（或弧）**，表示为＜vi，vj＞，其中vi称为弧尾，vj称为弧头。若图中所有边都为无向边，则该图为**无向图**，反之若都为有向边，则为**有向图**。  
![在这里插入图片描述][20181220102944630.png] ![在这里插入图片描述][20181220102959266.png]

**简单图**：不存在顶点到其自身的边，且同一条边不重复出现。  
**无向完全图**：任意两个顶点中都存在边的无向图。若顶点为n个，则边数为n(n-1)/2。  
**有向完全图**：任意两个顶点中都存在边的有向图。若顶点为n个，则边数为n(n-1)。  
**稀疏图和稠密图**：有很少条边或弧的图称为稀疏图，反之称为稠密图。  
**权**：与边或弧相关的数；带有权的图称为网  
![在这里插入图片描述][20181220104044665.png] ![在这里插入图片描述][20181220104057817.png]  
相邻且有边直接连接的两个顶点称为**邻接点**，列如上图中，V1和V4是邻接点，但V2和V4不是，因为它们之间没有直接相连。在图中，顶点所连边的数目称为**度**，在有向图中，由于边有方向，则顶点的度分为**入度**和**出度**。可以看出，在无向图中，边数是所有顶点度数和的一半，而在有向图中，边数=入度和=出度和。

无向图中，从顶点vi到顶点vj的**路径**是一个顶点序列，**路径的长度**为经过的边或弧的数目。第一个顶点和最后一个顶点相同的路径称为**回路或环**。序列中不出现重复的顶点称为**简单路径**。，除了第一个顶点和最后一个顶点外，其余顶点不重复的路径称为**简单回路**。如图，左图为简单回路，而右图不是，因为顶点C出现了2次。  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3pqd19weXRob24_size_16_color_FFFFFF_t_70]

## 2 连通图 ##

在无向图中，如果两个顶点之间有路径，则称这两个顶点是**连通**的。如果图中任意两个顶点都是连通的，那么该图为**连通图**。无向图中的极大连通子图称为**连通分量**，如图，图2和图3都是图1无向图的连通分量，但图4不是，因为其没有包含极大的顶点数。  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3pqd19weXRob24_size_16_color_FFFFFF_t_70 1]  
在有向图中，如果对于任意两个顶点vi和vj，都存在vi到vj和vj到vi的路径，则称那图为**强连通图**。在有向图中的极大强连通子图称做有向图的**强连通分量**。如图左图不是强连通图，因为没有顶点D到顶点A的路径，而右图则是强连通图，其也是左图的强连通分量。  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3pqd19weXRob24_size_16_color_FFFFFF_t_70 2]  
一个连通图的**生成树**是一个极小连通子图，它含有图中全部n个顶点，但只有n-1条边。在一条生成树中添加一条边，则必然构成一个环，如果减少一条边，则是非连通图。如图图1为连通图，图2和图3都是图1的生成树，但图4不是，因为它不连通。  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3pqd19weXRob24_size_16_color_FFFFFF_t_70 3]  
若一个有向图恰有一个顶点入度为0，其余顶点的入度均为1，则是一棵**有向树**。一个有向图的**生成森林**由若干棵有向树组成，含有图中全部顶点，但只有足以构成若干棵不相交的有向树的弧。如图，图2和图3是图1的生成森林。  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3pqd19weXRob24_size_16_color_FFFFFF_t_70 4]

## 3 图的抽象数据类型 ##

ADT{ 
    	Data
    		顶点的有穷非空集合和边的集合
    	Opeartion
    		CreateGraph(*G,V,VR)  //按照顶点集V合边弧集VR定义构造图G
    		DestroyGraph(*G)      //销毁图G
    		LocateVex(G,u)        //返回图G中顶点u的位置，若不存在，则返回其他信息
    		GetVex(G,v)           //返回图G中顶点v的值
    		PutVex(G,v,value)     //将图G中顶点v赋值value
    		FirstAdjVex(G,*v)     //返回顶点v的一个邻接顶点，若无则返回空
    		NextAdjVex(G,v,w)     //顶点w是顶点v的邻接顶点，返回顶点v相对于顶点w的下一个邻接顶点
    							   //若顶点w是顶点v的最后一个邻接顶点，则返回空
    		InsertVex(*G,v)		 //在图G种添加顶点v
    		DeleteVex(*G,v)       //删除图G中顶点v及其相关的弧
    		InsertArc(*G,v,w)     //在图G中添加弧<v,w>,如果是无向图，还要添加对称弧<w,v>
    		DeleteArc(*G,v,w)	  //在图G中删除弧<v,w>,如果是无向图，还要删除对称弧<w,v>
    		DFSTraverse(G)        //对图G进行深度优先遍历
    		HFSTraverse(G)		 //对图G进行广度优先遍历
    }

[20181220101616119.png]: /images/20220403/684dbda73b694280a56f3ec1c5d5b143.png
[20181220102944630.png]: https://img-blog.csdnimg.cn/20181220102944630.png
[20181220102959266.png]: /images/20220403/442f4a8500584e13b61ebf3ef219d66b.png
[20181220104044665.png]: https://img-blog.csdnimg.cn/20181220104044665.png
[20181220104057817.png]: /images/20220403/8f610068641342edb9297c42f8234a4f.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3pqd19weXRob24_size_16_color_FFFFFF_t_70]: /images/20220403/3b4a892376ea443f89043481820da9ef.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3pqd19weXRob24_size_16_color_FFFFFF_t_70 1]: /images/20220403/43ae5316896546b798e030c0090c409e.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3pqd19weXRob24_size_16_color_FFFFFF_t_70 2]: /images/20220403/4cbf0ea7b47c4c32a43f66ab7f03b608.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3pqd19weXRob24_size_16_color_FFFFFF_t_70 3]: /images/20220403/d5b03ddae99c44059c4c86a3f51c138d.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3pqd19weXRob24_size_16_color_FFFFFF_t_70 4]: /images/20220403/6f90ba41073f4156bc8018e58de4cde7.png