数据结构复习（第六章 图）

一.图的基本概念

1.有向图

每一条边都有一个方向，用<a,b>来表示

2.无向图

每一条边都没有方向，用（a,b）来表示，边的个数为0到n(n-1)/2

3.子图

每个边和每个点都得属于本身的图

4.生成子图

包含全部的顶点，和部分边

5.度

所有顶点的度数和为边的2倍，出度之和等与入度之和

6.简单路径

在一条路径种没有重复的顶点

7.环

第一个顶点和最后一个顶点相同

8.联通图

图中所有的结点都可以互相到达，反之就是非连通图

9.强连通图

任意两个点可以互相到达，反之有一个点到达不了其他的点就是非强连通图

10.联通分量

11.生成树

二.图的储存及基本操作

1.邻接矩阵

数据结构之图(二)——邻接矩阵_图的邻接矩阵-CSDN博客

2.邻接表

数据结构之图(三)——邻接表-CSDN博客

3.十字链法

数据结构之图的存储结构：十字链表法-CSDN博客

4.邻接多重表

数据结构之图的存储结构：邻接多重表-CSDN博客

三.图的遍历

1.深度优先搜索

深度优先搜索-CSDN博客

2.广度优先搜索

广度优先搜索-CSDN博客

四.图的应用

1.最小生成树

最小生成树算法-CSDN博客

2.最短路

最短路算法-CSDN博客

3.有向无环图（DAG）

4.拓扑排序

拓扑排序（思想+代码+示例）-CSDN博客

5.关键路径

10分钟了解关键路径及如何求得关键路径-CSDN博客