数据结构（六）：图论基础

文章目录

• 1. 基本概念
• 2. 存储方式
• • 2.1 邻接矩阵法
  • 2.2 邻接表法
  • 2.3 十字链表
  • 2.4 邻接多重表

重点

• 深度探索法与广度探索法
  • 图的核心要素与特征
  • 图的存储方式及其特点
  • 图的遍历过程

1. 基本概念

• simple graph ：①没有重复边；②没有自环。

• multigraph ：相对于simple graph而言的是multigraph。

• complete graph ：
  ①对于undirected graphs来说：拥有\frac{n(n-1)}{2}条edge的数量称为complete undirected graphs，并且任何两个顶点之间都存在一条edge。
  ②对于directed graphs来说：拥有n(n-1)条arc的数量称为complete directed graphs，并且任何两个顶点之间都存在两条相互反向的arc。

• 可连接性：对于无向图而言，在任意两个顶点之间都存在一条路径，则称这两个顶点是可连接的。

• 双向可达性：在有向图中，若任意一对不同的顶点u和v之间都存在从u到v以及从v到u的路径，则称这对顶点是双向可达的。

• **全互联图