数据结构-图

发表于 更新于 分类于
本文字数： 1.2k 阅读时长 ≈ 2 分钟

学习路径如下：

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

完整工程：zjZSTU/graph_algorithm

什么是图

  • 图

图（Graph）是由顶点的有穷非空集合和顶点之间边的集合组成，通常表示为：\(G(V，E)\)，其中，\(G\)表示一个图，\(V\)是图\(G\)中顶点（vertex）的集合，\(E\)是图\(G\)中边（edge）的集合

注意：图可以没有边，不能没有顶点

  • 子图

假设有两个图\(G(V,E)\)和\({G}'({V}',{E}')\)，如果\({V}'\subseteq V\)且\({E}'\subseteq E\)， 则称\({G}'\)为\(G\)的子图（subgraph）

简单图

图中不存在顶点到自身的边，且同一条边不重复出现，称这样的图为简单图

之后的讨论都是基于简单图进行的

权重/网

  • 权重（weight）

与边相关的数称为权重（weight）

  • 网

带权重的图通常称为网（network）

有向图/无向图

  • 无向边（undirected edge）

若顶点\(x\)和\(y\)之间的边没有方向，则称该边为无向边，用无序偶对\((x,y)\)表示。\((x,y)\)与\((y,x)\)意义相同，仅表示\(x\)和\(y\)之间有连接

  • 有向边（directed edge）

若顶点\(u\)和\(v\)之间的边有方向，则称该边为有向边（也称为弧\(Arc\)），用有序偶对<u,v>表示，表示从\(u\)指向\(v\)。称\(u\)为该边的起点（origin）或尾顶点/弧尾（tail），称\(v\)为该边的终点（destination）或头顶点/弧头（head）

  • 无向图

图中任意两个顶点之间的边都是无向边，称该图为无向图（undirected graph）

  • 有向图

图中任意两个顶点之间的边都是有向边的图称为有向图（directed graph）

  • 混合图

包含无向边和有向边的图称为混合图（mixed graph）

注意：无向边用小括号\(()\)表示，有向边用尖括号\(<>\)表示

稀疏图/稠密图/完全图

  • 稀疏图（sparse graph）

顶点很少互相连接的图

  • 稠密图（dense graph）

顶点几乎都能两两连接的图

  • 完全图（complete graph）

每个顶点均与除自身之外的其他顶点连接的图

  • 无向完全图

在无向图中，如果任意两个顶点之间都存在边，则称该图为无向完全图

含有\(n\)个顶点的无向完全图有\(\frac {n\times (n-1)}{2}\)条边

  • 有向完全图

在有向图中，如果任意两个顶点之间都存在方向互为相反的两条弧，则称该图为有向完全图

含有\(n\)个顶点的有向完全图有\(n\times (n-1)\)条边

相关阅读