什么是非线性数据结构

非线性数据结构指的是一个元素的直接前驱和直接后继都不只有0个或者1个，而树中一个元素的直接后继不可以有多个，图的直接前驱和直接后继都不可以有多个。

一、基本介绍

非线性结构中各个数据元素不再保持在一个线性序列中，数据元素之间是一对多，或者是多对一的关系。根据关系的不同，可分为层次结构（树）和群结构（图）。

常见的非线性结构有二维数组，多维数组，广义表，树(二叉树等)，图。（其中多维数组是由多个一维数组组成的，可用矩阵来表示，他们都是两个或多个下标值对应一个元素，是多对一的关系，因此是非线性结构。）

相对应于线性结构，非线性结构的逻辑特征是一个结点元素可能对应多个直接前驱和多个后继。

二、非线性结构图的相关概念

用于深度和广度搜索算法一般就是用来做图的遍历，或者说图是搜索算法的最常用数据结构，因此需要先储备一些图的概念。

图是由一个非空的顶点集合和一个边的集合组成。 G＝( V, E )

1.无向图：任意两顶点构成的偶对(vi , vj )是无序的。一个顶点的连接边数叫作结点的度。一个完全无向图有n(n-1)/2 条边。

2.有向图：顶点之间的关系（边）有方向，因此把度也分成了出度和入度。表示微博中的用户关注度可用

3.带权图：边加了权重的图。表示网络中，QQ好友亲密度度可用

4.完全图：（1）若 n 个顶点的无向图有 n(n-1)/2 条边, 称为无向完全图

（2）若 n 个顶点的有向图有n(n-1) 条边, 称为有向完全图

5.邻接矩阵：优点是容易实现图的操作，如：求某顶点的度、判断顶点之间是否有边（弧）、找顶点的邻接点等等。缺点是n个顶点需要n*n个单元存储边(弧);空间效率为O(n2)。

6.邻接表：对每个顶点vi 建立一个单链表，把与vi有关联的边的信息（度）链接起来。优点是空间效率高且容易寻找顶点的邻接点