一、图
图是由一组节点和边组成的非线性数据结构,用于描述节点之间的关系。图的节点称为顶点,边表示顶点之间的连接关系。图可以用于描述现实世界中的各种关系,例如社交网络中的好友关系、城市之间的道路连接、电路中的元器件连接等。
图的主要特点包括:
1. 顶点:图的基本单位,用于表示实体或抽象概念。
2. 边:用于表示顶点之间的连接关系,可以是有向或无向的,带权或不带权的。
3. 路径:连接图中两个顶点的路径是由一系列相邻的边构成的序列。
4. 连通性:如果图中任意两个顶点之间都存在路径,则称该图为连通图,否则为非连通图。
5. 度:顶点的度表示与该顶点相邻的边的数量。
6. 子图:图中的一部分称为子