数据结构图的存储

‘壹’ 图的定义与存储

图状结构是一种比树形结构更复杂的非线性结构。在树形结构中，结点间具有分支层次关系，每一层上的结点只能和上一层的至多一个结点相关，但可能和下一层的多个结点相关。而在图状结构中，任意两个结点之间都可能相关，即结点之间的邻接关系可以是任意的。因此，图是 比树更一般、更复杂的非线性结构，常被用于描述各种复杂的数据对象，在自然科学、社会科学和人文科学等许多领域有着非常广泛的应用。

图（Graph）是由非空的顶点集合和一个描述顶点之间的关系——边（或者弧）的集合组成的，其形式化定义为：G=(V,E)、V={v1|v1包含data object}、E={(v1,vj)|(vi,vj 包含V^P(vj,vj)。其中，G表示一个图，V是图G中顶点的集合，E是图G中边的集合，集合E中P(vi,vj)表示顶点vi和顶点vj之间有一条直接连线，即偶对(v1,vj）表示一条边。如：G2=(V2,E2)、V2={v1,v2,v3,v4}、E2={<v1,v2>,<v1,v3>,<v3,v4>,<v4,v1>}。

1、无向图：在一个图中，如果任意两个顶点构成的偶对(vi,vj）包含E是无序的，即顶点之间的连线是没有方向的，则称该图为无向图。

2、有向图：在一个图中，如果任意两个顶点构成的偶对<vj,vj>包含E是有序的（有序对常常用尖括号“<>”表示），即顶点之间的连线是有方向的，则称该图为有向图。

6、顶点的度、入度、出度：顶点的度（Degree）是指依附于某顶点v的边数，通常记为TD(v)。顶点v的入度是指以顶点v为终点的弧的数目，记为ID(V)；出度是指以顶点v为始点的弧的数目，记为OD(V)。有TD(V)=ID(v)+OD(v)。

7、边的权、网：与边有关的数据信息称为权(Weight)。在实际应用中，权值可以有某种含义。例如，在一个反映城市交通线路的图中，边上的权值可以表示该条线路的长度或等级；对于一个电子线路图，边上的权值可以表示两个端点之间的电阻、电流或电压值；对于反映工程进度的图而言，边上的权值可以表示从前一个工程到后一个工程所需要的时间或其他代价等。边上带权的图称为网或网络（network）。

8、路径、路径长度：顶点vp到顶点vq之间的路径（path）是指顶点序列vp、vi1、vi2、···、vim、vq。其中，（vp，vi1）、（vi1，vi2）、···、（vim，vq）分别为图中的边。路径上边的数目称为路径长度。

9、简单路径、回路、简单回路：序列中顶点不重复出现的路径称为简单路径。路径中第一个顶点与最后一个顶点相同的 路径称为回路或环（Cycle）。除第一个顶点与最后一个顶点之外，其他顶点不重复出现的回路称为简单回路，或者简单环。

10、子图：对于图G=（V，E），G'=（V',E'），若存在 V'是V的子集， E'是E的子集，则称图 G'是G的的一个子图。

11、连通、连通图、连通分量：在无向图中，如果从一个顶点vi到另一个顶点vj(i=!j)存在路径，则称顶点vi和vj是连通的。如果图中任意两个顶点都是连通的，则称该图是连通图。无向图的极大连通子图称为连通分量，极大连通子图是指在保证连通与子图的条件下，包含原图中所有的顶点与边。 如下图：

12、强连通图、强连通分量：对于有向图来说，若图中任意一对顶点vi和vj（i=!j）均存在从一个顶点vi到另一个顶点vj和从vj到vi的路径，则称该有向图是强连通图。有向图的极大强连通子图称为强连通分量，极大强连通子图的含义同上。

13、生成树：所谓连通图G的生成树，是G的包含其全部n个顶点的一个极小连通子图，所谓极小连通子图是指在包含所有顶点且保证连通的前提下尽可能少地包含原图中的边。生成树必定包含且仅包含连通图G的n-1条边。在生成树中添加任意一条属于原图中的边必定会产生回路，因为新添加的边使其所依附的两个顶点之间有了第二条路径。若生成树中减少任意一条边，则必然成为非连通的。

14、生成森林：在非连通图中，由每个连通分量都可得到一个极小连通子图，即一棵生成树。这些连通分量的生成树就组成了一个非连通图的生成森林。

将上图存储到计算机中，请设计一个数据结构并将其合理存储起来？

所谓邻接矩阵（Adjacency Matrix）的存储结构，就是用一维数组存储图中的顶点信息，用矩阵表示图中各顶点的信息，用矩阵表示图中各顶点的信息，用矩阵表示图中各顶点之间的邻接关系。假设图G=(V,E)有n个确定的顶点，即V ={v0,v1，···，vn-1}，则表示G中各顶点相邻关系的矩阵为一个n×n的矩阵，矩阵的元素为：

A[i][j]={1,若(vi,vj)或<vi,vj>是E(G)中的边 ；2，若(vi,vj）或<vi,vj>不是E(G)中的边。

若G是网，则邻接矩阵可定义为：

A[i][j]={wij,若(vi,vj)或<vi,vj>是E(G)中的边 ；0或&，若(vi,vj）或<vi,vj>不是E(G)中的边。

（1）无向图的邻接矩阵一定是一个对称矩阵。因此，在具体存放邻接矩阵时只需存放上或下三角矩阵的元素即可。

（2）对于无向图，邻接矩阵的第i行或第i列非零元素或非&元素的个数正好是第i个顶点的度TD(vi)。

（3）对于有向图，邻接矩阵的第i行货第i列非零元素或非&元素的个数正好是第i个顶点的出度OD(vi)或如度ID(vi)。

（4）用邻接矩阵方法存储图，很容易确定图中任意两个顶点之间是否有边相连；但是，要确定图中有多少条边，则必须按行、按列对每个元素进行检测，所花费的时间代价很大。这是用邻接矩阵存储图的局限性。

在实际应用邻接矩阵存储图时，除了用一个二维数组存储用于表示顶点间相邻关系的邻接矩阵外，还需用一个一维数组来存储顶点信息，另外，还有图的顶点树和边树。故可将其形式描述如下：

邻接表（Adjacency List）是图的一种顺序存储于链式存储结合的存储方法。邻接表表示法类似于树的孩子链表表示法。就是对于图G中的每个顶点vi，将所有邻接于vi的顶点vj链成一个单链表，这个单链表就称为顶点vi的邻接表，再将所有顶点的邻接表表头放到数组中，就构成了图邻接表。

在邻接表表示中有两种结点结构：一种是顶点表的结点结构，它由顶点域（vertex）和指向第一条邻接边的指针域（firstedge）构成。另一种是边表即邻接表结点，它由邻接点域（adjvex）和指向下一条邻接边的指针域（next）构成。对于网的边表需再增设一个存储边上的信息（如权值等）的域（info）。

‘贰’ 图的存储结构是什么

由于图的结构比较复杂，任意两个顶点之间都可能存在关系（边），无法通过存储位置表示这种任意的逻辑关系，所以，图无法采用顺序存储结构。这一点同其他数据结构（如线性表、树）不同。考虑图的定义，图是由顶点和边组成的，所以，分别考虑如何存储顶点和边。图常用的存储结构有邻接矩阵、邻接表、十字链表和邻接多重表。

‘叁’ 图的存储结构有哪些

最常见的：
顺序查找：适合顺序结构和链式结构
二分查找：适合顺序结构

其他的二叉查找树、B-树之类有自己的数据结构

‘肆’ 什么是数据结构的存储方式

1. 集合结构：在这种结构中，数据元素之间没有任何关系，除了它们都属于同一个集合。
2. 线性结构：线性结构的特点是数据元素之间存在一对一的关系，即每个元素只有一个直接前驱和一个直接后继。
3. 树形结构：树形结构中的数据元素之间存在一对多的关系。这种结构类似于家族树，其中每个节点（除了根节点）只有一个父节点，但可以有多个子节点。
4. 图状结构或网状结构：在这种结构中，数据元素之间存在多对多的关系。图可以用来表示网络、路径或其他任何类型的复杂关系。
(4)数据结构图的存储扩展阅读：数据不仅限于数字，它可以包括文字、字母、数字符号的组合、图形、图像、视频、音频等，是用来表示客观事物属性、数量、位置及其相互关系的抽象表示。例如，“0、1、2…”、“阴、雨、下降、气温”、“学生的档案记录、货物的运输情况”等都是数据。数据经过处理后变成信息。在计算机科学中，数据是指所有能输入计算机并被计算机程序处理的符号的总称，这些符号可以是数字、字母、符号和模拟量等。随着计算机科学的发展，数据的类型和复杂性也在不断增加。

‘伍’ 有关图的存储结构

(1)顺序存储方法
该方法把逻辑上相邻的结点存储在物理位置上相邻的存储单元里，结点间的逻辑关系由存储单元的邻接关系来体现。
由此得到的存储表示称为顺序存储结构 (Sequential Storage Structure)，通常借助程序语言的数组描述。
该方法主要应用于线性的数据结构。非线性的数据结构也可通过某种线性化的方法实现顺序存储。 (2)链接存储方法
该方法不要求逻辑上相邻的结点在物理位置上亦相邻，结点间的逻辑关系由附加的指针字段表示。由此得到的存储表示称为链式存储结构(Linked Storage Structure),通常借助于程序语言的指针类型描述。