图的定义与分类 #

图的基本定义 #

• 图的数学定义
• 顶点与边的概念
• 图的表示方法

图的分类 #

• 有向图与无向图
• 加权图与无权图
• 连通图与非连通图
• 简单图与多重图
• 完全图与稀疏图

图的基本术语 #

顶点相关术语 #

• 顶点的度
• 入度与出度
• 孤立顶点
• 悬挂顶点

边相关术语 #

• 邻接边
• 平行边
• 自环边
• 边的权重

路径与连通性 #

• 路径的定义
• 简单路径与回路
• 连通分量
• 强连通与弱连通

图的存储结构 #

邻接矩阵 #

• 邻接矩阵的定义
• 邻接矩阵的优缺点
• 邻接矩阵的空间复杂度

邻接表 #

• 邻接表的定义
• 邻接表的实现方式
• 邻接表的优缺点

其他存储结构 #

• 十字链表
• 邻接多重表
• 边集数组

图的基本操作 #

图的遍历 #

• 深度优先搜索(DFS)
• 广度优先搜索(BFS)
• 遍历的应用场景

图的构建与修改 #

• 图的创建
• 顶点与边的添加
• 顶点与边的删除
• 图的复制与销毁

图的性质与定理 #

基本性质 #

• 握手定理
• 图的同构
• 图的补图

特殊图的性质 #

• 树的性质
• 二分图的性质
• 平面图的性质

图的应用领域 #

计算机科学应用 #

• 网络路由算法
• 社交网络分析
• 编译器优化

实际工程应用 #

• 交通网络规划
• 电路设计
• 项目管理

图的算法基础 #

最短路径算法 #

• Dijkstra算法
• Floyd算法
• Bellman-Ford算法

最小生成树算法 #

• Prim算法
• Kruskal算法
• 最小生成树的应用

拓扑排序 #

• 拓扑排序的定义
• 拓扑排序的算法
• 拓扑排序的应用