图

概念的定义

图（Graph）是由顶点的有穷非空集合和顶点之间边的集合组成， 通常表示为：G(V,E)，其中，G表示一个图，V是图G中顶点的集合， E是图G中边的集合。

邻接矩阵与邻接链表的关系

联系

1. 邻接表中每个链表对应于邻接矩阵中的一行
2. 链表中结点个数等于一行中非零元素个数

区别

1. 对于任一确定的无向图,邻接矩阵是唯一的(行列号与顶点编号一致),但邻接表不唯一(链接次序与顶点编号无关)
2. 邻接矩阵的空间复杂度O(n^2),而邻接表的空间复杂度为O(n+e)

什么时候适合用邻接矩阵还是邻接表?

1. 邻接矩阵多用于稠密图
2. 邻接表多用于稀疏图

十字链图款

邻接多重表

DFS深度优先搜索

1. 一条路线走到底,然后检查是否每个结点都被访问过,如果都访问过,则后退一步.重复以上步骤.
2. 解题思路: 1.使用一个visited数组标记结点是否被访问过.然后借用递归或自己写的栈实现

BFS广度优先搜索

1. 适合非加权图的最短路径
2. 一层一层的遍历.遍历每一层结点
3. 解题思路: 1.使用一个循环队列,2再使用一个visited数组标记结点是否被访问过.3访问一个结点加入队列.直到队列为空和visited也都为1 则表示整个图访问完成

DFS&BFS比较

生成树

所有的顶点均由边连接在一起,但不存在回路的图

1. 一个有n个顶点连通图的生成树,有n-1条边
2. 生成树再加一条边必然形成回路.
3. 生成树任意两个顶点路径是唯一的
4. 一个图有多个生成树.

###　无向生成树

1. 深度优先生成树&广度优先生成树

最小生成树

1. 每个边都有权重,生成最小代价的树就是最小生成树.边的权重之和最小.

MST算法构造最小生成树

1. 首先创建一个非空子集顶点集合U,然后V-U中找到最小权重边进行连接.

Prim算法

1. 创建一个非空子集,初始时含一个顶点,然后找最小权重边连接.重复以上步骤.
2. 适合稠密图

Kruskal算法

1. 稀疏图
2. 贪心思想.
3. 选择权重最小的边进行连通.

狄克斯特拉算法(Dijkstra算法)求最短路径

1. 适合加权有向图.
2. 有负权边的有向图不适合.只能使用贝尔曼-福德算法

步骤

1. 找到最便宜的结点,即权重最小的边结点
2. 对于该结点的邻居,检查是否有前往它们的更短路径,如果有,就更新其开销
3. 重复这个过程,直到对图中的每一个结点都这样做了
4. 计算最终路径

Floyd算法

1. 初始时设置一个n阶方阵停令其对角线元素为0,若存在弧<vi,vj>则对应元素为权值,否则无穷大
2. 逐步试着在原直接路径中增加中间顶点,若加入中间顶点后路径变短则修改之.否则不变.所有顶点试探完毕,算法结束