图算法之个人整理总结.doc

陈江勇整理 2025-8-26
图算法实例

1. Dijkstra算法求最短路算法 2
2. 求所有点最短路的Dijkstra算法 3
3. 欧拉路径 4
4. 最大的流 8
5. 有向图的强连通分量和2-sat的判定问题 10
6. 求图中不含有割点（关结点）的块 18
7. 图的奇环的判断,是否为二分图的判断 19
8. 二分图的匹配 20
9. prim算法求最小生成树 20
10. 给有有向图最少加边使图中没有桥 21
11. 套汇问题 24
12. 差分系统 24
13. 二分图加权匹配--KM算法 32
14. floyed算法 36

1. Dijkstra算法求最短路算法
用堆来实现
输入输出说明：
N , M 然后
M 条边即相应的边的长
2 2
1 2 5
2 1 4
#include<iostream>
#include<algorithm>
#include<vector>
#include<limits>
using namespace std;
#define INF INT_MAX
#define maxn 30000
struct NODE
{
int v;
int weight;
};
int wt[maxn],heap[maxn*2],r,N,M; //wt[i]保存从开始节点到节点i的最短路，heap的大小不确定
bool visit[maxn]; //一般开到节点数目两到三倍。这是因为堆中会有相同的节点，但他们的权重
vector<NODE>G[maxn]; //不一样
int cmp(int a,int b)
{
return wt[a]>wt[b];
}
int dijkstra(int s,int t)
{
int i,u;
for(i=0;i<N;i++)
{
wt[i]=INF;
}
r=0;
heap[r]=s;
wt[s]=0;
r++;
memset(visit,0,sizeof(visit));
while(r>=0)
{
u=heap[0];
pop_heap(heap,heap+r,cmp);
r--;
if(visit[u])
{
continue;
}
visit[u]=1;
if(u==t)
{
return wt[t];
}
for(i=0;i<G[u].size();i++)
{
if(wt[u]+G[u][i].weight<wt[G[u][i].v]) //发现更好的状态但是堆可能已经存在
{ //编号为v的节点状态。
wt[G[u][i].v]=wt[u]+G[u][i].weight;
heap[r]=G[u][i].v;
r++;
push_heap(heap,heap+r,cmp);
}
}
}
return -1;
}
int main()
{
NODE temp;
int i,A,B,c;
scanf("%d%d",&N,&M);
for(i=0;i<M;i++)
{
scanf("%d%d%d",&A,&B,&c);
temp.v=A-1;
temp.weight=c;
G[B-1].push_back(temp);
}
printf("%d\n",dijkstra(N-1,0));
return 1;
}
2. 求所有点最短路的Dijkstra算法
void dijkstra(int s)
{
int i,u,j,min;
memset(visit,0,sizeof(visit));
for(i=1;i<=F;i++)
{
if(G[s][i]) //存在着边
{
dist[i]=G[s][i];
}
else
{
dist[i]=INT_MAX;
}
}
dist[s]=0;
visit[s]=1;
for(i=1;i<=F;i++)
{
u=-1;
min=INT_MAX;
for(j=1;j<=F;j++)
{
if(dist[j]<min&&!visit[j])
{
min=dist[j];
u=j;
}
}
if(u==-1)
{
break;
}
visit[u]=1;
for(j=1;j<=F;j++)
{
if(G[u][j]&&!visit[j]&&dist[j]>dist[u]+G[u][j])
{
dist[j]=dist[u]+G[u][j];
}
}
}
}
3. 欧拉路径
判断欧拉路径时要注意有向图无图的区别。
以下是链表形式
struct NODE
{
int v,id;
NODE *next;
};
void path(int u,int id)
{
link p;
int vv,dd;
while(adj[u])
{
p=adj[u];
vv=p->v;
dd=p->id;
adj[u]=p->next;
delete p;
path(vv,dd);
}
ans[top++]=id;
}
注意这边ans是反序存结果。

Sample Input

2
6
aloha
arachnid
dog
gopher
rat
tiger
3
oak
maple
elm

Sample Output

aloha.arachnid.dog.gopher.rat.tiger
***

