多源最短路（在曼哈顿图中）（无例题）（使用BFS，队列）：
操作的地图要有两个特点：既可以表示结果中所要的最短距离，又能记录这个点是否走过，那就全部memset为一个特殊的数-1（这里一定要专门设计一个结果图，不能只用最初的图，让最初的图承担三个责任，它哪里做的到啊（表示举例，判重，记录最初信息）（非要做的话，你可以想象，如果发现一个点可以是起点，那就改变其值为0，这个0要如何与其他没去过的点的0区分呢，如果另开一个数组那就可以区分了，起点处是0，没去过的地方是-1）），这就是个特殊的判重技巧：另开一个数组。
本题代码有个bug，不知道为什么输出结果有误，以后改过来。
题目：
code：
View Code
dijkstra算法：
问题：给出一个有向图，请问图中某一个点（这个点记作源点）到其余各点的最短距离是多少？
思路：（基于贪心算法）
1.将所有点到源点的距离初始化为无穷大
2.找到图中目前为止距离源最近的点
3.更新这个点的所有邻点的距离（松弛操作）
4.反复2，3操作直到遍历所有点为止
时间复杂度：O(n^2+m)
缺点：不能找出带有负边权的图，不能解决带有负环的图
注：vector是一个什么样的数据结构呢？vector是一个动态数组，像vector <int>a;这样就已经创建了一个整型数组。
题目:洛谷P3371
#include <bits/stdc++.h>
using namespace std;
struct edge{int v,w;};
int n,m,s,visit[10005],d[10005];
vector<edge>ed[10005];
#define inf 2147483647
void dijkstra(){
for(int i=1;i<n;i++){
int u=0;
for(int j=1;j<=n;j++)
if(d[j]<d[u] && visit[j]==0)u=j;
visit[u]=1;
for(edge e:ed[u]){
int v=e.v,w=e.w;
if(d[v]>d[u]+w)d[v]=d[u]+w;
}
}
}
int main(){
cin>>n>>m>>s;
for(int i=0;i<=n;i++)d[i]=inf;
d[s]=0;
int u,v,w;
for(int i=1;i<=m;i++){
cin>>u>>v>>w;
ed[u].push_back({v,w});
}
dijkstra();
for(int i=1;i<=n;i++)cout<<d[i]<<' ';
return 0;
}
dijkstra可以用堆来优化，得到heap-dijkstra算法
学会了dijkstra算法的堆优化，其实就是用一个小根堆来维护队列，将距离的相反数储存起来，这样堆顶的元素距离就最小（相反数最大）。
随后遍历每个点，已经遍历过的就打上visit标记不再遍历。题目：洛谷P4779.代码：
View Code
解析错误RE（runtime error）：
1.数组开的小了，但题目数据规模大于数组的大小，所以根本给不出结果
2.数组开的太大了，系统根本给不出这么大的空间
3.除数是0
bellman-ford算法：
问题：给出从一个点到其他点的最短距离，存在权值为负的边。
思路：
1.进行n轮判断
2.每轮判断中，对每条边都进行更新
3.如果某一轮没有再更新，那就停止判断
时间复杂度：一共n轮判断，每轮m条边，所以时间复杂度O(nm)
优点：可以判断负环
名词解释：什么是负环？
图中有一条路经过的边的权值之和是负数。这样一个图没有最短路，因为每走一遍这条路，权值都会变小。
如何用bellman-ford判断负环？
答：bellman-ford算法通过迭代算最短路径，每轮至少更新一个结点，最多更新n-1个结点，如果第n轮时发现仍有可以被更新的结点，那么存在负环。
题目：P3385
代码：
View Code
注：这个代码没过，而且不知道为啥过不去
背诵一个数字：2的32次方-1是21 47 48 36 47
生成树：
在一个连通图中，如果一个连通子图用n-1条边连接了全部N个点，这个连通子图就可以被称为生成树。
在一个带权图中，各边权值最小的生成树就是最小生成树。（MST,minimum spanning tree）
题目：洛谷P3366
#include <bits/stdc++.h>
using namespace std;
int n,m,ans,d[5005],visit[5005],cnt;
struct edge{int v,w;};
vector<edge>ed[5005];
const int inf=2147483647;
int prim(){
for(int i=0;i<=n;i++)d[i]=inf;
d[1]=0;
for(int i=1;i<=n;i++){
int u=0;
for(int j=1;j<=n;j++){//找出最近的点
if(visit[j]==0 && d[j]<d[u])u=j;
}
visit[u]=1;//标记出圈
ans+=d[u];
if(d[u]!=inf)cnt++;//有一个点被画出圈外
for(edge e:ed[u]){
int v=e.v,w=e.w;
if(d[v]>w)d[v]=w;
}
}
return cnt==n;
}
int main(){
cin>>n>>m;
int a,b,c;
for(int i=1;i<=m;i++){
cin>>a>>b>>c;
ed[a].push_back({b,c});
ed[b].push_back({a,c});
}
if(prim())cout<<ans;
else cout<<"orz";
return 0;
}
寻找方法：PRIM算法，思想贪心。
bellman-ford算法优化算法： spfa(shortest path faster algorithm)(戏称shortest path fake algorithm)
考虑到在bellman-ford算法中每轮的判断其实不用考虑每一条边，只用考虑那些可能更新的边，所以开数组visit和队列q,visit用来标记点是否在队列内，相当于给队列加个扩展的小功能。在队列中进行大家习惯的更新操作。加一个cnt数组记录边数（某一条路径上经过了多少边）。
题目：P3385
代码：
View Code
注：还是过不去，不知道为啥。
全源最短路算法（DP算法）：（思想：动态规划，插点法）
1.遍历每个点作为插点
2.某个点作为插点时，更新从i到j的距离
图的储存方法：邻接矩阵法
优点：可以解决负权和负环问题。
最小环问题，使用floyd算法。P6175
View Code
思路：插值，假设图中序号最大的点序号是k,k的邻居是i,j。看看i,k,j是不是最短路，不是的话就考虑下一个K。在此过程中用floyd算法不断更新i,j之间的距离备用。
模板：
View Code
最小生成树：
稠密图用prim，稀疏图用kruskal。
题目：洛谷P3366.
思想:运用并查集与贪心算法求最小生成树
步骤：
1.初始化并查集，将n个点放入n个独立集合。
2.将每条边按照边权从小到大排序。
3.枚举每条边，如果边上的两个点不在同一个集合，那就合并起来并且加入最小生成树；如果在同一集合，那就跳过。
4.重复步骤3直到选取了n-1条边。如果不是连通图的话就选不了n-1条边。
View Code
复杂度：O(mlogm)（来自于排序sort）
这题过不了。。。。
lowest common ancestor最近公共祖先：
倍增算法：最经典的LCA算法。
预处理：
两个数组dep[u]结点u的深度，fa[u][i]结点u向上跳2的i层的祖先。
步骤:1.DFS求出两个数组，称为求ST表 2.在已经求好的ST表中求LCA，步骤有2，首先将u,v跳至同一层，其次将u和v跳至LCA的下一层
题目：洛谷P3379
View Code
最近公共组先tarjan（塔杨算法）算法：
使用并查集进行离线（全部输入）计算。
在线计算：一般输入一边计算。
View Code
树剖算法写LCA：
洛谷3379：
View Code
算法复杂度：dfs1:O(n) dfs2:O(n) lca:O(mlog(n))(这是因为最多log(n)个重链) 一共O(n+mlog(n))
fa:父节点
son:重儿子
sz:该结点子树的结点数目
top:结点所在重链的根结点。轻儿子的根节点是它自己
dep:结点的深度
重儿子：子结点中sz最大的那个
轻儿子：除了重儿子之外的都是轻儿子
重链：重儿子们集合起来的链
三种算法比较：
倍增算法：最经典
tarjan：最高效
树剖：另有他用
DAG：有向无环图
AOV:activity on vertex network,用顶点表示活动的网络
我们往往用AOV或者DAG来表示一个大工程中各个小工程的前后顺序，而拓扑排序就是在AOV或DAG中找到一个可以正确施工的流程。
拓扑排序步骤：
1.将入度为0的点放入栈中
2.弹栈，将入度为0的点周围的邻点做处理：使邻点的入度减一，如果领点入度为0则入栈
反复执行第二步直到栈空
1.邻接矩阵法
View Code
时间复杂度==空间复杂度==O(n^2)，建议用在点不多的稠密图中
2.边集数组
View Code
时间复杂度O(n*m),空间复杂度O(m)
3.邻接表
View Code
时间复杂度O(n+m),原因：每个点都要遍历，总体来看每条边都要遍历；空间复杂度：O(n+m)。时间复杂度大大降低，但可惜不能处理反向边。
4.链式邻接表
5.链式前向星
学不会，先看别的，等哪天要用的时候再回来补上
手敲了两遍三种存储方式就十点半了。。时间贵如油哦。
标签：图论,Code,int,复杂度,结点,算法,View From： https://www.cnblogs.com/-ark/p/16555825.html