6.1 图的基本概念

图：图由顶点集和边集组成：G=(V,E),V是有限非空集合，E表示的是有穷的集合可以为空，所以图中的边可以为空，但是必须存在点。
有向图：有向图是每个边都带有方向的图。
无向图：每条边都是没有方向的图。
完全图：完全图是图中的任意两个节点之间都存在一个连线，一个节点与另外的n-1个节点之间都有连线，所以无线完全图一共是n(n-1)/2条边，而有向完全图是n(n-1)条边。
网：带有权值的图叫做网。
邻接：存在边或者弧连接的两个顶点叫做邻接。
关联（依附）：边/弧与顶点之间的关系。称之为边依附于这两个顶点vi和vj。
顶点的度：与该节点相关联的边的数目，在有向图中顶点的度是出度和入度的和。
有向树：一个顶点的入度为0，其余顶点的入度为1的有向图称之为有向树。
简单路径：除了第一个和最后一个顶点外，其余顶点不会重复出现的路径。
简单回路：除了第一个和最后一个顶点外，其余顶点不会重复出现的回路。
连通图（强连通图）:对于任何两个节点u和v之间的都存在从v到u的路径。无向图说是连通图，有向图说是强连通图。
权和网：将图上边或者弧的数字代表权，带有权的图称之为网。
子图：顶点和边的集合是图中的边和点的子集，那就是子图。
极大连通子图：该子图是G连通子图，将G的任何不在该子图的顶点加入，子图就不连通了。（就是这个子图中的顶点的数目已经达到了最大值，再加入新的节点就不联通了）。
无向图的极大连通子图称之为连通分量。

下面的这两个都是极大连通子图
有向图中的极大连通子图称之为强连通分量。这里的极大连通子图的概念是：该子图是强连通子图，再加入任何一个顶点就不联通了。
极小连通子图：该子图是连通子图，在该子树中删除一条边就不再是连通。（极小连通子图是无环的图，因为存在环的话，你删除一个环中的边，还是连通的）。
生成树：包含无向图中的所有顶点的极小连通子图。
生成森林：对于非连通图，由各个连通分量的生成树的集合。

6.2 图的存储及基本操作

图的存储必须要保证能够表示出顶点集和边集的信息。

多对多的逻辑关系

没有储存结构，但是可以使用二维数组来表示元素之间的关系。

链式存储结构，因为图是多对多，无法确定结点的指针域的个数。可以使用邻接表、十字链表、邻接多重表进行表示。

6.2.1 邻接矩阵表示法

用一维数组存储顶点的信息
用二维数组存储边的信息（顶点之间的邻接关系）

1
2
3

含有结点数为n的图的邻接矩阵是nxn的矩阵
A[i][j]=1   //表示的是点i和点j之间存在边。
A[i][j]=0   //表示的是点i和点j之间不存在边。

例子：

总结：

无向图的邻接矩阵一定是一个对称矩阵，斜对角线上全部是0，并且是唯一的。
完全图的邻接矩阵中，对角元素为0，其余为1。
对于无向图来说，顶点所在的第i行或者第i列上的非零或者非无穷的个数代表的是顶点的度。
对于有向图来说，顶点第i行的个数代表的是顶点的出度，顶点所在的第i列的个数代表的是顶点的入度。（行出列入）
邻接矩阵的优点：非常适合存储稠密图，用邻接矩阵存储图的有点是能够快速知道两个顶点是否连通并取到权值。缺点：如果顶点比较多，边比较少时，矩阵中存储了大量的0 成为系数矩阵，比较浪费空间，并且要求两个节点之间的路径不是很好求。（就是边比较多的情况）

6.2.2 邻接表表示法

邻接表的方法结合了顺序存储和链式存储的等优点，适合与存储稀疏图。

首先建立一个顶点的单链表，然后单链表中的各节点，连着一个边表。
邻接表中存在两种表，顶点表节点和边表节点。
顶点表的构成是顶点域和指向第一邻接的边的指针域（也就是指向的是边表）。
边表的构成是邻接点和指针域。

图的遍历

BFS（广度优先遍历）

广度优先遍历是一种由近及远的遍历方式，从距离最近的顶点开始访问，并一层层向外扩张。具体来说，从某个顶点出发，先遍历该顶点的所有邻接顶点，然后遍历下一个顶点的所有邻接顶点，以此类推，直至所有顶点访问完毕。  -----来源于hello 算法

