【图论】图论算法（一）——概念与无向图的邻接矩阵

基本概念

又进入了繁杂的概念之中……

概念

图是一种数据结构，表现对象集合及其间关系的集合。
图的对象称为结点或顶点，“关系”表示顶点与顶点之间的关系，称为边。
举个例子：

以上就是一个普通的无向图。

分类

图可以分为四类，用来处理不同类型的问题。

名称	特征
无向图	边没有方向的图
有向图	边有方向的图
加权无向图	边有权（值）但没有方向的图
加权有向图	边有权（值）但有方向的图

术语

顶点集合为V$V$，边集合为E$E$的图记作G=(V,E)$G=(V,E)$。在G=(V,E)$G=(V,E)$中，顶点数为|V|$|V|$，边数为|E|$|E|$。
连接两个顶点u$u$,v$v$记作e=(u,v)$e=(u,v)$。在无向图中，(u,v)$(u,v)$、(v,u)$(v,u)$代表同一条边；在有向图中，(u,v)$(u,v)$的权记作w(u,v)$w(u,v)$。
如果无向图中存在(u,v)$(u,v)$，我们就称顶点u$u$和v$v$相邻；相邻顶点的序列v0,v1,...,vk$v_0,v_1,...,v_k$(对于所有i=0,1,...,k$i=0,1,...,k$存在边(vi−1,vi)$(v_i-1,v_i)$称为路径；起点和终点相同的路径称为环。
与顶点u$u$相连的边数称为顶点u$u$的度。在有向图中，以顶点u$u$为终点的边数称为顶点u$u$的入度，以顶点u$u$为起点的边数称为顶点u$u$的出度。

记住了这些繁杂的基本概念后，接下来我们来学习如何存储图。

存储

存储图，可使用邻接矩阵和邻接表。

（一）邻接矩阵

邻接矩阵作为最简单、最易实现、最简洁的存储图的方法，极易令人理解。
顾名思义，邻接矩阵就是使用二维数组来实现存储图的。数组的下标表示各个顶点的编号，所以，我们可以将数组下标为(u,v)$(u,v)$的元素赋值为真，就可以表示从顶点u到顶点v$v$有边。
代码实现如下（我没有调试hhh）

bool a[M+5][M+5];//a是邻接矩阵存储表，只需bool数组即可，原因前面讲过
int n,m;//n记录顶点数，m记录边数
...
scanf("%d%d",&n);
for(int i=1;i<=m;i++)
{
    int u,v;
    scanf("%d %d",&u,&v);
    a[u][v]=1;
    a[v][u]=1;//这是无向图邻接矩阵存储，若是有向图，只需把这句话删掉
}

其实以上代码只是存储无向图的，但是我们只需稍稍对代码做一点变形，就可以实现对有向图、加权无向图、加权有向图的存储。
【未完待续】
补博客计划：图论系列文章：
1. 【未完】【板子图论】图论算法（二）——有向图的邻接矩阵与邻接表
2. 【未完】【板子图论】图论算法（三）——最短路径：Bellman-Ford算法与SPFA算法
3. 【未完】【板子图论】图论算法（四）——最短路径：Dijkstra算法与优先队列优化Dijkstra算法
4. 【未完】【板子图论】图论算法（五）——最短路径：Floyd-Warshall算法
5. 【未完】【板子图论】图论算法（六）——并查集
6. 【未完】【板子图论】图论算法（七）——最小生成树：Prim算法
7. 【未完】【板子图论】图论算法（八）——最小生成树：Kruskal算法