数据结构 - 图（基础概念）
[TOC]
我们知道， 数据结构 是存储相互之间存在的一种或多种特定关系的数据元素的集合。也即，数据结构是对数据的存储与数据关系的描述。
实际上，数据结构强调的是对数据关系的描述，存储只是为了持有数据，同时在底层以一个合适的存储结构对数据进行组织，以便更好地满足对数据关系的描述。
对于数据的存储结构，有按前驱后继的线性组织形式排列的，比如线性表。也有数据按层的方式进行组织的，比如说树（结点与结点之间是一种层次关系）。
但是，无论是哪种数据存储组织方式，其基本底层存储结构主要就是数组和链表。因此，很多其他的数据结构底层真正用于存储数据就是数组和链表，然后在这之上构建出线性或层次组织。
对于数据关系的描述，我们知道，数据之间存在四种关系：
简而言之， 图 是一种较线性表和树等数据结构更加复杂的结构，在图中，元素之间的关系可以是任意的，图中任意两个数据元素之间都可能存在关系。
因此，对于图的元素之间的关系描述就显得比较复杂。
简单来说， 图 是由顶点和边组合而成，其结构示意图如下所示：
对于图的定义，有以下几个地方需要明确注意：
图是一个相对复杂的数据结构，为了更好地对图进行描述，让我们先来了解下与图相关的一些基础概念，主要包含如下：
注 ：实际上，如果一个图有 个顶点和小于 条边，则它是非连通图。
由前面的内容可以知道，图中的元素主要由顶点和边（或弧）组成，任意两个顶点之间都可能存在联系，而顶点和边本身也存在联系，因此图的结构比较复杂，很难以数据元素在内存中的物理位置来表示图中元素之间的关系，也就是说， 图不可能仅用简单的顺序存储结构（即数组）来表示 。而多重链表尽管可以实现图结构（即以一个数据域和多个指针域组成的结点表示图中的一个顶点），但是却存在内存浪费或操作不便的问题。因此，图存储结构最终还是得通过结合顺序存储和链式存储才能做到比较好地实现。
当前用于图的存储主要有以下 5 种结构：
迈杰
2024-11-30 广告
