【复习笔记】数据结构之图

【复习笔记】数据结构之图

文章目录

​​一、顶点的度​​​​二、顶点—顶点关系的描述​​​​三、连通图与强连通图​​​​四、子图​​​​五、连通分量​​​​六、生成树​​​​七、几种特殊形态的图​​​​八、图的存储​​​​1.邻接矩阵法​​​​邻接矩阵的性质​​​​2. 邻接表法​​​​3. 十字链表法​​​​九、图的遍历​​​​1. 广度优先遍历（BFS）​​​​广度优先生成树​​​​2. 深度优先遍历（DFS）​​​​深度优先生成树​​​​图的遍历与图的连通性​​​​十、最小生成树​​​​1. 相关概念​​​​2. Prim算法​​​​3. Kruskal算法​​​​算法对比​​​​十一、最短路径问题​​​​1.Dijkstra算法​​​​2. Floyd算法​​​​十二、有向无环图​​​​构造有向无环图步骤​​

一、顶点的度

对于无向图，顶点的度 = 依附于该顶点的边的数量对于有向图，入度 = 出度 = 边的数量

二、顶点—顶点关系的描述

三、连通图与强连通图

四、子图

五、连通分量

六、生成树

七、几种特殊形态的图

无向完全图、有向完全图

树、森林、有向树

八、图的存储

1.邻接矩阵法

对于不带权无向图，求顶点的度时，只需要对某行或某列求和即可

对于不带权有向图，对行求和表示顶点的出度，对列求和表示顶点的入度

邻接矩阵的性质

2. 邻接表法

邻接表和邻接矩阵的对比：

3. 十字链表法

只能存储有向图，一个结构体表示一条边

九、图的遍历

1. 广度优先遍历（BFS）

广度优先生成树

根据遍历的顺序，构造生成树

邻接表中结点顺序不同，构造的生成树也不同。用邻接矩阵构造的生成树必唯一。

2. 深度优先遍历（DFS）

类似于树的先序遍历。

图的DFS： 遍历一个点，然后遍历与该点相邻的第一个点，接着再遍历与正在遍历结点第一个相邻的且未被访问的结点，如此下去，直到某个遍历的结点不存在没遍历的结点，然后返回上层。上层接着遍历相邻的第二个未被访问的结点

复杂度分析

深度优先生成树

根据深度优先遍历的顺序，构造生成树

图的遍历与图的连通性

无向图

有向图

十、最小生成树

1. 相关概念

2. Prim算法

从某个顶点开始构建生成树，每次将代价最小的新顶点纳入生成树，直到所有顶点都纳入为止。同一个图构建的 最小生成树不唯一。

3. Kruskal算法

每次选择一条权值最小的边，使这条边的两头连通（原本已经连通就不选），直到所有结点都连通。

算法对比

十一、最短路径问题

1.Dijkstra算法

​​参考代码​​

注： Dijkstra不能解决带负权值的图

2. Floyd算法

注： Floyd不能解决带负权值的图

十二、有向无环图

答案选A：

构造有向无环图步骤

三个加号的操作数相同，合并3个加号：

右侧两个乘号的操作数相同，合并2个乘号：

注： 不同层的运算符不可能合并

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。