备考408——数据结构基础知识

一、连通图与非连通图

无向图：边是没有方向的。
度：顶点所具有的边的数目称为顶点的度。
连通图：无向图中，任意两个顶点是连通的（一个顶点不必与另一个顶点直接相连，可以通过其它顶点到达即可）最少有n-1条边；如下：4个顶点最少需要3条边才能够连通
非连通图：即存在某个顶点无法到达另一个顶点的情况，最多有$(n-1)\ast (n-2)/2$条边（n个顶点，1个顶点孤立，(n-1)个顶点互相连接 --> $(n-1)\ast (n-2)$，又因为是无向图，所以除以2，即$(n-1)\ast (n-2)/2$）。
生成树：无向图中，包含图中全部顶点的一个极小连通子图（生成树不唯一）。若去除一条边，则生成树会变成非连通图；若多加上一条边，则会形成回路。

无向图：边是有方向的。入度是指指向该节点的边的数量；出度是指从该节点出发指向其他节点的边的数量。
度：一个顶点的入度与出度之和称为该顶点的度
强连通图：有向图中，任意两个顶点是连通的，最少有n条边（循环）。
若有向图本身不是强连通图，但其包含的最大连通子图具有强连通图的性质，则称该子图为强连通分量。参考强连通图见图

弱连通图：不是强连通图，但是如果将有向图的所有有向边替换为无向边，所得到的图（原图的基图）是连通图，则该有向图是弱连通图。

二、邻接矩阵和邻接表

邻接矩阵：数组(邻接矩阵)表示法，N个顶点，则是N*N维的矩阵。
无向图：W[i][j]=1表示顶点i到顶点j 有边，W[i][j]=0表示顶点i到顶点j 无边。
有向图：W[i][j]表示顶点i到顶点j的距离，即顶点i到顶点j的边的权重，W[i][j]=inf表示顶点i到顶点j 无边，所以是无穷大。
参考邻接矩阵

邻接表：
顶点： 按编号顺序将顶点数据存储在一维数组中。
关联同一顶点的边： 用线性链表存储。
如果有边\弧的信息，还可以在表结点中增加一项。
参考邻接表图形化讲解
若无向图中有n个顶点、e条边，则其邻接表需要n个头结点和2e个表结点。适宜存储稀疏图。
邻接矩阵多用于稠密图；而邻接表多用于稀疏图

三、树的序列

树的序列化，类似层序遍历，不一样的是，空叶子节点也要记录下来（层序遍历一般不用）。
如：

出题类型为，给出一棵树的序列化数组，询问前序、中序、后序遍历的结果。
前序： 根、左、右
中序： 左、根、右
后序： 左、右、根

四、循环队列

参考循环队列判断队满和队空
队头指针在队尾指针的下一位置时，队满。

Q.front == (Q.rear + 1) 
% MAXSIZE 因为队头指针可能又重新从0位置开始，而此时队尾指针是MAXSIZE - 1，所以需要求余。

当队头和队尾指针在同一位置时，队空。

Q.front == Q.rear

五、广义表

广义表的长度，指的是广义表中所包含的数据元素的个数，如{a,{b,c},{c,d,e}}的长度是3。
广义表的深度，可以通过观察该表中所包含括号的层数间接得到，如{a,{b,c},{c,d,e}}的长度是2。

六、