定义

图是由若干给定的顶点及连接两顶点的边所构成的图形，这种图形通常用来描述某些事物之间的某种特定关系。顶点用于代表事物，连接两顶点的边则用于表示两个事物间具有这种关

图的数据存储结构

图是由顶点的有穷非空集合和顶点之间边的集合组成，通过表示为G(V,E)
其中，G标示一个图，V是图G中顶点的集合，E是图G中边的集合。

图的属性定义

1. 图中的数据元素，称之为顶点(Vertex)；

2. 线性表中可以没有数据元素，称为空表，树种可以没有元素，叫做空树。但是图不存在没有数据元素的情况，最少会有一个顶点。

3. 在图中，任意两个顶点都可能有关系，顶点之间的逻辑关系用边表示。

4. 无边图：若顶点Vi到Vj之间的边没有方向，则称这条边为无项边（Edge），用序偶对(Vi,Vj)标示。如果有方向，就用<Vi，Vj>表示。

5. 在无向图中，如果任意两个顶点之间都存在边，则称为该图为无向完全图。例如：

   
   

6. 如果从顶点Vi到Vj的边有方向，则称为这条边为有向边，也称为弧。
   用有序偶<Vi,Vj>来表示，Vi称为弧尾，Vj称为弧头。如果任意两个顶点之间的边都是有向边，则称为该图为有向图。在有向图中，如果任意两个顶点之间都存在方向相反的两条弧，则称为该图为有向完全图。

7. 权（Weight）：有些图的边和弧有相关的数，这个数叫做权（Weight）。这些带权的图通常称为网（Network）。例如：

   
   

8. 连通图：在无向图中，如果从顶点V到V'有路径，则称V和V'是连通的，如果任意两个顶点Vi,Vj都是连通的，则称该图是连通图。

9. 度：无向图中，顶点的边数叫度，有向图中，顶点的边数，叫出度和入度。

图的存储结构

邻接矩阵

图的邻接矩阵的存储方式是用两个数组来表示图，一个一维数组存储图中的顶点信息，一个二维数组存储图中的边和弧的信息。例如：

横着的是出度，竖着的是入度。

带权的邻接矩阵

例如：

邻接表

邻接矩阵会存在空间浪费的现象，讲到了一种孩子表示法，将结点存入数组，并对结点的孩子进行链式存储，不管有多少孩子，也不会存在空间浪费问题，这个思路同样适用于图的存储。我们把这种数组与链表相结合的存储方法称为邻接表。

无向图的邻接表

无向图连接表就是讲顶点连接的元素用链表的形式表现出来，如图，这是一个无向图连接表

V0连接着V1，V2，V3，所以第一排的表就是1，2，3
V1连接着V0和V2，所以第二排的表就是0和2
V2连接着V0，V1，V3，所以第三排的表就是0，1，3
V3连接着V0和V2，所以第四排的表就是0和2

有向图的邻接表

有向图连接表就是讲顶点出度的的顶点用链表的形式表现出来，如图，这是一个有向图连接表

V0出度的顶点是V3，所以第一行表就是3
V1出度的顶点是V0，V2，所以第二行表就是0，2
V2出度的顶点是V0，V1，，所以第三行表就是0，1
V3没有出度的顶点，所以第四行没有

带权邻接表

如果在连接表加入权，那么就是带权连接表，如下图

数据结构导读目录