1	广度优先遍历按层次进行遍历，一层层往外进行，相当于二叉树的层次遍历。

样例：

遍历的结果为：0,3,1,6,4,2,7,5,8

注：广度优先的顺序是不唯一的。广度优先遍历只要求按“由近及远”的顺序遍历，而多个相同距离的顶点的遍历顺序是允许被任意打乱的。以上图为例，顶点 1 , 3 的访问顺序可以交换、顶点 2 , 4 , 6 的访问顺序也可以任意交换。

采用邻接矩阵的存储方式对应的广度优先的时间复杂度O(v+e)
采用邻接矩阵的存储方式对应的广度优先的时间复杂度O(v*v)

广度优先生成树

对于一个图的邻接矩阵是唯一的，所以其广度优先生成树是唯一的。

对于一个图的邻接表是不唯一的，所以其广度优先生成树也是不唯一的。

DFS(深度优先遍历)

深度优先遍历是一种优先走到底、无路可走再回头的遍历方式。具体地，从某个顶点出发，访问当前顶点的某个邻接顶点，直到走到尽头时返回，再继续走到尽头并返回，以此类推，直至所有顶点遍历完成。   ----hello 算法

注：**DFS相当于树的先根遍历算法的实现**

样例：

遍历的结果为：0,3,1,2,5,4,6

对于定了邻接矩阵存储的深度优先遍历顺序是唯一的。

与广度优先遍历类似，深度优先遍历序列的顺序也不是唯一的。给定某顶点，先往哪个方向探索都可以，即邻接顶点的顺序可以任意打乱，都是深度优先遍历。

算法实现

采用的是定义调用的方式进行的，递归调用的次数是图的连通分量的个数。

时间复杂度和空间复杂度

时间复杂度：

当使用邻接矩阵表示图时，遍历图中的每一个顶点都要从头扫描该顶点所在的行(nxn)，时间复杂度是O(nxn)。
当用邻接表来表示的时候，虽然有2e个边表结点，但是只需要扫描e个结点即可，加上n个表头节点的访问，时间复杂度是O(n+e)。

深度优先生成树

深度优先成树

图的应用

生成树

所有顶点均连接在一起，但是不存在回路。（故不能少，也不能多）
包含图中的所有顶点
一个图可以有很多的生成树
生成树的点是n个，边数是n-1
生成树中的任意两个定之间的路径是唯一的

最小生成树问题

最小生成树是对网这种数据结构来说的，最小生成树是权值最小的生成树（不唯一，但是权值都是一样的）。

MST性质

MST算法的性质类似于典型的贪心算法

普利姆Prim算法（选点）

Prims算法同样是遵循MST性质的，选点：每次选一个点是v-u（所有点-已经加入生成树的点）到u（已经加入生成树的点）的集合中的连线的权值最小的那个点。

注：适用于稠密图（邻接矩阵也是的（主要是与点有关））

时间复杂度

因为选择的是点，所以时间复杂度是O（nxn）:因为每个顶点都是需要找其他的n-1个顶点去进行判断，所以是O（nxn）

克鲁斯卡尔Kruskal算法（选边）

这个算法一开始就将图的所有顶点加入到了生成树中去了，首先将边根据权值进行排序，每次选择权值最小的边，不能形成环路，最后所有的点是需要在同一个连通分量里的。

注：适用于稀疏图（邻接表也是的）

时间复杂度

因为选择的是有序的边，所以时间复杂度是O（ElogE)

最短路径问题

单源最短路径：即图中的任一顶点到其他各个顶点的之间的最短路径。（迪杰斯特拉算法）
求每对顶点之间的最短路径问题。（佛洛依德算法）

迪杰斯特拉算法

初始化：先找出从源点到各个终点的直达路径，使用权值表示，不能直达的记为无穷。
选择：从这些路径中选择一条长度最短的路径。
更新：然后对其余的路径进行调整。

迪杰斯特拉算法将顶点集合V分成两组：
S集合：已经求出最短路径的顶点集合
T=V-S：尚未确定最短路劲的顶点集合。
保证：
从原点v到集合S中的最短路径长度都不大于从v到集合T中的任何顶点的最短路径长度。
2.将未加入最短路径集合的集合T中的点依次地加入S集合中去。
每个顶点对应一个距离值：
S中的顶点：从v到此顶点的最短路径长度
T中顶点：从v到此顶点的只包括S中作为中间结点的最短路径。