#include<string>
#include<iostream>
#include<algorithm>
using namespace std;
#define maxn 1024
bool cmp(string a,string b)
{
return a>b;
}
struct NODE
{
int v,id;
NODE *next;
};
typedef NODE *link;
int ans[maxn],top,in[32],out[32],start;
string save[maxn];
link adj[32];
void insert(int u,int v,int id)
{
link p=new NODE;
p->v=v;
p->id=id;
p->next=adj[u];
adj[u]=p;
}
void path(int u,int id)
{
link p;
int vv,dd;
while(adj[u])
{
p=adj[u];
vv=p->v;
dd=p->id;
adj[u]=p->next;
delete p;
path(vv,dd);
}
ans[top++]=id;
}
int check()
{
int i,e1,e2,cnt;
e1=e2=cnt=0;
for(i=0;i<26;i++)
{
if(out[i]-in[i]==1)
{
start=i;
e1++;
cnt++;
}
else if(in[i]-out[i]==1)
{
e2++;
cnt++;
}
else if(in[i]!=out[i])
{
return 0;
}
}
if(!(cnt==2||cnt==0))
{
return 0;
}
if(cnt==2&&e1!=1)
{
return 0;
}
if(cnt==0)
{
for(i=0;i<26;i++)
{
if(out[i])
{
start=i;
break;
}
}
}
return 1;
}
int main()
{
int T,N,i,a,b;
cin>>T;
while(T--)
{
cin>>N;
for(i=0;i<N;i++)
{
cin>>save[i];
}
sort(save,save+N,cmp);
memset(adj,0,sizeof(adj));
memset(in,0,sizeof(in));
memset(out,0,sizeof(out));
for(i=0;i<N;i++)
{
a=save[i][0]-'a';
b=save[i][save[i].length()-1]-'a';
insert(a,b,i);
out[a]++;
in[b]++;
}
top=0;
if(!check())
{
cout<<"***\n";
continue;
}
else
{
path(start,-1);
}
if(top!=N+1)
{
cout<<"***\n";
}
else
{
for(i=top-2;i>0;i--)
{
cout<<save[ans[i]]<<'.';
}
cout<<save[ans[0]]<<endl;
}
}
return 1;
}

4. 最大的流
1． BFS找找增广路
int G[402][402],N,D,F,start,end,Q[402],save[402]; //Q是村节点的队列
int pre[402]; //村前一个节点的编号 ，邻接矩阵表示
int BFS(int s,int t)
{
int i,f,r,v;
memset(pre,-1,sizeof(pre));
f=r=0;
Q[r++]=s;
while(f<r)
{
v=Q[f++];
for(i=1;i<=end;i++)
{
if(G[v][i]&&pre[i]==-1)
{
pre[i]=v;
Q[r++]=i;
if(i==t)
{
return 1;
}
}
}
}
return 0;
}
int max_flow(int s,int t)
{
int p,ans=0,d;
while(BFS(s,t))
{
d=INF;
for(p=t;p!=s;p=pre[p])
{
if(G[pre[p]][p]<d)
{
d=G[pre[p]][p];
}
}
ans+=d;
for(p=t;p!=s;p=pre[p])
{
G[pre[p]][p]-=d;
G[p][pre[p]]+=d;
}
}
return ans;
}
5. 有向图的强连通分量和2-sat的判定问题
#include<iostream>
#include<vector>
using namespace std;
#define INF 102400
#define maxn 1024*2
int low[maxn*2],cnt,cnt1,stack[maxn*2],top,sc[maxn*2],N,M,flag;
int visit[maxn*2]={0};
vector<int>G[maxn*2];
void DFS(int u)
{
int i,len,min,v;
visit[u]=flag;
len=G[u].size();
min=low[u]=cnt++;
stack[top++]=u;
for(i=0;i<len;i++)
{
if(visit[G[u][i]]!=flag)
{
DFS(G[u][i]);
}
if(min>low[G[u][i]])
{
min=low[G[u][i]];
}
}
if(min<low[u])
{
low[u]=min;
}
else
{
do
{
sc[v=stack[--top]]=cnt1;
low[v]=INF;
}while(v!=u);
cnt1++;
}
}
bool check()
{
int i;
cnt=cnt1=0;
for(i=0;i<2*N;i++)
{
if(visit[i]!=flag)
{
top=0;
DFS(i);
}
}
for(i=0;i<N;i++)
{
if(sc[i]==sc[i+N])
{
return false;
}
}
return true;
}
有 2×N把钥匙，分成 N组，每组只能选一把钥匙
有 M个门，每个门需要 X或者 Y钥匙，只要其中一把即可,选了一把后同组的令一把钥匙就永远消失。
门是有顺序的，只能先开前面的才能开后面的门，求最多能开多少门？
输入：
N M
A B 有 N行，表示 A，B钥匙一组
X Y 有 M行，表示需要 X或者 Y钥匙
输出：
最多可以打开的门的数量。
Sample Input
3 6
0 3
1 2
4 5
0 1
0 2
4 1
4 2
3 5
2 2
0 0
Sample Output
4

