各个图论的理论讲解（符代码）
*由于本蒟蒻太弱真的只是一名13岁的新初二学生，所以这里不提SPFA等高级算法，只是概括了：
- 克鲁斯卡尔
- prim
- Dijkstra 地杰斯塔拉（优先队列优化）
- Dijkstra 地杰斯塔拉（无优化）
- Floyd 弗洛伊德*
1. Kruskal 克鲁斯卡尔
（用于求最小生成树…）
这里先讲一下：最小生成树就是指一颗贯通整个图的树，并且可以从任意一个点到达任意一个点
这个本质就是找到最小生成树然后再求总和
（1）.如何寻找最小生成树：
只需找到一个“爸爸”点，然后再往上加，每次和“爸爸”家族连接即可。
程序中的 fa 数组就是用于记录它到底属于哪一个家族。（并且由于这个特性，Kruskal更适用于稀疏图…自己脑补吧…）
代码O(∩_∩)O哈哈~
劲量看懂再抄…
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
using namespace std;
const int maxn = 1e5+10;
struct node{
int u,v,w;
}e[2*maxn];
int fa[maxn]; // fa[i] 为顶点 i 所在集合对应的树中的根结点
int r[maxn];
int n,m; //点和边
void init() {//初始化
for(int i=0;i<=n;i++)
{
fa[i] = i;
r[i] = 0;
}
}
bool cmp(node a,node b){
return a.w<b.w;
}
int find(int x){
if(fa[x]==x)
return x;
else
return fa[x] = find(fa[x]);
}
void merge(int x,int y){
x = find(x);//x 和 y 都去找爸爸
y = find(y);
if(x!=y){
if(r[x]<r[y])//这里如果y的家族更大，那么大家都跟着它混
fa[x]=y;//纯属拼爹......
else{
fa[y] = x;
if(r[x]==r[y])
r[x]++;//反正y这个x走了，所以就加上呗~
}
}
}
void kruskal(){
int sumw = 0; //生成树的权值
int num = 0; //已选用边的数目
int u,v;
init();
for(int i=0; i<m; i++){
u = e[i].u;
v = e[i].v;
if( find(u)!=find(v) ){//开始和结尾的爹不同了
sumw += e[i].w;
num++;
merge(u,v);//看缘分分家...
}
if(num >= n-1)//终于分完了...
break;
}
printf("%d\n",sumw);
}
int main(){
int t;
int u,v,w;
while(~scanf("%d",&n) && n){
scanf("%d",&m);
for(int i=0; i<m ;i++){
scanf("%d%d%d",&u,&v,&w);
e[i].u = u;
e[i].v = v;
e[i].w = w;
}
sort(e,e+m,cmp);
kruskal();
}
return 0;
2.Prim//真**的累嗨没办法啊生活真苦…
这个也是求最小生成树的，还没吐的就再忍一忍吧…
这个的大概就是先找好最小生成树然后再一点一点的加上去
这个更适用于稠密图…
代码
尽量看懂再抄~~
#include <bits/stdc++.h>
using namespace std;
int n, q[1001][1001], minn[100001], ans;//minn表示不在最小生成树中的点与在最小生成树中的点相连的最小边权
bool f[100001];//不在最小生成树中的点f等于false，在就等于true
int main() {
memset(minn, INF, sizeof(minn));//初始化
minn[1] = 0;
scanf("%d", &n);
for(int i = 1; i <= n; i++) {
for(int j = 1; j <= n; j++) {
scanf("%d", &q[i][j]);//输入邻接矩阵
}//q[i][j]表示从i到j用多久
}
for(int i = 1; i <= n; i++) {
int k = 0;
for(int j = 1; j <= n; j++) {
if(!f[j] && minn[j] < minn[k]) { //寻找权值最短的边（且不能是已经在最小生成树中的点）
k = j;
}
}
f[k] = true;//把它加入最小生成树
for(int j = 1; j <= n; j++) {
if(!f[j] && q[k][j] < minn[j]) {
minn[j] = q[k][j];
}
}
}
for(int i = 1; i <= n; i++) {
ans += minn[i];//把所有在最小生成树中的点的权值加起来
}
printf("%d", ans);
return 0;
}
这个代码这段享受
3. Floyd
这个更短，只是时间复杂度有点大。n3
这个就跟最小生成树没关系了~~
#include<bits/stdc++.h>
int main() {
int e[10][10],k,i,j,n,m,t1,t2,t3;
int inf=99999999;
//读入n和m，n表示顶点个数，m表示边的条数
scanf("%d %d",&n,&m);
//初始化
for(i=1; i<=n; i++)
for(j=1; j<=n; j++)
if(i==j) e[i][j]=0;
else e[i][j]=inf;
//读入边
for(i=1; i<=m; i++) {
scanf("%d %d %d",&t1,&t2,&t3);
e[t1][t2]=t3;
}
//Floyd算法核心语句
for(k=1; k<=n; k++)
for(i=1; i<=n; i++)
for(j=1; j<=n; j++)
if(e[i][j]>e[i][k]+e[k][j] )//意思就是如果在两点之间在加上一个点的话，如果可以更短就加
e[i][j]=e[i][k]+e[k][j];
//输出最终的结果
for(i=1; i<=n; i++) {
for(j=1; j<=n; j++) {
printf("%10d",e[i][j]);
}
printf("\n");
}
return 0;
}
4.Dijkstra（警告：这个最**的烦人，心态不好的不要进入…）
Dijkstra就是求一个从1到i的最短路
给你们看一个视频
Dijkstra详解
最后再给各位DALAO们讲一下代码
#include <stdio.h>
#include <algorithm>
#include <cstring>
#include <cmath>
using namespace std;
const int inf=2147483647;
const int maxn=10000+10;
struct hh
{
int u,v,w,next;
}e[maxn];
int n,m,x,head[maxn],dis[maxn];
bool vis[maxn];//this is weather or not it has been visited
void dij()
{
int k;
memset(vis,0,sizeof(vis));
for(int i=1;i<=n;i++)dis[i]=inf;//dis means the dis[i] from 0 to i
dis[x]=0;//x means where it starts so that is defintly 0
for(int i=1;i<=n;i++)
{
k=-1;
for(int j=1;j<=n;j++)
if(!vis[j]&&(k==-1||dis[j]<dis[k]))k=j;//this is the part where you find the smallist
vis[k]=true;//been visited
for(int j=head[k];j!=-1;j=e[j].next)//always looking for the next
if(!vis[e[j].v]&&e[j].w+dis[k]<dis[e[j].v])dis[e[j].v]=e[j].w+dis[k];//if this hasn't been visited before and the total distance is smaller then just changing it
}
}
int main()
{
scanf("%d %d %d",&n,&m,&x);
for(int i=1;i<=m;i++)
{
scanf("%d%d%d",&e[i].u,&e[i].v,&e[i].w);//start end cost
e[i].next=head[e[i].u];//cheak out the picture 这个就是前面点
head[e[i].u]=i;//出发点
}
dij();
for(int i=1;i<=n;i++)
printf("%d",dis[i]);
return 0;
}
5.Dijkstra+堆优化（终极警告真烦人，别说我没警告你…）
在这里插入代码片#include<cstdio>
#include<iostream>
#include<algorithm>
#include<queue>
using namespace std;
const int INF = 2147483647;
const int maxn = 10000 + 10;
const int maxm = 500000 + 10;
int n, m, s;
int fir[maxn], nxt[maxm], to[maxm], val[maxm], cnt;
void add_edge(int u, int v, int w) //前向星加边
{
nxt[++cnt] = fir[u];
fir[u] = cnt;
to[cnt] = v;
val[cnt] = w;
}
struct Node
{
int d, id;
Node(){}
Node(int d, int id) : d(d), id(id){}
bool operator < (const Node& rhs) const
{
return d > rhs.d;//重载 < 方便堆
}
};
int dis[maxn], vis[maxn];
void Dijkstra(int s)
{
for(int i = 1; i <= n; i++) dis[i] = INF;
dis[s]=0;
priority_queue<Node> Q;
//here you can see that it is the same as the code from the top
//just that priority queue can just sort it from small to large
//so now it is a bit more faster
//if you are going to memorize Dijkstra then please remember this
Q.push(Node(0,s));
while(!Q.empty())
{
Node u = Q.top(); Q.pop();
if(vis[u.id]) continue; //若某个点已经被更新到最优,就不用再次更新其他点
vis[u.id] = 1;
for(int e = fir[u.id]; e; e = nxt[e])
{
int v = to[e], w = val[e];
if(u.d + w < dis[v])
{
dis[v] = u.d + w;
Q.push(Node(dis[v],v));
}
}
}
}
int main()
{
scanf("%d%d%d",&n ,&m ,&s);
for(int u, v, w, i=0; i < m; i++)
{
scanf("%d%d%d",&u ,&v ,&w);
add_edge(u, v, w);
}
Dijkstra(s);
for(int i = 1; i <= n; i++) printf("%d ", dis[i]);
return 0;
}
6.拓扑排序本蒟蒻目前还不认识拓扑排序，打字时候只能打tppx 并我不知道到底拼音是什么，只好把他叫成脱裤排序…O(∩_∩)O哈哈~
请求大家催更，要不然我都懒得写了，太**的累了o(￣▽￣)ｄ
祝贺大家NOIP,CSP-J,CSP-S,acm RP++!!!