数据结构相关知识（图）

1.关于一条边（弧）的表示
1）用图形
2）用符号
(v1,v2)：无向图
<v1,v2>：有向图
3）用语言

2.图的分类：
1）边是干干净净的，什么也没有：无向图
2）边加个方向：有向图
3）边加个权重：网络

3.顶点的度：依附于顶点vi的边的数目称为顶点vi的度，记为TD(vi)，有向图中还分为出度（以顶点为起点的边的数目，记为OD(vi)）和入度（以顶点为终点的边的数目，记为ID(vi)）

4.完全图：边的数目达到最大的图称为完全图
稠密图：边的数目达到或接近最大的图称为稠密图
否则，称为稀疏图

5.顶点序列中顶点不重复出现的路径就称为简单路径（顶点序列其实就组成了一个路径）

6.不带权的图的路径长度指路径上所经过的边的数目；
带权图的路径长度是指路径上经过的边的权值之和

7.关于连通
1）无向图的连通：
无向图中顶点vi和vj有路径，则称vi和vj是连通的。若无向图中任意两个顶点都连通，则称该无向图是连通的
2）有向图的连通：
有向图中顶点和顶点之间的连通的定义和1）相同，如果有向图中所有顶点都连通，那称这个有向图是强连通的

1）连通分量：无向图中的极大连通子图
2）强连通分量：有向图中的极大强连通子图

9.生成树：包含连通图G的所有n个顶点，且仅包含其n-1条边的极小连通子图称为G的一个生成树

10.用邻接矩阵存储一个图：
用两个数组存储一个图
1）第一个数组是一个一维数组，用来存储所有的顶点
2）第二个数组是一个二维数组，用来存储各个顶点之间的边的信息，如下：