图的基本概念
- 图
- 有向图
- 无向图
- 简单图
- 多重图
- 完全图(亦称 简单完全图)
- 子图
- 连通图,连通分量
- 强连通图,强连通分量
- 生成树,生成森林
- 顶点的度(入度,出度)
- 边的权和网
- 稠密图,稀疏图
- 路径,路径长度,回路
- 简单路径,简单回路
- 距离
- 有向树
图的存储
👉🏻邻接矩阵法
一维数组存储顶点信息(将顶点编号),二维数组存储顶点间关系(二维数组存储边的信息)
邻接矩阵
网(带权图)的邻接矩阵

存储结构定义:
1 |
|
👉🏻邻接表法
邻接表
是在稀疏图的情况下对邻接矩阵
的一种改进,是实际中广泛采用的一种存储结构。
结点结构

有向图和无向图的邻接表


存储结构定义
1 |
|
👉🏻十字链表
有向图
的另一种链式存储结构。可看是将有向图
的邻接表和逆邻接表结合得到的一种存储方法。对应于有向图中的每一条弧有一个结点,对应于每个顶点也有一个结点。图的十字链表不唯一,但是一个十字链表确定一个图。
好处:既容易找以 Vi 为尾的弧,又容易找到以 Vi 为头的弧 ==> 容易求得顶点的入度
和出度
。
结点结构


存储结构定义
1 | typedef struct ArcNode |
图示
👉🏻邻接多重表
无向图
的另一种链式存储结构。 是为了解决在邻接表中对同一条边存储两个结点而引入的一种结构。
结点结构

其中:
mark
为标志域,可用于标记该边是否被搜索过。
ivex
和 jvex
记录依附于该边的两个顶点;
ilink
指示依附于 ivex 的下一条边。
jlin
指示依附于 jvex 的下一条边。
info
与边相关的信息。

其中:
data
存储顶点的相关信息;
firstedge
指示第一条依附于该顶点的边
图的遍历
👉🏻深度优先遍历 (DFS)
算法思路
性能分析
深度优先生成树
👉🏻广度优先遍历 (BFS)
算法思路
性能分析
广度优先生成树
👉🏻应用
图的遍历可以用来判断图的连通性。
图的应用
- 图的遍历 —— 连通性判断
- 有向无环图 —— 拓扑排序
- 带权有向图 —— 最短路径,Dijkstra 算法