数据结构之图zzx的blog.pptxVIP

数据结构之图zzx的blog

CATALOGUE目录图论基础图的存储结构图的遍历最小生成树最短路径问题拓扑排序与关键路径图的应用实例分析

01图论基础

图是由顶点集和边集组成的数据结构，表示为G=(V,E)，其中V是顶点的集合，E是边的集合。图的定义图可以用邻接矩阵、邻接表、边集数组等多种方式表示。其中邻接矩阵适用于稠密图，邻接表适用于稀疏图。图的表示方法图的定义与表示

根据边的方向性，图可以分为有向图和无向图；根据顶点的连通性，图可以分为连通图和非连通图。图具有一些基本性质，如无向图中所有顶点的度数之和等于边数的2倍，有向图中所有顶点的入度之和等于出度之和等。图的类型与性质图的性质图的类型

03度数无向图中与顶点相关联的边的数量，有向图中分为入度和出度。01顶点图中的数据点，通常表示为V。02边连接两个顶点的线段，通常表示为E。图的基本术语

路径连通性环子图图的基本术一个顶点到另一个顶点所经过的边的序列。如果图中任意两个顶点之间都存在路径，则称该图是连通的。路径的起点和终点相同的路径，且路径中其他顶点不重复出现。如果图G1的顶点集和边集都是图G2的顶点集和边集的子集，则称G1是G2的子图。

02图的存储结构

邻接矩阵表示法优点直观、简单、好理解；方便检查任意一对顶点间是否存在边；方便找任一顶点的所有“邻接点”（有边直接相连的顶点）。定义邻接矩阵是表示顶点之间相邻关系的矩阵。对于无权图，若顶点i与顶点j之间有边相连，则邻接矩阵中第i行第j列的元素值为1；否则为0。对于有权图，若顶点i与顶点j之间有边相连，则邻接矩阵中第i行第j列的元素值为该边的权值；否则为无穷大（表示不可达）。缺点不便于增加和删除一个顶点；浪费空间——存稀疏图（点很多而边很少）有大量无效元素。

优点便于增加和删除一个顶点；节省存储空间——存稀疏图时只需存储实际存在的边。缺点不便于检查任意一对顶点间是否存在边；找任一顶点的所有“邻接点”需要遍历整个链表。邻接表表示法

优点便于检查任意一对顶点间是否存在边；找任一顶点的所有“邻接点”和“逆邻接点”都比较方便。缺点结构比较复杂，需要更多的存储空间来存储额外的指针信息。十字链表表示法

03图的遍历

深度优先遍历01访问起始顶点v；02依次从v的未被访问的邻接点出发，进行深度优先遍历；03直至图中和v有路径相通的顶点都被访问；04若此时图中尚有顶点未被访问，则从一个未被访问的顶点出发，重新进行深度优先遍历，直到图中所有顶点均被访问过为止。

广度优先遍历访问起始顶点v；对v的每个邻接点vi，再访问vi的所有未被访问过的邻接点；访问v的所有未被访问过的邻接点；如此继续，直到所有顶点都被访问过。

非递归遍历算法使用一个栈或队列来保存待访问的顶点；首先将起始顶点入栈或入队；当栈或队列非空时，取出栈顶或队首元素进行访问，并将其未被访问过的邻接点入栈或入队；重复上述过程，直到栈或队列为空，此时所有顶点都被访问过。

04最小生成树

实现方式使用优先队列（堆）优化，每次取出距离最小的边，判断该边是否连接已有点集和未有点集，若是则加入最小生成树。时间复杂度O(ElogE)，其中E为边数。算法思想从某一点开始，每次加入与已有点集最近的点，直到所有点都加入。Prim算法

123从小到大枚举所有边，若该边连接的两个点不在同一连通块中，则加入最小生成树。算法思想使用并查集维护连通块，每次合并两个连通块。实现方式O(ElogE)，其中E为边数。时间复杂度Kruskal算法

网络建设电路设计交通规划图像处理最小生成树的应用在计算机网络中，最小生成树算法可以用于构建最低成本的网络拓扑结构。在交通规划中，最小生成树算法可以用于设计最短路径或最低成本的交通网络。在电路设计中，最小生成树算法可以用于确定最小电阻或最小成本的电路连接方式。在图像处理中，最小生成树算法可以用于图像分割、边缘检测等任务。

05最短路径问题

算法思想：Dijkstra算法是一种单源最短路径算法，用于计算一个节点到其他所有节点的最短路径。它采用贪心策略，每次从未被访问的节点中选择距离源节点最近的节点进行访问，并更新其邻居节点的距离。Dijkstra算法

算法步骤2.创建一个空集合S，用于存放已找到最短路径的节点。1.初始化距离数组dist[]，将源节点到各节点的距离初始化为无穷大，源节点到自身的距离初始化为0。Dijkstra算法

3.对于未被访问的节点，选择距离源节点最近的节点u，将其加入集合S中，并标记为已访问。5.重复步骤3和4，直到所有节点都被访问过。算法特点：Dijkstra算法适用于没有负权边的图，能够求得源节点到其他所有节点的最短路径。4.对于节点u的所有邻居节点v，如果通过u到达v的距离比当前已知的距离更短，则更新dist[v]的值。Dij