Floyd 算法（求多源汇最短路）
题目链接：97. 小明逛公园
题目描述：
小明喜欢去公园散步，公园内布置了许多的景点，相互之间通过小路连接，小明希望在观看景点的同时，能够节省体力，走最短的路径。
给定一个公园景点图，图中有 N 个景点（编号为 1 到 N），以及 M 条双向道路连接着这些景点。每条道路上行走的距离都是已知的。
小明有 Q 个观景计划，每个计划都有一个起点 start 和一个终点 end，表示他想从景点 start 前往景点 end。由于小明希望节省体力，他想知道每个观景计划中从起点到终点的最短路径长度。 请你帮助小明计算出每个观景计划的最短路径长度。
算法思想：
使用三重for循环，遍历从1~n节点，grip二维数组含义是表示点i和j间的距离，将其初始化为INT_MAX，对角线初始化为0。使用grip[i][j] = min(grip[i][j],grip[i][k]+grip[k][j])来判断最短路径。
代码：
#include<iostream>
#include<vector>
#include<climits>
using namespace std;
void floyd(vector<vector<int>>& graphs)
{
int n = graphs.size() - 1;
for(int k = 1; k <= n; k++)
for(int i = 1; i <= n; i++)
for(int j = 1; j <= n; j++)
if(graphs[i][k] != INT_MAX && graphs[k][j] != INT_MAX)
graphs[i][j] = min(graphs[i][j],graphs[i][k] + graphs[k][j]);
}
int main()
{
int n,m;
cin >> n >> m;
vector<vector<int>> graphs(n+1,vector<int>(n+1,INT_MAX));
for(int i = 1; i <= n; i++) graphs[i][i] = 0;
for(int i = 0; i < m; i++)
{
int u,v,w;
cin >> u >> v >> w;
graphs[u][v] = min(graphs[u][v],w);
graphs[v][u] = min(graphs[v][u],w);
}
floyd(graphs);
int q;
cin >> q;
while(q--)
{
int start,end;
cin >> start >> end;
if(graphs[start][end] == INT_MAX) cout << -1 << endl;
else cout << graphs[start][end] << endl;
}
return 0;
}A*算法
题目链接：127. 骑士的攻击
题目描述：
在象棋中，马和象的移动规则分别是“马走日”和“象走田”。现给定骑士的起始坐标和目标坐标，要求根据骑士的移动规则，计算从起点到达目标点所需的最短步数。
棋盘大小 1000 x 1000（棋盘的 x 和 y 坐标均在 [1, 1000] 区间内，包含边界）
算法思想：
1、该算法是对宽搜算法的优化，能保证有方向地去搜索点。在宽搜基础上增添了权重概念。
2、如何保证有方向搜索--对每一个点设置一个权重f，f=g+h，g表示起点达到目前遍历节点的距离，h表示目前遍历的节点到达终点的距离。距离计算公式如下：
- 曼哈顿距离，计算方式： d = abs(x1-x2)+abs(y1-y2)
- 欧氏距离（常用，不会超时） ，计算方式：d = (x1-x2)^2 + (y1-y2)^2
- 切比雪夫距离，计算方式：d = max(abs(x1 - x2), abs(y1 - y2))
3、每次使用具有最小权重的点来更新节点位置--->使用优先级队列保存
代码：
#include<iostream>
#include<vector>
#include<queue>
#include<algorithm>
using namespace std;
int b1,b2;
int dx[8] = {-1,-1,1,1,2,2,-2,-2};
int dy[8] = {2,-2,2,-2,-1,1,-1,1};
typedef struct Knight
{
int a1,a2;
int f,g,h;
bool operator < (const struct Knight& k) const
{
return k.f < f;
}
}Knight;
int function(const Knight& knt)
{
return (knt.a1 - b1)*(knt.a1 - b1) + (knt.a2 - b2)*(knt.a2 - b2);
}
void Astar(vector<vector<int>>& step, const Knight& knt, priority_queue<Knight>& pq)
{
Knight cur,next;
while(!pq.empty())
{
cur = pq.top(),pq.pop();
if(cur.a1 == b1 && cur.a2 == b2) break;
for(int i = 0; i < 8; i++)
{
next.a1 = cur.a1 + dx[i];
next.a2 = cur.a2 + dy[i];
if(next.a1 < 1 || next.a1 > 1000 || next.a2 < 1 || next.a2 > 1000) continue;
if(!step[next.a1][next.a2])
{
step[next.a1][next.a2] = step[cur.a1][cur.a2] + 1;
next.g = cur.g + 5;
next.h = function(next);
next.f = next.g + next.h;
pq.push(next);
}
}
}
}
int main()
{
int a1,a2,n;
cin >> n;
while(n--)
{
priority_queue<Knight> pq;
vector<vector<int>> step(1010,vector<int>(1010));
cin >> a1 >> a2 >> b1 >> b2;
Knight knt;
knt.a1 = a1;
knt.a2 = a2;
knt.g = 0;
knt.h = function(knt);
knt.f = knt.g + knt.h;
pq.push(knt);
Astar(step,knt,pq);
cout << step[b1][b2] << endl;
}
return 0;
}图论总结
深搜广搜
- 搜索方式：深搜是可一个方向搜，不到黄河不回头。 广搜是围绕这起点一圈一圈的去搜。
- dfs有两种写法：1）处理当前节点 2）处理下一个节点
- 一般是需要计算路径的问题 需要回溯，如果只是染色问题（岛屿问题系列） 就不需要回溯。 （注意：以上说的是不需要回溯，不是没有回溯，只要有递归就会有回溯，只是我们是否需要用到回溯这个过程）
并查集
- 为什么要用并查集，怎么不用个二维数据，或者set、map之类的。
- 并查集能解决那些问题，哪些场景会用到并查集
- 并查集原理以及代码实现
- 并查集写法的常见误区
- 带大家去模拟一遍并查集的过程
- 路径压缩的过程
- 时间复杂度分析--路径压缩后的并查集时间复杂度在O(logn)与O(1)之间，且随着查询或者合并操作的增加，时间复杂度会越来越趋于O(1)。在第一次查询的时候，相当于是n叉树上从叶子节点到根节点的查询过程，时间复杂度是logn，但路径压缩后，后面的查询操作都是O(1)，而 join 函数 和 isSame函数 里涉及的查询操作也是一样的过程
最小生成树
1、prim 算法是维护节点的集合，而 Kruskal 是维护边的集合。
2、prim 算法 时间复杂度为 O(n^2)，其中 n 为节点数量，它的运行效率和图中边树无关，适用稠密图。Kruskal算法 时间复杂度 为 O(mlogm)，其中m为边的数量，适用稀疏图。
3、prim算法三部曲：
- 选距离生成树最近节点
- 最近节点加入生成树
- 更新非生成树节点到生成树的距离（即更新minDist数组）
4、kruscal的主要思路：
- 边的权值排序，因为要优先选最小的边加入到生成树里
- 遍历排序后的边：
- 如果边首尾的两个节点在同一个集合，说明如果连上这条边图中会出现环
- 如果边首尾的两个节点不在同一个集合，加入到最小生成树，并把两个节点加入同一个集合
拓扑排序
- 给出一个 有向图，把这个有向图转成线性的排序 就叫拓扑排序。
两步拓扑排序的过程，代码就容易写了：
1）找到入度为0 的节点，加入结果集 2）将该节点从图中移除
最短路算法
单源汇最短路无负权边
- dijkstra朴素版
- dijkstra堆优化版
单源汇最短路有负权边无负权回路
- Bellman_ford
- Bellman_ford 队列优化算法（又名SPFA）
单源汇最短路有负权回路
- bellman_ford 算法判断负权回路
- bellman_ford之单源有限最短路
多源汇最短路
- Floyd 算法精讲
启发式搜索
- A*算法
