计算机基础知识——数据结构与算法（五）（山东省大数据职称考试）

   大数据分析应用-初级

第一部分 基础知识

       一、大数据法律法规、政策文件、相关标准

       二、计算机基础知识

       三、信息化基础知识

       四、密码学

       五、大数据安全

       六、数据库系统

       七、数据仓库.

第二部分 专业知识

       一、大数据技术与应用

       二、大数据分析模型

       三、数据科学

数据结构与算法

• 大数据分析应用-初级
• 前言
• 一、图的描述方法与应用
• 二、图的应用
• 练习题目

前言

数据结构与算法

5、掌握图的描述方法与应用。

一、图的描述方法与应用

图的描述方法

常用概念：

图是由顶点集合V和边集合E构成的数据结构，即G=(V,E)。

邻接矩阵

邻接表

 说明:

        标号为0的结点的相关联的结点为 1 2 3 4

        标号为1的结点的相关联结点为0 4，

        标号为2的结点相关联的结点为 0 4 5

        。。。。。

十字链表（针对有向图）

定义：十字链表是将有向图的邻接表和逆邻接表结合起来的一种存储结构。在十字链表中，顶点表节点有三个域：数据域（存储顶点信息）、firstin（指向以该顶点为终点的第一条边）和 firstout（指向以该顶点为起点的第一条边）。边表节点有四个域：tailvex（边的起点在顶点表中的下标）、headvex（边的终点在顶点表中的下标）、hlink（指向终点相同的下一条边）和 tlink（指向起点相同的下一条边）。

优点：可以方便地找到以一个顶点为起点或终点的所有边，对于有向图的一些操作（如求顶点的入度、出度等）效率较高。

邻接多重表（针对无向图）

定义：邻接多重表的顶点表节点结构与邻接表类似，有数据域和 firstedge（指向第一条依附于该顶点的边）。边表节点有五个域：mark（标记域，用于标记边是否被访问等）、ivex（边的一个端点在顶点表中的下标）、jvex（边的另一个端点在顶点表中的下标）、ilink（指向下一条依附于 ivex 顶点的边）和 jlink（指向下一条依附于 jvex 顶点的边）。

优点：在处理无向图的一些操作（如删除边等）时，相比于邻接表可以避免对两条边（因为无向图的一条边在邻接表中会被存储两次）的重复操作，提高了效率。

二、图的应用

最短路径问题

Dijkstra 算法（单源最短路径，非负权边）

Floyd - Warshall 算法（多源最短路径）

最小生成树问题

Prim 算法（贪心算法）

Kruskal 算法（贪心算法）

拓扑排序（针对有向无环图）

图的遍历

深度优先搜索（DFS）

广度优先搜索（BFS）

练习题目