数据结构与算法 图_数据结构算法流程图

目录

一、定义

二、图的存储

1、数组（邻接矩阵）表示法

1.1、邻接矩阵表示法创建无向网

2、邻接表表示方法（链式）

2.1  采用邻接表表示法创建无向图

三、图的遍历

1、深度优先搜索（DFS）

2、广度优先搜索（BFS）

四、生成树

1、定义

2、小生成树（MST）

3、构造最小生成树算法

3.1 普里姆（Prim）算法

3.2 克鲁斯卡尔（Kruskal）算法

五、最短路径

1、简述

2、Dijkstra（迪杰斯特拉）算法 

3、Floyd（佛洛伊德）算法

六、有向无环图的应用

1、拓扑排序

2、关键路径

一、定义

图是一种比较常用的数据结构，有许多定义需要理解，下面一一介绍。

                                                                             

                            

连通图（强连通图）：在无（有）向图G=(V, {E})中，若对任何两个顶点v、u都存在从v到u的路径，则称G是连通图（强连通图）。 如下图：                                                                                         

权与网：图中边或弧所具有的相关数称为权，表明从一个顶点到另一个顶点的距离或耗费。带权的图称为网。 

子图：设有两个图G=(V, {E})、G1=(V1, {E1})、若V1  V，E1  E，则称G1是G的子图。              

                                                        

       

图的几个重要操作：

                                       

二、图的存储

图的逻辑结构是多对多的形式，图没有顺序存储结构，但是可以借助二维数组来表示元素间的关系。

数组表示法：邻接矩阵

链式存储结构：多重链表（邻接表、邻接多重表、十字链表）

重点学习：邻接矩阵（数组）表示法、邻接表（链式）表示法

1、数组（邻接矩阵）表示法

                                                                                                                                                                                                                                                      

 

1.1、邻接矩阵表示法创建无向网

   

                                                          

邻接矩阵的优缺点：                                                                     

                                              

2、邻接表表示方法（链式）

                                                             

                                                                                                                                                                            

邻接表相关操作举例：

2.1  采用邻接表表示法创建无向图

                                           

                                                

邻接表的特点：

邻接矩阵与邻接表两种表示法的关系：

                                               

三、图的遍历

图的遍历分为深度优先和广度优先。

1、深度优先搜索（DFS）

                                                                                                                                            

DFS算法时间效率分析：

  

2、广度优先搜索（BFS）

BFS时间效率分析：

DFS与BFS算法比较：

四、生成树

1、定义

                                                                                                                                     

最小生成树的典型应用：

                    

2、小生成树（MST）

MST性质分析：

3、构造最小生成树算法

3.1 普里姆（Prim）算法

3.2 克鲁斯卡尔（Kruskal）算法

两种算法比较：

五、最短路径

1、简述

                                           

最短路径问题分类：

                                                                                                                                

2、Dijkstra（迪杰斯特拉）算法 

                                          

3、Floyd（佛洛伊德）算法

                                                                                                   

六、有向无环图的应用

   

1、拓扑排序

AOV网特点：

 

    

2、关键路径