图
1. 图的定义
1.1 各种图
图由顶点的有穷非空集合和顶点之间边的集合组成，记为G(V,E)，其中G表示图，V是G图中顶点的集合，E是G图中边的集合。
- 无向边：用无需偶对(Vi,Vj)表示
- 有向边：也称为弧，<Vi,Vj>表示，Vi为弧头（head）。主要顺序不能写错
- 无顶点到自身的边和重边的图称为简单图（无向图中任意顶点间都有边的简单图为完全简单图，n个顶点有n*(n-1)/2条边
- 有向完全图，n个顶点，n*(n-1)条边
- 带权（weight）的图成为网（network）
1.2 顶点与边
无向图中被边相连的顶点互为邻接点（adjacent），这条边依附（incident）与这两个顶点。
顶点的度数：略。图的边数为全部顶点度数和的一半
有向图分出度和入度。边数=出度和=入度和
路径
路径的长度
路径的首尾相接->回路/环（cycle）
- 顶点不重复的路径->简单路径
- 除首尾顶点外无重复顶点的回路->简单回路
1.3 连通图
无向图的的极大连通子图称为连通分量
- 子图
- 子图是连通的
- 连通子图含有极大顶点数
- 具有极大顶点数的连通子图包含依附于这些顶点的所有边
有向图双向连通->强连通
无向图中连通且n个顶点n-1条边叫生成树
有向图：有向树，若干颗有向树构成生成森林
2. 抽象数据类型
3. 存储结构
3.1 邻接矩阵
- 一维数组存储图中顶点信息
- 二位数组（邻接矩阵）存储边/弧的信息
- 求Vi的所有邻接点只需将矩阵的第i行元素扫描一遍，为1的为邻接点
- 无向图的邻接矩阵为对称阵
- 网的权值表示法
- 用权值代替1
- 无连接的为“无穷”
- 主对角线为0
代码实现
typedef char VertexType;
typedef int Endg Type;
#define MAXVEX 100
#define INFINITY 65535
typedf struct
{
VertexType vexs [MAXVEX];
EdgeType arc [MAXVEX] [MAXVEX];
int numVertexes, numEdges;
} MGraph;
邻接矩阵浪费空间，优化：邻接表
