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

女爷i 2022-06-14 01:09 325阅读 0赞

# 数据结构——图的基本概念 #

不同于线性结构和树形结构，图结构中的元素之间的关系是多对多的。

## 1、相关定义： ##

>  *  **图：**图G由数据元素（顶点）集合V和边的集合E组成。分为无向图和有向图，无向图中边e的取值范围是0~n(n-1)/2，有向图中e的取值范围是0~n(n-1)，其中n为图中顶点的个数。![20170606095344244][]
>  *  **邻接点：**在无向图G=(V,E)中，如果存在边(vi,vj)∈E，那么称vi和vj互为邻接点。在有向图G=(V,A)中，如果存在弧<vi,vj>∈A，那么称vi和vj相互邻接。
>  *  **顶点的度：**在无向图中，顶点v的度为与顶点v相关联的边的条数，记为TD(v)。在有向图中，以v为弧头的弧的条数称为v的入度，记为ID(v)，以v为弧尾的弧的条数称为v的出度，记为OD(v)，TD(v)=ID(v)+OD(v)。边数e与顶点的度TD(v)的关系为：e = 1/2∑TD(vi)
>  *  **路径：**从vi出发经过一系列顶点到达顶点vj称为从vi到vj的路径。路径的长度为路径上边或弧的数目，顶点不重复出现的路径称为**简单路径**。
>  *  **子图：**两个图G=(V,E)和G'=(V',E')，如果V‘含于V并且E'含于E，那么G’称为G的子图。
>  *  **连通图和强连通图：**无向图中，如果顶点vi到vj有路径，则称vi与vj是**连通的**。如果图中任意两个顶点之间都是连通的，那么这个图就是连通图。在有向图中，如果任意两个顶点vi，vj，从vi到vj和从vj到vi都存在路径，那么称图为强连通图。
>  *  **网：**边或弧上带有权值的称为网。

## 2、图的抽象数据类型 ##

>  *  CreateGraph(&G)：创建图
>  *  DestroyGraph(&G)：销毁图
>  *  LocateVertex(G,v)：在图G中定位顶点v的位置
>  *  GetVertex(G,j)：返回图G中编号为j的顶点
>  *  FirstAdjVertex(G,v)：返回图G中v的第一个邻接点
>  *  NextAdjVertex(G,v)：返回G中v的下一个邻接点
>  *  InsertVertex(&G,v)：在图G中插入新的顶点v
>  *  DeleteVertex(&G,v)：删除图G中的顶点v
>  *  InsertArc(&G,v,w)：在图G中插入新的弧
>  *  DeleteArc(&G,v,w)：删除G中的弧
>  *  DFSTraverseGraph(G)：深度优先遍历图
>  *  BFSTraverseGraph(G)：广度优先遍历图

## 3、图的存储结构 ##

>  *  邻接矩阵表示法
>  *  邻接表表示法
>  *  十字链表表示法
>  *  多重链表表示法

[20170606095344244]: /images/20220614/87666b5ef8cf422eb26117e6b301d366.png