每把钥匙都对应一个变量A和~A
算法，本题采用2-sat算法，通过求强连通分量来求解。

以下是代码的解释：
for(i=1;i<=n;i++)
{
scanf("%d%d",&a,&b);
G[a].push_back(b+N); 由于每把钥匙不能同时都用所以~(A^B) ~A∨~B
G[b].push_back(a+N); Aà~B Bà~A (即A和B不能同
} 时为1）
ans=0;
for(i=1;i<=M;i++)
{
scanf("%d%d",&a,&b);
G[a+N].push_back(b); //两把钥匙，选一就可以开门了，X∨Y ~XàY
G[b+N].push_back(a); // ~YàX
flag++;
if(!check())
{
break;
}
else
{
ans=i;
}
}
题目意思：
Farmer john要用两个中转站把所有的农场连起来，但是有些农场的牛互相恨对方，不能将这些农场连在同一个中转站，有些农场的牛是朋友
必须将这些农场连在同一个农场。现在问你通过某种方案相连后，距离最远的两个农场的最小距离是多少。
Sample Input

4 1 1
12750 28546 15361 32055
6706 3887
10754 8166
12668 19380
15788 16059
3 4
2 3

Sample Output

53246

解题报告：
标程用的算法是二分查找，给定一个答案后，用2-SAT判断是否可行。下面主要说一下2-SAT问题的建模。用布尔变量Xi表示第i个牛栏连到第一个中转站，即Xi为真时连到第一个，为假时连到第二个。那么~Xi表示第i个牛栏连到第二个中转站，~表示布尔取反。 检查每一个约束条件，构造2-SAT的和取范式。

1）i和j不连到同一个中转站，就增加和取范式(Xi + Xj)(~Xi + ~Xj)。

2）i和j必须连到同一个中转站，就增加和取范式(Xi + ~Xj)(~Xi + Xj)。

设现在二分的答案是S。那么检查每一对牛栏i和j（假设D1i，D1j表示i和j到第一个中转站的距离，D2i，D2j表示i和j到第二个中转站的距离，DD表示两个中转站之间的距离）。如果

3）D1i + D1j 〉S，就增加和取范式（~Xi + ~Xj）

4）D2i + D2j 〉S，就增加和取范式（Xi + Xj）

5）D1i + D2j + DD 〉S，就增加和取范式（~Xi + Xj）

6）D2i + D1j + DD 〉S，就增加和取范式（Xi + ~Xj）

剩下的只是用2-SAT的现成算法去判断是否有解。
#include<stdio.h>
#include<string.h>
#include<limits.h>
#define maxn 500
int G[maxn*2][maxn*2],en[maxn*2]={0},tn[maxn*2];
int dis[maxn][2],sc[maxn*2],lw[maxn*2],stack[maxn*2],top;
bool visit[maxn*2];
int N,A,B,low,high,sx1,sy1,sx2,sy2,DS,cnt,cnt1;
inline int abs(int a)
{
return a>0?a:-a;
}
inline void insert(int a,int b)
{
G[a][en[a]++]=b;
}
void DFS(int u)
{
visit[u]=1;
stack[top++]=u;
lw[u]=cnt++;
int min=lw[u];
int i;
for(i=0;i<en[u];i++)
{
if(!visit[G[u][i]])
{
DFS(G[u][i]);
}
if(min>lw[G[u][i]])
{
min=lw[G[u][i]];
}
}
if(min<lw[u])
{
lw[u]=min;
return;
}
int v;
do
{
sc[v=stack[--top]]=cnt1;
lw[v]=INT_MAX;
}while(v!=u);
cnt1++;
}
int add_edge(int dd)
{
int i,j,f;
for(i=0;i<N;i++)
{
for(j=i+1;j<N;j++)
{
f=0;
if(dis[i][0]+dis[j][0]>dd)
{
f++;
insert(i,j+N);
insert(j,i+N);
}
if(dis[i][1]+dis[j][1]>dd)
{
f++;
insert(i+N,j);
insert(j+N,i);
}
if(dis[i][0]+dis[j][1]+DS>dd)
{
f++;
insert(i,j);
insert(j+N,i+N);
}
if(dis[i][1]+dis[j][0]+DS>dd)
{
f++;
insert(j,i);
insert(i+N,j+N);
}
if(f>=4)
{
return 0;
}
}
}
return 1;
}
int check()
{
int i;
cnt=cnt1=1;
memset(visit,0,sizeof(visit));
for(i=0;i<2*N;i++)
{
if(!visit[i])
{
DFS(i);
}
}
for(i=0;i<N;i++)
{
if(sc[i]==sc[i+N])
{
return 0;
}
}
return 1;
}
int main()
{
int i,a,b,mid;
scanf("%d%d%d",&N,&A,&B);
scanf("%d%d%d%d",&sx1,&sy1,&sx2,&sy2);
DS=abs(sx1-sx2)+abs(sy1-sy2);
low=INT_MAX;
high=-INT_MAX;
for(i=0;i<N;i++)
{
scanf("%d%d",&a,&b);
dis[i][0]=abs(a-sx1)+abs(b-sy1);
dis[i][1]=abs(a-sx2)+abs(b-sy2);
if(dis[i][0]>high)
{
high=dis[i][0];
}
if(dis[i][1]>high)
{
high=dis[i][1];
}
if(dis[i][0]<low)
{
low=dis[i][0];
}
if(dis[i][1]<low)
{
low=dis[i][1];
}
}
for(i=0;i<A;i++)
{
scanf("%d%d",&a,&b);
a--,b--;
insert(a,b+N);
insert(b,a+N);
insert(a+N,b);
insert(b+N,a);
}
for(i=0;i<B;i++)
{
scanf("%d%d",&a,&b);
a--,b--;
insert(a,b);
insert(b,a);
insert(a+N,b+N);
insert(b+N,a+N);
}
if(!check())
{
printf("-1\n");
return 1;
}
low*=2;
high=high*2+DS;
for(i=0;i<2*N;i++)
{
tn[i]=en[i];
}
while(low<high)
{
mid=(low+high)/2;
memcpy(en,tn,sizeof(int)*2*N);
if(add_edge(mid)&&check())
{
high=mid;
}
else
{
low=mid+1;
}
}
printf("%d\n",high);
return 1;
}
关键部分说明：
for(i=0;i<A;i++)
{
scanf("%d%d",&a,&b);
a--,b--;
insert(a,b+N); //a和b必须连在不同的站上
insert(b,a+N); 有~(a^b)^~(~a^~b)转化成和取式后有
insert(a+N,b); (a∨b)^(~a∨~b)有a-->~b,b-->~a,~a-->b
insert(b+N,a); //_b-->a
}
for(i=0;i<B;i++)
{
scanf("%d%d",&a,&b);
a--,b--;
insert(a,b); //必须连在一起，即a和b连在相同的站上
insert(b,a); (a^b)∨(~a^~b)化简和取式后(a∨~b)^(b∨~a)有a-->b,~b-->`~a,b-->a, ~a-->~b
insert(a+N,b+N);
insert(b+N,a+N);
}
6. 求图中不含有割点（关结点）的块
void dfs(int u,int father)
{
int v,t;
pre[u]=low[u]=cnt++;
stack[top++]=u;
for(v=0;v<N;v++)
{
if(mp[u][v]&&v!=father)
{
if(pre[v]==-1)
{
dfs(v,u);
if(low[v]<low[u])
{
low[u]=low[v];
}
if(low[v]>=pre[u])
{
do
{
t=stack[--top];
save[k++]=t;
}while(t!=v);
save[k++]=u;
check(); //这个函数处理save中块的结点函数，处理完后k=0
}
}
else if(low[u]>pre[v])
{
low[u]=pre[v];
}
}
}
}
void solve()
{
cnt=top=0;
int i,ans=0;
for(i=0;i<N;i++)
{
if(pre[i]==-1)
{
dfs(i,-1);
}
}
}

要正确区别不含关结点的块和（有向图或无向图）的强连通分量的区别，也就是要区别双向连通性和边连通性，双向连通任何两个结点存在两条不共用结点的路径，边连通性则不共用边,可以共用结点。

1
4

3
5
2
右边这个图有两个块：
5
4
3
2
3
1
如下面的图所示：

7. 图的奇环的判断,是否为二分图的判断

bool color(int u,int c)
{
int v;
cor[u]=c;
for(v=0;v<G[u].size();v++)
{
if(cor[G[u][v]]==-1)
{
if(!color(G[u][v],1-c))
return false;
}
else if(cor[G[u][v]]==c)
{
return false;
}
}
return true;
}
memset(cor,-1,sizeof(cor));
color(0,1);
8. 二分图的匹配
一个G[N][M]的图的匹配，当图的边很少时，可以采用链表来做。
int my[M],visit[M];
int path(int u)
{
int i;
for(i=0;i<M;i++)
{
if(G[u][i]&&!visit[i])
{
visit[i]=1;
if(my[i]==-1||path(my[i]))
{
my[i]=u;
return 1;
}
}
}
return 0;
}
int macth()
{
int i,cnt=0;
memset(my,-1,sizeof(my));
for(i=0;i<N;i++)
{
memset(visit,0,sizeof(visit));
cnt+=path(i);
}
return cnt;
}
9. prim算法求最小生成树
int G[maxn][maxn]={0},wt[maxn],N,st[maxn],fr[maxn];
void GRAPHmstV(int st[],int wt[]) //节点编号为0到N-1
{ //wt[i] 若i未加入生成树中，表示结点i到生成树中结点的最小距离。
int v,w,min; //st[]有两个作用，初始st[]为-1可以作是否访问的标记，最后i--st[i]为所求最小
for(v=0;v<N;v++) //生成树的边
{
st[v]=-1;
fr[v]=v;
wt[v]=INT_MAX;
}
st[0]=0; //初始0为
wt[N]=INT_MAX;
for(min=0;min!=N;)
{
v=min;
st[min]=fr[min];
for(w=0,min=N;w<N;w++) //这边注意min=N 所以要保证wt[N]不会越界。
{
if(st[w]==-1) //w为未加入到生成树的结点
{
if(G[v][w]<wt[w])
{
wt[w]=G[v][w];
fr[w]=v;
}
if(wt[w]<wt[min])
{
min=w;
}
}
}
}
int i;
for(i=1;i<N;i++) //最小生成树的边的个数为N-1
{
printf("%d %d\n",i+1,st[i]+1); //输出最小生成树的边
}
}
10. 给有有向图最少加边使图中没有桥
也就是任何两个结点都有两个不共用边的路径。
Sample Input
7 7
1 2
2 3
3 4
2 5
4 5
5 6
5 7
Sample Output
2
#include<iostream>
#include<string>
#include<vector>
using namespace std;
vector<int>G[5001];
int stack[5001],N,low[5001],sc[5001],cnt,cnt1;
bool visit[5001];
void dfs(int father,int u) //这边多了一个father参数的作用要注意
{ //与有向图的的强连通分量的求法有所不同
int i,len,min,v;
len=G[u].size();
visit[u]=1;
stack[N++]=u;
low[u]=cnt++;
min=low[u];
for(i=0;i<len;i++)
{
v=G[u][i];
if(v!=father)
{
if(!visit[v])
{
dfs(u,v);
}
if(min>low[v])
{
min=low[v];
}
}
}
if(min<low[u])
{
low[u]=min;
}
else
{
do
{
sc[v=stack[--N]]=cnt1;
low[v]=10000;
}while(v!=u);
cnt1++;
}
}
int main()
{
int N,M,i,a,b,j;
scanf("%d%d",&N,&M);
for(i=1;i<=M;i++)
{
scanf("%d%d",&a,&b);
for(j=0;j<G[a].size();j++)
{
if(G[a][j]==b)
{
break;
}
}
if(j<G[a].size()) continue;
G[a].push_back(b);
G[b].push_back(a);
}
cnt=cnt1=1;
dfs(0,1);
vector<int>::iterator p;
memset(stack,0,sizeof(stack));
for(i=1;i<=N;i++)
{
// printf("%d\n",sc[i]);
for(p=G[i].begin();p!=G[i].end();p++)
{
if(sc[i]!=sc[*p])
{
// printf("%d %d\n",sc[i],sc[*p]);
stack[sc[i]]++;
}
}
}
int ans=0;
for(i=1;i<cnt1;i++)
{
if(stack[i]==1)
{
ans++;
}
}
printf("%d\n",(ans+1)/2);
return 1;
}
11. 套汇问题
double rate[32][32];
void folyd()
{
int i,j,k;
for(k=0;k<N;k++)
{
for(i=0;i<N;i++)
{
if(rate[i][k]>0)
{
for(j=0;j<N;j++)
{
if(rate[i][k]*rate[k][j]>rate[i][j])
{
rate[i][j]=rate[i][k]*rate[k][j];
}
}
}

}
}
}
bool check()
{
int i;
for(i=0;i<N;i++)
{
if(rate[i][i]>1)
{
return true;
}
}
return false;
}
12. 差分系统

注意差分系统只能处理x1>=x2+3, x3>=x4+5……等（或把大于等于改成小于等于）只能是大于等于或小于等