图论基础理论

在我看来，想要掌握图的基础应用，仅需要三步走。

什么是图（基本概念）、图的构造（打地基）、图的遍历方式（应用的基础）

只要能OK的掌握这三步、就算图论入门了！！！

当然新手也不要恐惧啥的，新知识嘛，就是需要一个接受的过程。

学术上，是这么称图的： 

图由顶点（Vertex）集合和（Edge）集合组成，通常表示G(v,e)

当然，这太学术了(～﹃～)~zZ

换句话说，图，就是由顶点与边组成的。

顶点就是各个节点。边就是各个节点的关系or性质。

基本概念：

首先就是图的种类，毕竟人还分不同肤色呢，就更不用说图了。

图分无向图、有向图。

无向图，边之间没有方向。

有向图，边之间存在方向。

接下来，咱们讲讲度的概念。他在有向图与无向图中，分别有不同的含义。

在无向图中，只有统一的 “度”（因为边无方向）

度：与该节点有几条边相邻。

如图，节点1，有4条边与其相连。故度为4。

在有向图中，他分别是出度、入度与总度。

出度: 指向其他节点的边。

入度: 其他节点指向本节点的边。

总度: 出度+入度的总和。

如图，节点1：出度（3）、入度（1）、总度（3+1=4）

接下来就讲到，连通图与强连通图的概念。

连通图是 图中的概念。意思是每个节点之间，都能相互到达。

但是如果节点之间，无法相互抵达，就是非连通图。

如下所示，左侧每个节点之间，都能相互到达，为连通图，而右侧不是却不能。为非连通图。

强连通图同样也是每个节点之间，都能相互抵达，但是有个前提条件，必须按照边的方向。

如图左侧，直接形成了闭环。故为 强连通图。

而图的右侧，为非强连通图（举例：节点4 无法到达 节点3）

构造：

有三种构造方式。

拓扑储存，邻接矩阵、邻接表。

拓扑储存，虽然是Carl自创的名字，但我挺认同的(。・ω・。)

如图，一共有8个节点，如果，想要将这8个节点储存，需要8*2个单位。

如果存在二维数组中，大概需要建立一个二维数组储存。

但是这样的前提是，想要遍历所有内容非常麻烦。（用map储存，用的是同样的效果）

邻接矩阵

邻接矩阵，通过二维数组来储存。是从节点的角度来考虑的。有多大的节点，就分配，其平方大的数组。

如图grid[2][5]=6，代表节点2与节点5之间，有一条节点，权值为6；

在有向图中，grid[2][5]=6 表示为，节点2指向节点6；

在无向图中，若向表示2与5之间有节点。grid[2][5]=6、grid[5][2]=6。

这样联动着表示。

优点：可以迅速查询，两点直接是否有联通。

缺点：适用于稠密图，若果节点变很少，会造成空间极大的浪费。

邻接表

邻接表是通过，数组+链表来储存的。

优点：需要多少边，就申请多少节点。

缺点：若要查询两点之间，是否连通。无法很快查询到。

应用：

其实最后一部分，叫做图的遍历方式更好。

但为啥叫做应用呢，图的应用不就是图的遍历吗，通过各种遍历解决问题。

图的遍历方式大概分为两大类：

深度优先搜索（DFS），与广度优先搜索（BFS）

其实图的遍历方式与树的遍历方式大差不差。

主要还是需要借助实战。

从下一篇博客，就要开始实战喽。

注意⚠️⚠️⚠️，用Carl的话说，图论是非常庞大的知识体系，以上只是一小部分理论基础。

更多的，还是要考刷题积累。

接下来，我们要面对，深度优先搜索(dfs)、广度优先搜索(bfs)、并查集、拓扑排序、最小生成树系列、最短路径系列....热血沸腾吧！

---

借鉴博客：

1、图论理论基础

---