数据结构课上笔记14

谁借莪１个温暖的怀抱￠ 2022-04-14 07:09 224阅读 0赞

**图是一种： 数据元素间存在多对多关系的数据结构 加上一组基本操作构成的抽象数据类型。**

**图 (Graph) 是一种复杂的非线性数据结构，由顶点集合及顶点间的关系（也称弧或边）集合组成。可以表示为： G＝(V, VR)**

**其中 V 是顶点的有穷非空集合；**

**VR 是顶点之间 关系的有穷集合，也叫做弧或边集合。**

**弧是顶点的有序对，边是顶点的无序对。**

**特点：（相对于线性结构）**

**顶点之间的关系是任意的**

**图中任意两个顶点之间都可能相关**

**顶点的前驱和后继个数无限制**

### 相关概念： ###

**顶点(Vertex)：图中的数据元素。线性表中我们把数据元素叫元素，树中将数据元素叫结点。**

**边：顶点之间的逻辑关系用边来表示，边集可以是空的。**

**无向边(Edge)：若顶点V1到V2之间的边没有方向，则称这条边为无向边。**

**无向图(Undirected graphs)：图中任意两个顶点之间的边都是无向边。（A,D）=（D,A）**

**无向图中边的取值范围：0≤e≤n(n-1)/2**

**有向边：若从顶点V1到V2的边有方向，则称这条边为有向边，也称弧(Arc)。用<V1,V2>表示，V1为狐尾(Tail)，V2为弧头(Head)。（V1，V2）≠（V2，V1）。**

**有向图(Directed graphs)：图中任意两个顶点之间的边都是有向边。**

**有向图中弧的取值范围：0≤e≤n(n-1)**

**注意：无向边用“（）”，而有向边用“< >”表示。**

**简单图：图中不存在顶点到其自身的边，且同一条边不重复出现。**

**无向完全图：无向图中，任意两个顶点之间都存在边。**

**有向完全图：有向图中，任意两个顶点之间都存在方向互为相反的两条弧。**

**稀疏图：有很少条边。**

**稠密图：有很多条边。**

**邻接点：若 (v, v´) 是一条边，则称顶点 v 和 v´互为 邻接点，或称 v 和 v´相邻接；称边 (v, v´) 依附于顶点 v 和 v´，或称 (v, v´) 与顶点 v 和 v´ 相关联。**

**权（Weight）：与图的边或弧相关的数。**

**网（Network）：带权的图。**

**子图（Subgraph）：假设G=（V,\{E\}）和G‘=（V',\{E'\}），如果V'包含于V且E'包含于E，则称G'为G的子图。**

**入度：有向图中以顶点 v 为头的弧的数目称为 v 的入度，记为：ID(v)。**

**出度：有向图中以顶点 v 为尾的弧的数目称为 v 的出度，记为：OD(v)。**

**度（Degree）：无向图中，与顶点V相关联的边的数目。有向图中，入度表示指向自己的边的数目，出度表示指向其他边的数目，该顶点的度等于入度与出度的和。**

**回路（环）：第一个顶点和最后一个顶点相同的路径。**

**简单路径：序列中顶点（两端点除外）不重复出现的路径。**

**简单回路（简单环）：前后两端点相同的简单路径。**

**路径的长度：一条路径上边或弧的数量。**

**连通：从顶点 v 到 v´ 有路径，则说 v 和 v´ 是连通的。**

**连通图：图中任意两个顶点都是连通的。**

**连通分量：无向图的极大连通子图（不存在包含它的 更大的连通子图）；**

**任何连通图的连通分量只有一个，即其本身；非连通图有多个连通分量（非连通图的每一个连通部分）。**

**强连通图： 任意两个顶点都连通的有向图。**

**强连通分量：有向图的极大强连通子图；任何强连通 图的强连通分量只有一个，即其本身；非强连通图有多个 强连通分量。**

**生成树：所有顶点均由边连接在一起但不存在回路的图。（n个顶点n-1条边）**

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2hlYnR1NjY2_size_16_color_FFFFFF_t_70][]

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2hlYnR1NjY2_size_16_color_FFFFFF_t_70 1][]

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2hlYnR1NjY2_size_16_color_FFFFFF_t_70]: /images/20220414/bddfd6d603194251bc403ce958aeab4a.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2hlYnR1NjY2_size_16_color_FFFFFF_t_70 1]: /images/20220414/fc597c064fdb4c55b362d07fda127777.png