数据结构笔记

数据结构笔记

图

图的定义

• 线性表中：数据元素是串起来的仅仅只有线性关系（一对一）

• 树形结构中：数据元素之间有明显的层次关系（一对多）

• 图：是一种较线性表和树更加复杂的结构（多对多）

图的定义：
图（Graph）是由顶点的有穷非空集合（意思是图不能没有顶点但可以没有边）和顶点之间边的集合组合成的，通常表示为
G ( V , E ) G(V,E) G(V,E)
其中：

• V：顶点（数据元素的）的有穷集合；

• E：边的有穷集合。

G r a p h = ( V e r t e x , E d g e ) Graph=(Vertex,Edge) Graph=(Vertex,Edge)

图的定义几个需要注意的点：

• 线性表中的数据元素叫做元素，树中的数据元素叫做结点，图中的数据元素叫做顶点（Vertex）。

• 线性表中可以没有元素，叫做空表。树中可以没有结点，叫做空树。但在图的结构中不允许没有顶点，图的定义中顶点集合V的有穷非空性。

• 线性表中，相邻的数据元素之间具有线性关系，树结构中，相邻的两层的结点具有层次关系，而图中，任意两个顶点之间都有可能有关系，顶点之间的逻辑关系用边来表示，边集E可以是空的。

各种图的定义

• 无向图：每条边都是无方向。

图中的无向边用无序偶对 ( V i , V j ) (V_i,V_j) (Vi​,Vj​)来表示。

无向图 G 1 G_1 G1​ , G 1 = ( V 1 , { E 1 } ) G_1=(V_1,{E_1}) G1​=(V1​,{E1​})

其中：

顶点集合 V 1 = { A , B , C , D } V_1={A,B,C,D} V1​={A,B,C,D}

边集合 E 1 = { ( A , B ) , ( B , C ) , ( C , D ) , ( D , A ) } E_1={(A,B),(B,C),(C,D),(D,A)} E1​={(A,B),(B,C),(C,D),(D,A)}

• 有向图：每条边都是有方向的。

有向边也称为弧（Arc），用有序偶 < V i , V j > <V_i,V_j> <Vi​,Vj​>来表示， V i V_i Vi​表示弧尾（也就是有向边箭头的尾部，出发的顶点）， V j V_j Vj​表示弧头（也就是有向边箭头的头部，终点的顶点）。

有向图 G 2 G_2 G2​ , G 2 = ( V 2 , { E 2 } ) G_2=(V_2,{E_2}) G2​=(V2​,{E2​})

其中：

顶点集合 V 2 = { A , B , C , D } V_2={A,B,C,D} V2​={A,B,C,D}

边集合 E 2 = { < A , B > , < B , C > , < C , D > , < D , A > } E_2={<A,B>,<B,C>,<C,D>,<D,A>} E2​={<A,B>,<B,C>,<C,D>,<D,A>}

有向边和无向边的表示方法是不同的。

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

以下讨论的都是简单图

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

n个顶点，有 n ( n − 1 ) / 2 n(n-1)/2 n(n−1)/2条边（计算方式：任意两个边之间都有一条边，所以是 C n 2 C_n^2 Cn2​）

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

n个顶点，有 n ( n − 1 ) n(n-1) n(n−1)条边（计算方式：有向图边数乘2）

简单结论： 对于具有n个顶点和e条边数的图，无向图 0 ≤ e ≤ n ( n − 1 ) / 2 0leq e leq n(n-1)/2 0≤e≤n(n−1)/2,有向图 0 ≤ e ≤ n ( n − 1 ) 0leq e leq n(n-1) 0≤e≤n(n−1)。

• 稀疏图： 有很少的边或者弧（判断标准： e ≤ n log ⁡ n eleq nlog n e≤nlogn）。

• 稠密图： 与稀疏图相反。

• 网（Network）： 也就是带权的图

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

