数据结构-图2

发表于 更新于 分类于 阅读次数：21
本文字数： 1.4k 阅读时长 ≈ 3 分钟

学习路径如下：

  1. 图的基本定义
  2. 顶点/边/图的关系（本文学习内容）
  3. 图的存储结构
  4. 深度/广度优先遍历
  5. 最小生成树

完整工程：zjZSTU/graph_algorithm

度/入度/出度

对于无向图G=(V,E)，如果边(u,v)∈E，则称顶点u和v互为邻接点（adjacent），即u和v相邻接

对于有向图G=(V,E)，如果弧<u,v>∈E，则称顶点u邻接到顶点v，顶点v邻接自顶点u

  • 度

顶点v的度（degree）是和v相关联的边的数目，记为TD(v)

  • 入度

以顶点v为头的弧的数目称为v的入度（InDegree），记为ID(v)

  • 出度

以顶点v为尾的弧的数目称为v的出度（OutDegree），记为OD(v)

对于有向边<u,v>而言，顶点u是弧尾，顶点v是弧头，所以ID(v)=1, OD(u)=1

对无向图而言，仅存在度的概念；对于有向图而言，同时还存在入度和出度的概念，入度和出度之和就是该顶点的度：TD(v)=ID(v)+OD(v)

路径

  • 路径

图G(V,E)中从顶点u到顶点v的路径（path）是一个顶点序列(V=v0,v1,...,vm)，其中v0=u,vm=v,(vi−1,vi)⊆E,1≤i≤m

  • 回路或环（cycle）

第一个顶点和最后一个顶点相同的路径

  • 简单路径

序列中顶点不重复出现的路径

  • 简单回路或简单环

除了第一个顶点和最后一个顶点相同外，其余顶点不重复出现的回路

连通图/连通分量

  • 连通图

在一个无向图G中，若从顶点vi到顶点vj有路径相连，则称vi和vj是连通的。如果图中任意两点都是连通的，那么图被称作是连通图

  • 强连通图

在图G中，如果对于每一对u,v⊆V,u≠v，从u到v和从v到u都存在路径，则称G是强连通图

连通图是相对于无向图而言的，强连通图是相对于有向图而言的

  • 连通分量

无向图G的极大连通子图称为G的连通分量（connected component）。任何连通图（connected graph）的连通分量仅有一个，即是其自身，非连通的无向图有多个连通分量

  • 强连通分量

有向图中的极大强连通子图称做有向图的强连通分量

生成树

  • 生成树

如果连通图G的一个子图是一颗包含G的所有顶点的树，则该子图称为G的生成树（spanning tree）

连通图的生成树是一个极小的连通子图，包含全部n个顶点，但只有足以构成一棵树的n−1条边

对于生成树而言，前提是它是连通图，也就是顶点之间有连接

  • 最小生成树

给定无向图G=(V,E)，(u,v)代表连接顶点u和v的边，w(u,v)代表此边的权重，如果存在生成树T使得w(T)最小（权值之和最小），那么称T为最小生成树(MST, Minimum Spanning Tree)

相关阅读