数据结构中1. 图的定义？ 2. 最小生成树的特点？

1. **图的定义：** 在数据结构中，图是一个由节点（或称作顶点）和边组成的集合。每个节点可以代表一个人、地方、物体或其他实体，而边代表节点之间的连接关系或相互关系。具体来说： - **节点（Vertex）**：图的基本单位，代表现实世界中的一个实体。 - **边（Edge）**：连接两个节点的线段，代表节点之间的联系。节点之间的这种联系可以是双向（无向边）也可以是单向的（有向边）。 - **度（Degree）**：一个节点的度指的是与它相连的边的数量，在无向图中每个连接该节点的边算作一度；而在有向图中，则分为入度（指向该节点的边的数量）和出度（从该节点出发的边的数量）。 - **邻接关系（Adjacency）**：表示图中节点之间的连接情况，可以通过邻接矩阵或者邻接表来表示。 - **路径（Path）**：从一个节点到另一个节点通过边进行行走的序列。 - **环（Cycle）**：一条起点和终点为同一节点的路径，表示从某个节点出发最后又回到这个节点。 - **连通性（Connectivity）**：如果任意两个节点之间都存在路径，则称该图为连通图。若每两个节点间都至少有一条路径，则为强连通图。 - **图的分类**： - 根据边的方向性分：无向图和有向图。 - 根据边是否加权分：无权图和有权图。 - 根据各节点的连接方式分：简单图（不包含多条边和环）和多重图（可能有多条边且允许环的存在）。 2. **最小生成树的特点：** 最小生成树（Minimum Spanning Tree, MST）是图论中的一个重要概念，主要用于连接图的所有的顶点，且确保每个顶点都只被访问一次，同时保证所有边的总权重最小。 特点如下： - **连接原始图中全部顶点**：最小生成树包含原图的所有顶点，无冗余。 - **构成树形结构**：虽然包含原图中所有顶点，但没有环。这意味着能够形成一棵连通所有节点的“树”，而不会有回溯。 - **边权重之和最小**：在保留所有顶点连通的同时，边的总权重为最小的。 - **适用于无向图**：最小生成树主要用于无向加权图。 - **满足条件无唯一性**：对于某些图来说，其最小生成树可能不只一个。 常见的寻找最小生成树的算法包括Kruskal算法和Prim算法，这两种算法都用于寻找最小生成树，但它们在查找最小生成树时候的思路和实现有所不同。