数据结构-图

学习路径如下：

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

完整工程：zjZSTU/graph_algorithm

什么是图

• 图

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

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

• 子图

假设有两个图$G(V,E)$和$G^{\prime }(V^{\prime },E^{\prime })$，如果$V^{\prime }\subseteq V$且$E^{\prime }\subseteq E$， 则称$G^{\prime }$为$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)$条边

相关阅读

• 《大话数据结构》第7章 图
• 数据结构与算法——图论基础与图存储结构
• 无向图