• 子图： 假设有两个图 G = ( V , { E } ) G=(V,{E}) G=(V,{E})和 G 1 = ( V 1 , { E 1 } ) G_1=(V_1,{E_1}) G1​=(V1​,{E1​})，如果 V 1 ∈ V V_1in V V1​∈V且 E 1 ∈ E E_1in E E1​∈E,就称 G 1 G_1 G1​是 G G G的子图（Subgraph）

图的顶点与边间的关系

• 邻接： 有边/弧相连接的两个顶点之间的关系。

存在 ( V i , V j ) (V_i,V_j) (Vi​,Vj​)，则称 V i V_i Vi​和 V j V_j Vj​互为相邻的点；

存在 < V i , V j > <V_i,V_j> <Vi​,Vj​>，则称 V i V_i Vi​邻接于 V j V_j Vj​，称 V j V_j Vj​邻接于 V i V_i Vi​。

• 关联（依附）： 边/弧与顶点之间的关系。

存在 ( V i , V j ) / < V i , V j > (V_i,V_j)/<V_i,V_j> (Vi​,Vj​)/<Vi​,Vj​>，则称该边/弧关联于 V i V_i Vi​和 V j V_j Vj​。

• 顶点的度(Degree)： 与该顶点相关联的边的数目，记为 T D ( v ) TD(v) TD(v)。
  • 在无向图中：
    边数就是各个顶点度数和的一半
    e = 1 / 2 ∑ i = 1 n T D ( V i ) e=1/2sum_{i=1}^nTD(V_i) e=1/2i=1∑n​TD(Vi​)
  • 在有向图中：顶点的度等于入度和出度的和。所有的入度数量等于出度数量，所以边数
    e = ∑ i = 1 n T D ( V i ) = ∑ i = 1 n O D ( V i ) e=sum_{i=1}^nTD(V_i)=sum_{i=1}^nOD(V_i) e=i=1∑n​TD(Vi​)=i=1∑n​OD(Vi​)
    • 入度(InDegree)：以V为终点的有向边的条数，记为 I D ( V ) ID(V) ID(V)；
    • 出度(OutDegree)：以V为终点的有向边的条数，记为 O D ( V ) OD(V) OD(V)。

• 路径（Path）： 连续的边构成的顶点序列。
  • 路径长度：路径上边/弧的数目/权值之和

树中根结点到任意结点的路径是唯一的，但图中顶点与顶点之间的路径却不是唯一的。

• 回路（环）（Cycle）： 第一个顶点和最后一个顶点相同的路径。
• 简单路径： 序列中顶点不重复出现的路径。
• 简单回路（环）： 除第一个顶点和最后一个顶点外，其余顶点不重复出现的路径。

连通图的相关术语

在无/有向图G中，若对任意两个顶点v,u都存在从v到u的路径，就称图G是连通图（强连通图）。

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-iKSjd6IA-1684937477217)(/Data_structures_and_algorithms/notefile/picture/连通图.jpg)]

完全图一定是（强）连通图，强）连通图不一定是完全图。

• 连通分量（强连通分量）： 无/有向图G的极大连通子图称为G的（强）连通分量。强调：
  • 要是子图；
  • 子图要是连通的；
  • 连通子图含有极大顶点数；
  • 具有极大顶点数的连通子图包含依附于这些顶点的所有边。

• 无向连通图的生成树： 一个连通图的生成树是一个极小的连通子图，它包含图中全部n个顶点，但只有足以构成一棵树的n-1条边
  • 极小的连通子图：在该子图中删除任何一条边子图不再连通（说明原本的图必须是连通图，因为图中的所有顶点，对于生成树）

图1是普通图不是生成树，图2和图3满足n个顶点n-1条边且连通的定义，是生成树。可知

1. 如果一个图有n个顶点小于n-1条边，则是非连通图，
2. 多余n-1条边，必定构成一个环，
3. n-1条边不一定是生成树。

• 有向树： 一个有向图的一个顶点入度为0，其余顶点入度均为1。

  • 入度为0，就相当于树中的根结点，
  • 其余顶点入度均为1，树的非根结点的双亲只有一个。
    

• 有向图的生成森林：各个连通分量的生成树的集合。

图2和图3的集合就是图1有向图的生成森林。

总结