笔记2：图基础
Social_Zhao · · 个人记录
笔记2：图基础
前言
- 最近在绵中WC学了图论，写此文来复习（顺便增加RP）
引入（一些摘自度娘的闲话）
图论〔Graph Theory〕是数学的一个分支。它以图为研究对象。图论中的图是由若干给定的点及连接两点的线所构成的图形，这种图形通常用来描述某些事物之间的某种特定关系，用点代表事物，用连接两点的线表示相应两个事物间具有这种关系。
图G=（V,E）是一个二元组（V,E）使得E⊆[V]的平方，所以E的元素是V的2-元子集。为了避免符号上的混淆，我们总是默认V∩B=Ø。集合V中的元素称为图G的定点（或节点、点），而集合E的元素称为边（或线）。通常，描绘一个图的方法是把定点画成一个小圆圈，如果相应的顶点之间有一条边，就用一条线连接这两个小圆圈，如何绘制这些小圆圈和连线时无关紧要的，重要的是要正确体现哪些顶点对之间有边，哪些顶点对之间没有边。
图论本身是应用数学的一部份，因此，历史上图论曾经被好多位数学家各自独立地建立过。关于图论的文字记载最早出现在欧拉1736年的论著中，他所考虑的原始问题有很强的实际背景。
众所周知，图论起源于一个非常经典的问题——柯尼斯堡（Konigsberg）问题。
1738年，瑞典数学家欧拉( Leornhard Euler)解决了柯尼斯堡问题。由此图论诞生。欧拉也成为图论的创始人。
1859年，英国数学家汉密尔顿发明了一种游戏：用一个规则的实心十二面体，它的20个顶点标出世界著名的20个城市，要求游戏者找一条沿着各边通过每个顶点刚好一次的闭回路，即“绕行世界”。用图论的语言来说，游戏的目的是在十二面体的图中找出一个生成圈。这个生成圈后来被称为汉密尔顿回路。这个问题后来就叫做汉密尔顿问题。由于运筹学、计算机科学和编码理论中的很多问题都可以化为汉密尔顿问题，从而引起广泛的注意和研究。
正题
先进行一段瞎扯：
- 经过度娘的介绍，我发现：图论真是个很麻烦的东西。
- 所以下面写一些我自己对图论的看法（比度娘简单得多）
- 1、图其实就是一些点之间连着一些边。
- 2、图论就是研究图的。
- 3、然后就没了
- 当然图论有许多分支（真是毒瘤啊）
重回正题：
所以我们把目光放回OI中。现在问题大了。
首先看：
图的基本概念（瞎扯淡）：
- 顶点：就是图上的定点，又称结点、点（这谁不懂啊）
- 边：点之间的连线。
- 有/无向图：边有规定方向的图叫有向图，边无规定方向的叫无向图。有向图的边叫有向边，无向图的边叫无向边。
- 边权：每条边对应的值（包括长度、花费等）。
- 重(chóng)边：两点之间有多条边相连。
- 自环：一个点自己连自己。
- 见下图：（画图板，丑，勿喷）
- 还有（图上无法标示）：
- 度：无向图中连接某个点的边数。
- 出（入）度：有向图中由此点发出（到达此点）的边数。
- 稠密图：边很多的图。
- 稀疏图：边很少的图。
其次，作为OI的一个分支，你想做这类题，就首先需要知道：“图”到底怎么存储？
见下方
图的存储
第一种存法：邻接矩阵（较简单）
前置知识：二维数组（如果你这都不知道，推荐你先别学图论）
邻接矩阵（Adjacency Matrix）是表示顶点之间相邻关系的矩阵。设G=(V,E)是一个图，其中V={v1,v2,…,vn}。G的邻接矩阵是一个具有下列性质的n阶方阵：
①对无向图而言，邻接矩阵一定是对称的，而且主对角线一定为零（在此仅讨论无向简单图），副对角线不一定为0，有向图则不一定如此。
②在无向图中，任一顶点i的度为第i列（或第i行）所有非零元素的个数，在有向图中顶点i的出度为第i行所有非零元素的个数，而入度为第i列所有非零元素的个数。
③用邻接矩阵法表示图共需要n^2个空间，由于无向图的邻接矩阵一定具有对称关系，所以扣除对角线为零外，仅需要存储上三角形或下三角形的数据即可，因此仅需要n（n-1）/2个空间。
- 用法：
- 如果两个点（a和b）之间有一条边，则将矩阵中的对应位置（a,b）赋值为1(不带权图)或边权(带权图)。
- 如果两点之间没有边，则将矩阵中对应位置设为0或∞(一个大于所有可能边权但不爆栈的数)。
- 补充：对于重边和自环：
- 邻接矩阵无法处理重边。自环大多无意义，所以忽略即可。
- 举个例子：
- 对于下面这个图（无向图【带权】）：
-
就可以这样表示：
-
{0,1,2}
-
{1,0,3}
-
{2,3,0}
-
邻接矩阵有它的优缺点：
-
优点：用邻接矩阵表示图，很容易确定图中任意两个顶点是否有边相连。并且在稠密图中效率较高
-
缺点：浪费空间
因此，我们就有了第二种存法：邻接链表（又称链式前向星）（较为复杂）
前置知识：静态模拟链表
- 首先我们需要一个结构体和一个数组，以及一个单独的变量：
struct Edge {
int to,next,dis
} edge[maxm];int head[maxn],k=1;-
to是这条边到达的点，next是下一条边，dis是边权;head数组存储每个点连接的最后一条边的下标，k是边数。
-
然后我们需要执行下面的函数来向结构体中添加一条边：
-
void add(int from,int to,int dis) { edge[k].to=to; edge[k].dis=dis; edge[k].next=head[from]; head[from]=k++; } -
解释：首先存下这条边到达的点和权，将这条边的下一条边设为目前起点最后一条边的下标，在更新起点最后一条边为此边（很绕，看不懂可以咨询别人或者背下来）
-
注意：
-
有向边只需执行一次本操作
-
存储无向边时，直接将此边从起点到终点建一次，再从终点到起点建一次。
-
此方法也有优点和缺点：
-
优点：节约空间，实用性强。
-
缺点：十分难理解，难写。
图的遍历：
- 深度优先遍历（dfs）：一条路走到底，碰壁就返回（就和深搜差不多）
- 广度优先遍历（bfs）：不常用，先把一个点连接的所有点走到，在对下一个点做同样的操作（就和广搜差不多）
- 如果你连深搜和广搜都不会的话，还是建议先不要学图论。