数据结构入门-图

数据结构

发布日期: 2022-10-03

更新日期: 2022-11-08

文章字数: 1.9k

阅读时长: 6 分

阅读次数:

图

图形结构是多对多的关系，任何两个数据元素都可能有关系，每个节点可以有多个前驱和后继。

图的基本术语

图通常用一个二元组 G=<V, E>表示，V 表示顶点集，E 表示边集。

|V|表示顶点集中元素的个数，即顶点数，n 个顶点的图称为 n 阶图。
|E|表示边集中元素的个数，即边数。

注意：顶点集 V 和边集 E 均为有限集合，其中 E 可以为空集，V 不可以为空集，但在运算中，可能产生 V 为空集。

V 为空集的图称为空图，记为φ 。

无向图

若图 G 中每条边都是没有方向的，则称为无向图。

每条边都是两个顶点组成的无序对，例如顶点 v₁ 和顶点 v₃ 之间的边，记为（v₁ , v₃）或（v₃ , v₁）
有向图

若图 G 中每条边都是有方向的，则称为有向图。

有向边也称为弧，每条弧都是由两个顶点组成的有序对，例如从顶点 v₁ 到顶点 v₃ 的弧，记为<v₁，v₃ >，v₁ 称为弧尾，v₃ 称为弧头。
简单图

既不含平行边也不含环的图称为简单图。
- 平行边：
  
  在无向图中，若关联一对顶点的无向边多于一条，则称这些边为平行边，平行边的条数称为重数；
  
  在有向图中，若关联一对顶点的有向边多于一条，并且这些边的始点和终点相同（方向一致），则称这些边为平行边
  
  含有平行边的图称为多重图。平行边的条数称为重数。
- 自环：
  
  自环是指一条边关联的两个顶点为同一个顶点，也就是说自己到自己有一条边。
完全图

在无向图中，若任意两个点都有一条边，则该图称为无向完全图。

含有 n 个顶点的无向图，每个顶点到其他的 n−1 个顶点都有边，一共有 n(n−1)/2 条边。

在有向图中，若任意两个点都有两条方向相反的两条弧，则该图称为有向完全图。

含有 n 个顶点的有向图，每个顶点发出 n−1 条边，并且进来 n−1 条边，一共有 n(n−1)条边。
稀疏图和稠密图

有很少边或弧的图称为稀疏图，反之，则称为稠密图。这是一个非常模糊的概念，很难讲多少算稀疏，多少算稠密，一般来说，若图 G 满足|E|<|V|×log|V|，则称 G 为稀疏图。
网

在实际应用中，经常在边上标注如距离、时间、耗费等数值，该数值称为边的权值。带权的图称为网。
邻接和关联

邻接是指顶点和顶点之间的关系，关联是指边和顶点之间的关系。

有边/弧相连的两个顶点之间的关系，如无向边(v_i, v_j)，则称 v_i 和 v_j 互为邻接点；有向边<v_i, v_j>，则称 v_i 邻接到v_j，v_j 邻接于 v_i。若存在(v_i, v_j)或<v_i, v_j>，则称该边或弧关联于 v_i 和 v_j，
顶点的度

顶点的度是指与该顶点相关联的边的数目，记为 TD(v)。

握手定理：度数之和等于边数的两倍

如果在计算度数时，每算一度划一条线，则可以看出每条边被计算了两次。

在有向图中，顶点的度又分为入度和出度：
- 顶点 v 的入度是以 v 为终点的有向边的条数，记作 ID(v)，即进来的边数。
- 顶点 v 的出度是以 v 为始点的有向边的条数，记作 OD(v)，即发出的边数。
顶点 v 的度等于其入度和出度之和，即：

在有向图中，所有顶点的入度之和等于出度之和，又因为所有顶点度数之和等于边的 2倍，因此：
路径、路径长度和距离

路径：接续的边的顶点构成的序列。

路径长度：路径上边或弧的数目。

距离：从顶点到另一顶点的最短路径长度。
回路（环）、简单路径和简单回路

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

简单路径：除路径起点和终点可以相同外，其余顶点均不相同的路径。

简单回路：除路径起点和终点相同外，其余顶点均不相同的路径。
子图与生成子图

子图：设有两个图 G=(V, E)、G1 =(V1 , E1 )，若 V1⊆V，E1 ⊆ E，则称 G1 是 G 的子图。从图中选择若干个顶点、若干条边构成的图称为原图的子图。

生成子图：从图中选择所有顶点，若干条边构成的图称为原图的生成子图。
连通图和连通分量

连通图：在无向图中，如果顶点 v i 到 v j 有路径，则称 v i 和 vj 是连通的。

如果图中任何两个顶点都是连通的，则称 G 为连通图。

连通分量：无向图 G 的极大连通子图称为 G 的连通分量。极大连通子图意思是：该子图是 G 的连通子图，如果再加入一个顶点，该子图不连通。

对于连通图，其连通分量就是它自己；对于非连通图，则有 2 个以上连通分量。
强连通图和强连通分量

强连通图：在有向图中，如果图中任何两个顶点 v i 到 v j 有路径，且 v j 到 v i 也有路径，则称 G 为强连通图。

强连通分量：有向图 G 的极大强连通子图称为 G 的强连通分量。极大强连通子图意思是：该子图是 G 的强连通子图，如果再加入一个顶点，该子图不再是强连通的。
树和有向树

从图论的角度来看，树是一个无环连通图。

一个含 n 个顶点、m 条边的图，只要满足下列 5 个条件之一就是一棵树：
- G 是连通图且 m=n−1；
- G 是连通图且无环；
- G 是连通图，但删除任意一条边就不连通；
- G 是无环图，但添加任意一条边就会产生环；
- G 中任意一对顶点之间仅存在一条简单路径。
有向树：只有一个顶点入度为 0，其余顶点入度均为 1 的有向图
生成树和生成森林

极小连通子图：该子图是 G 的连通子图，在该子图中删除任何一条边，该子图不再连通。

生成树：包含无向图 G 所有顶点的极小连通子图。

因为生成树包含所有顶点，因此只有连通图才有生成树，而非连通图，每一个连通分量会有一棵生成树。

生成森林：对非连通图，由各个连通分量的生成树组成的集合。
二分图

二分图，又称为二部图，是图论中的一种特殊模型。设 G=<V，E>是一个无向图，如果顶点集 V 可分割为两个互不相交的子集 V1、V2，并且图中的每条边(i, j)所关联的两个顶点 i 和 j 分别属于这两个不同的顶点集(i∈V1 , j∈V2 )，则称图 G 为二分图：