一、数据结构图的定义

       数据结构图，也称为数据结构示意图，在结构分析中用于表示实体、属性和数据之间关系的一种示意图。它清晰地展示了数据元素（如顶点或节点）以及它们之间的连接关系（如边或弧）。

二、数据结构图的基本术语

1. 顶点（Vertex）：
   • 图中的基本数据元素，也称为结点。在图结构中，不允许没有顶点。
   • 在无向图中，顶点之间没有方向性。
   • 在有向图中，顶点之间的边或弧具有方向性。
2. 边（Edge）/弧（Arc）：
   • 连接两个顶点的线段。
   • 在无向图中，边没有方向，用无序偶对(v, w)表示。
   • 在有向图中，边有方向，称为弧，用有序偶<v, w>表示，v称为弧尾，w称为弧头。
3. 无向图（Undirected Graph）：
   • 任意两个顶点之间的边都是无向边的图。
   • 例如，假设有一个无向图G，顶点集合V={A, B, C, D}，边集合E={(A, B), (B, C), (C, D), (D, A)}。
4. 有向图（Directed Graph）：
   • 任意两个顶点之间的边都是有向边的图。
   • 例如，假设有一个有向图G，顶点集合V={A, B, C, D}，边集合E={<A, B>, <B, C>, <C, D>}。
5. 简单图：不存在顶点到自身的边，且同一条边不重复出现的图。
6. 完全图：
   • 无向完全图：任意两个顶点之间都存在边的无向图。含有n个顶点的无向完全图有n*(n-1)/2条边。
   • 有向完全图：任意两个顶点之间都存在方向互为相反的两条弧的有向图。含有n个顶点的有向完全图有n*(n-1)条弧。
7. 稀疏图与稠密图：
   • 稀疏图：边或弧的数量远小于顶点数量的平方的图。
   • 稠密图：与稀疏图相对，边或弧的数量较多的图。
   • 稀疏图和稠密图并没有严格的界限，但一般来说，可以根据边或弧的数量与顶点数量的平方的关系来判断。
8. 权（Weight）：
   • 与图的边或弧相关的数，通常表示某种度量（如距离、耗费等）。
   • 带权的图称为网（Network）。
9. 邻接点：
   • 在无向图中，如果边(v, w)∈E，则称顶点v和w互为邻接点。
   • 在有向图中，如果弧<v, w>∈E，则称顶点v邻接到顶点w，顶点w邻接自顶点v。
10. 顶点的度：
    • 在无向图中：与该顶点相关联的边的数目。
    • 在有向图中：分为入度和出度。入度是以该顶点为头的弧的数目，出度是以该顶点为尾的弧的数目。
11. 路径（Path）：
    • 顶点序列v1, v2, ..., vn，使得(vi, vi+1)∈E（1≤i<n），则称该序列为从v1到vn的路径。
    • 路径的长度是路径上边的数目。
12. 连通图（Connected Graph）：在无向图中，如果任意两个顶点之间都有路径，则称该图为连通图。
13. 连通分量（Connected Component）：无向图中的极大连通子图称为连通分量。
14. 强连通图（Strongly Connected Graph）：在有向图中，如果对于每一对顶点v和w，从v到w和从w到v都存在路径，则称该图为强连通图。
15. 生成树（Spanning Tree）：一个连通图的极小连通子图，它含有图中全部的n个顶点，但只有n-1条边。

三、数据结构图的存储结构

1. 邻接矩阵（Adjacency Matrix）：
   • 使用二维数组来表示图。数组的行和列分别对应图中的顶点，元素的值表示顶点之间是否存在边或弧。
   • 在无向图中，如果两个顶点之间存在边，则对应位置的值为1（或其他非零值），否则为0。
   • 在有向图中，如果两个顶点之间存在弧，则对应位置的值为1（或其他非零值），否则为0。弧的方向由行和列的顺序表示。
2. 邻接表（Adjacency List）：
   • 使用链表数组来表示图。数组的每个元素对应一个顶点，链表存储与该顶点相邻的顶点。
   • 在无向图中，每个顶点的链表存储与该顶点直接相连的所有顶点。
   • 在有向图中，每个顶点的链表存储从该顶点出发可以到达的所有顶点（即出度）。
3. 十字链表（Cross-Linked List）：
   • 有向图的一种链式存储结构。在十字链表中，对应于有向图中的每条弧有一个结点，对应于每个顶点也有一个结点。
   • 弧结点包含指向弧起点和终点的指针，以及指向下一条入边和出边的指针。
   • 顶点结点包含指向该顶点的第一条入边和第一条出边的指针。
4. 邻接多重表（Adjacency Multilist）：
   • 无向图的链式存储结构。在邻接多重表中，每条边有一个结点，每个顶点也有一个结点。
   • 边结点包含指向两个顶点的指针，以及指向下一条依附于这两个顶点的边的指针。
   • 顶点结点包含指向第一条依附于该顶点的边的指针。
5. 边集数组（Edge Set Array）：
   • 由两个一维数组构成。一个数组存储顶点信息，另一个数组存储边的信息。
   • 边的信息包括边的起点、终点和权重（如果图带权）。

 结语 

我们要反醒自己的眼光和见识

但是不要怀疑自己的真诚和善良   

！！！