07-图

type
status
date
slug
summary
tags
category
icon
password

1️⃣ 图的分类

类型
说明
有向图
边有方向，如 (A → B)
无向图
边无方向，如 (A - B)
带权图
边带有权值，如地图上的距离
稀疏图/稠密图
边少 / 边多的图
连通图
任意两点间至少存在一条路径
有环图 / 无环图（DAG）
是否存在回路（如拓扑排序的 DAG）

1.邻接矩阵（Adjacency Matrix）

  • graph[i][j] = 1 表示顶点 i 与 j 有边
  • 空间复杂度：
  • 适合稠密图

2.邻接表（Adjacency List）

  • 更节省空间，适合稀疏图
  • 时间复杂度取决于度数

2️⃣ 图的遍历算法

1.DFS（深度优先搜索）

  • 沿一个方向尽可能深地搜索，走不通回退
  • 可用于：连通块、拓扑排序、环检测、岛屿数量

2.BFS（广度优先搜索）

BFS（广度优先搜索，Breadth-First Search） 是图与树中常用的遍历算法，其特点是按层逐层遍历，适用于：
  • 最短路径搜索（如迷宫、图中路径）
  • 层序遍历（如树）
  • 连通块查找
 
上一篇
06-AVL / 红黑树
下一篇
08-B 树/B+树/B*树
Loading...