数据结构学习——图

发布网友发布时间：2024-09-15 08:29

共1个回答

热心网友时间：2024-09-30 13:11

图是数据结构中一种复杂的数据组织形式，它由顶点（Vertex）和边（Edge）组成。顶点用有限非空集合V(G)表示，边用集合E(G)表示，图可表示为G=(V,E)。顶点数量|V|称图阶，边数量|E|称图的边数。
图与线性表和树结构不同。在图中，结点间的关系可以任意，任意两个结点间都可能相关，且没有前后之分。而线性表中数据元素间仅存在线性关系，每个元素最多有一个直接前驱和后继。树形结构则具备明显的层次关系，每个元素可以与多个下层元素相关，但只能与一个上层元素相关。
根据边的指向性，图分为有向图和无向图。在有向图中，边为有向边，每条边带箭头指向性。无向图中，边无箭头，方向可逆。简单图中，任意两个顶点间最多一条边。多重图允许多条边连接两个顶点，甚至允许顶点自身有边。完全图定义为任意两个顶点间都有一条边相连。
路径、路径长度、回路等术语描述了图中结点间的连通关系。路径是顶点间的序列，路径长度为序列中顶点数量减一。回路是路径中起点和终点相同的情况。距离则是顶点间最短路径的长度，若不存在，则距离为无穷大。
连通图中任意两个顶点间有路径相连。图中最大的连通子图称为连通分量，若图自身为连通分量，即为连通图。在有向图中，若任意两个顶点间都有路径双向可达，则称图为强连通图，强连通分量是图中最大的强连通子图。
生成树和生成森林涉及图的连通性。生成树包含图中所有顶点的极小连通子图，非连通图的每个连通分量对应一个生成树，整体构成生成森林。有向树是顶点入度为0，其余顶点入度为1的有向图。
图的顶点度包括入度和出度，描述了边在顶点间的方向分布。权值赋予图中的边，形成带权图或网络。边的数量远小于顶点数量的平方时称为稀疏图，反之为稠密图。
图的存储结构多样，包括邻接矩阵、邻接表、邻接多重表、十字链表和边集数组等。常用方法包括一维数组、二维数组、链表和相交链表存储边与顶点关系。一维数组简单存储边信息，二维数组存储边及权值，链表与相交链表用于更灵活地管理边与顶点的关联。存储结构的选择取决于图的特点和操作需求。