数据结构与算法图.pptxVIP

数据结构与算法图

2024-01-25

CATALOGUE

目录

图的基本概念与性质

图的存储结构

图的遍历算法

最小生成树算法

最短路径算法

拓扑排序与关键路径

图的基本概念与性质

01

图是由顶点集和边集组成的数据结构，表示为G=(V,E)，其中V是顶点的集合，E是边的集合。

图的定义

图可以用邻接矩阵、邻接表、边集数组等多种方式表示。其中邻接矩阵适用于稠密图，邻接表适用于稀疏图。

图的表示方法

连通性

如果图中任意两个顶点之间都存在路径，则称该图是连通的。

路径

从一个顶点到另一个顶点所经过的边的序列。

度

与顶点相关联的边的数量。对于有向图，度分为入度和出度。

顶点

图中的数据点，通常用小写字母表示。

边

连接两个顶点的线段，表示顶点之间的关系。边可以是有向的或无向的。

欧拉回路与欧拉图

欧拉回路是指通过图中的每一条边恰好一次并回到起点的路径。存在欧拉回路的图称为欧拉图。

平面图与对偶图

可以画在平面上且任意两条边只在端点相交的图称为平面图。平面图的对偶图是由平面图的面构成的图，其中两个面相邻当且仅当它们共享一条边。

最小生成树与最短路径

对于连通的无向图，其所有边的权值之和最小的生成树称为最小生成树。对于有向图，从起点到终点的所有路径中权值之和最小的路径称为最短路径。

哈密尔顿回路与哈密尔顿图

哈密尔顿回路是指通过图中的每一个顶点恰好一次并回到起点的路径。存在哈密尔顿回路的图称为哈密尔顿图。

图的存储结构

02

定义

01

邻接矩阵是表示图的一种简单方式，对于n个顶点的图，邻接矩阵是一个n×n的矩阵，其中矩阵元素A[i][j]表示顶点i与顶点j之间的边的信息。

优点

02

直观、简单、好理解方面，对于稠密图而言，邻接矩阵是一种非常不错的存储方式，并且使用邻接矩阵来表示图的话，很容易看出图中任意两个顶点之间是否有边相连。

缺点

03

对于稀疏图而言，邻接矩阵是不适用的，因为它将浪费大量的存储空间。

邻接表是图的一种链式存储结构，对于n个顶点的图，邻接表包含n个顶点表和若干个边表。

定义

对于稀疏图而言，邻接表是一种非常不错的存储方式，因为它可以节省大量的存储空间。

优点

对于稠密图而言，邻接表可能不是最优的选择，因为访问某个顶点的所有邻居可能需要遍历整个边表。

缺点

定义

十字链表是图的另一种链式存储结构，可以看作是将邻接表和逆邻接表结合起来得到的一种链表。

优点

容易找到以某个顶点为起点或终点的所有边，也容易找到与某个顶点相邻的所有顶点。

缺点

结构比较复杂，需要为每个顶点分配两个链表（一个正向链表和一个反向链表），并且需要为每个边分配两个结点（一个正向结点和一个反向结点）。因此，十字链表的存储密度较低。

图的遍历算法

03

深度优先遍历（Depth-FirstSearch，DFS）是一种用于遍历或搜索树或图的算法。这个算法会尽可能深地搜索树的分支。

在图中，这个算法是用来标记已经访问和未被访问过的顶点，并保留标记的顶点信息，以防止重复访问。

DFS使用栈来保存需要后续处理的顶点。当访问到某个顶点时，将其标记为已访问，并将其相邻的未访问顶点加入栈中。然后重复此过程，直到栈为空。

BFS使用队列来保存需要后续处理的顶点。当访问到某个顶点时，将其标记为已访问，并将其相邻的未访问顶点加入队列中。然后重复此过程，直到队列为空。

广度优先遍历（Breadth-FirstSearch，BFS）是另一种图遍历算法，它是按照层次进行遍历的。

BFS从图的某一顶点出发，首先访问它的所有相邻顶点，然后再对这些相邻顶点进行同样的操作，直到所有的顶点都被访问过。

除了递归方式实现图的遍历外，还可以使用非递归方式实现。非递归方式通常使用栈或队列来辅助实现遍历过程。

在非递归的深度优先遍历中，可以使用一个栈来保存需要后续处理的顶点。首先将起始顶点入栈，然后进入一个循环，每次从栈顶取出一个顶点进行访问，并将其相邻的未访问顶点入栈。重复此过程直到栈为空。

在非递归的广度优先遍历中，可以使用一个队列来保存需要后续处理的顶点。首先将起始顶点入队，然后进入一个循环，每次从队首取出一个顶点进行访问，并将其相邻的未访问顶点入队。重复此过程直到队列为空。

最小生成树算法

04

时间复杂度

Kruskal算法的时间复杂度为O(ElogE)，其中E为边的数量。

算法思想

Kruskal算法每次选择一条连接两个未连接顶点的最小边加入生成树，直到生成树中包含所有顶点为止。

空间复杂度

Kruskal算法需要维护一个并查集和一个边集合，因此空间复杂度为O(V+E)。

最短路径算法

05

基本思想

从起点开始，逐步向外扩展，每次找到距离起点最近的顶点，并更新与其相邻顶点的距离

时间复杂度

O(n^2)，其中n为顶点数

优点

稳定且易于实现

通过动态规划的思想，逐步计算