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

图的定义：

在数据结构中，图是一个由节点（或称作顶点）和边组成的集合。每个节点可以代表一个人、地方、物体或其他实体，而边代表节点之间的连接关系或相互关系。具体来说：

• 节点（Vertex）：图的基本单位，代表现实世界中的一个实体。
• 边（Edge）：连接两个节点的线段，代表节点之间的联系。节点之间的这种联系可以是双向（无向边）也可以是单向的（有向边）。
• 度（Degree）：一个节点的度指的是与它相连的边的数量，在无向图中每个连接该节点的边算作一度；而在有向图中，则分为入度（指向该节点的边的数量）和出度（从该节点出发的边的数量）。
• 邻接关系（Adjacency）：表示图中节点之间的连接情况，可以通过邻接矩阵或者邻接表来表示。
• 路径（Path）：从一个节点到另一个节点通过边进行行走的序列。
• 环（Cycle）：一条起点和终点为同一节点的路径，表示从某个节点出发最后又回到这个节点。
• 连通性（Connectivity）：如果任意两个节点之间都存在路径，则称该图为连通图。若每两个节点间都至少有一条路径，则为强连通图。
• 图的分类：
  • 根据边的方向性分：无向图和有向图。
  • 根据边是否加权分：无权图和有权图。
  • 根据各节点的连接方式分：简单图（不包含多条边和环）和多重图（可能有多条边且允许环的存在）。

最小生成树的特点：

最小生成树（Minimum Spanning Tree, MST）是图论中的一个重要概念，主要用于连接图的所有的顶点，且确保每个顶点都只被访问一次，同时保证所有边的总权重最小。

特点如下：

• 连接原始图中全部顶点：最小生成树包含原图的所有顶点，无冗余。
• 构成树形结构：虽然包含原图中所有顶点，但没有环。这意味着能够形成一棵连通所有节点的“树”，而不会有回溯。
• 边权重之和最小：在保留所有顶点连通的同时，边的总权重为最小的。
• 适用于无向图：最小生成树主要用于无向加权图。
• 满足条件无唯一性：对于某些图来说，其最小生成树可能不只一个。

常见的寻找最小生成树的算法包括Kruskal算法和Prim算法，这两种算法都用于寻找最小生成树，但它们在查找最小生成树时候的思路和实现有所不同。