图论
基础
是什么
是数学的一个分支，叫几何拓扑学;
以图为研究对象;
由若干给定的点以及连接两点的线所构成的图形,这种图形通常用来描述某些事物之间的某种特定的关系;用点代表事物,用两点之间的连线表示相应的两个事物间具有的关系;
图=二元组(顶点集V,边集E).
术语
阶: 顶点个数(V);
无向图与有向图: 边(u,v)与弧<u,v>,入边与出边;
邻接: 两个顶点的邻接与非邻接;
度: 入度与出度;
奇点与偶点: 无向图中顶点度的奇偶性;
自环: 若一天边的两个顶点为同一顶点.
路径: (字面意义)
回路: 环(起点终点重合)
简单图: 没有环,没有多重边
连通: 从顶点x到顶点y有路径相连
连通图: 无向图的任意两个顶点都是连通的
强连通图: 有向图的任意两个顶点都有互相到达的路径*(不管方向与边)*
带权图: 权的含义
最短路: 从x到y具有的最小长度(长度包含路径上的所有边权之和)
二分图: 一个图的顶点集可以划分为两个非空子集.
满足每一条边都有一个顶点在x中,而另一个顶点在y中
图形分类
1.完全图
-
每一对顶点间都有边相连.
-
总变数为n*(n-1)/2;n=顶点数
2.稀疏图与稠密图
- 稠密图,接近于完全图
- 稀疏图,有很多点,但是没有几条边
-
子图
- 取出若干顶点和边构成的新图
-
补图
- 图中所有的顶点和所有能使该图成为完全图的添加边 所组成的图
-
逆图
- 把一个有向图的每条边都反向得到的有向图
问题类型
① 欧拉回路问题(一笔画);
有0个或2个奇点就可以一笔画;
0个奇点起点终点重合;
2个奇点能画完,但起点终点不重合; 否则不行.
应用
很多题目可以转化为一张图来做.
存储结构
① 邻接矩阵
定义A[n][n]
A[i][j]用来表示两个顶点之间的权数(长度).
同时记录权值
适用于稠密图.
② 边集数组
开二维数组.
同时记录起点,中点与权值(A[n][3])
适用于稀疏图.
③ 邻接表
开结构体与用结构体存储的vector.
同时记录起点,中点,权数与指针.
适用于稀疏图.
④ 链式向前星
这是一种特殊的边集数组,在边集数组的基础上将每一条边按照起点从小到大排序(,如果起点相同就按终点).
同时记录
