图论学习
图论
- 1.图的存储
- 2.拓扑排序
- 3.欧拉路
- 4.无向图的连通性
- 5.有向图的连通性
- 6.基环树
- 7.2-SAT
- 8.最短路径
- 9.最小生成树
- 10.最大流
- 11.二分图
- 12.最小割
- 13.费用流
1.图的存储
邻接矩阵和邻接表
链式前向星
链式前向星没有空间浪费，编程简单。
一个静态数组 \(head[u]\) 存储以 \(u\) 为起点，到相邻点的某一条边。
一个结构体数组 \(edge\) 存储这条边的信息，包括终点、边权等。
#include<bits/stdc++.h>
using namespace std;
const int N=1e6+5,M=2e6+5;
int head[N],cnt;
struct{
int from,to,next;//起点,终点,起点的其他邻接点
int w;//边权
}edge[M];
void addedge(int u,int v,int w){
edge[cnt].from=u;
edge[cnt].to=v;
edge[cnt].w=w;
edge[cnt].next=head[u];
head[u]=cnt++;
}
int main(){
int n,m;cin>>n>>m;
for(int i=0;i<m;i++){
int u,v,w;cin>>u>>v>>w;
addedge(u,v,w);
}
for(int i=0;i<=n;i++)
printf("h[%d]=%d,",i,head[i]);
printf("\n");
for(int i=head[2];i!=-1;i=edge[i].next)
printf("%d-%d\n",edge[i].from,edge[i].to);
return 0;
}
2.拓扑排序
在图中求一个有先后关系的排序，这就是拓扑排序。
拓扑排序可以找到图中的环。
基于BFS的拓扑排序
a. 无前驱的顶点优先
就是先输出入度为0的点。
步骤如下：
- 找到所有入度为0的点，放入队列作为起点，找不到说明图不是DAG，不存在拓扑排序
- 队首弹出，所有邻居点入度减1，入度为0的邻居点入队
- 重复操作，直到队列为空
- 队列已空还有点未入队，说明图上存在环
b.无后继的顶点优先
就是先输出出度为0的点。
时间复杂度都为 \(O(n+m)\) 。
如果要输出字典序最小的拓扑排序，可以将队列改为优先队列。
基于DFS的拓扑排序
从入度为0的点开始DFS，递归返回的就是拓扑排序。
多个入度为0的点都执行DFS。
时间复杂度 \(O(n+m)\)。
我的评价是poj好烂，只允许国外访问，并且语言版本太老了
#include<iostream>
#include<algorithm>
#include<cstring>
using namespace std;
const int N=30,M=2e6+5;
int n,a[N],dir[N][N];//dir[i][j]=1表示ij是先后关系
int topo[N],vis[N],indegree[30];//topo拓扑排序,indegree入度,vis是否访问
void dfs(int z,int cnt){
topo[cnt]=z;//记录拓扑排序
if(cnt==n-1){//所有点都取完了
for(int i=0;i<n;i++)
printf("%c",topo[i]+'a');
printf("\n");
}
vis[z]=1;//标记为已访问
for(int i=0;i<n;i++)
if(!vis[a[i]]&&dir[z][a[i]])
indegree[a[i]]--;//把所有下属的入度-1
for(int i=0;i<n;i++)
if(!indegree[a[i]]&&!vis[a[i]])//入度为0的点继续取
dfs(a[i],cnt+1);
for(int i=0;i<n;i++)//把下属的入度复原
if(!vis[a[i]]&&dir[z][a[i]])
indegree[a[i]]++;
vis[z]=0;//恢复
}
int main(){
char s[100];
int len;
while(gets(s)!=NULL){
memset(dir,0,sizeof(dir));
memset(vis,0,sizeof(vis));
memset(indegree,0,sizeof(indegree));
len=strlen(s);
n=0;
for(int i=0;i<len;i++)
if(s[i]<='z'&&s[i]>='a')
a[n++]=s[i]-'a';
sort(a,a+n);
gets(s);
len=strlen(s);
int first=1;//表示当前字母是起点
for(int i=0;i<len;i++){//处理先后关系
int st,ed;
if(first&&s[i]<='z'&&s[i]>='a'){//起点
first=0;
st=s[i]-'a';//把字母转换为数字
continue;
}
if(!first&&s[i]<='z'&&s[i]>='a'){//终点
first=1;
ed=s[i]-'a';
dir[st][ed]=1;//记录先后关系
indegree[ed]++;//终点入度+1
continue;
}
}
for(int i=0;i<n;i++)
if(!indegree[a[i]])//所有入度为0的点开始
dfs(a[i],0);
printf("\n");
}
return 0;
}
#include<iostream>
#include<algorithm>
#include<cstring>
#include<queue>
using namespace std;
const int N=30;
int ANS[N],TMP[N],IN[N],MAP[N][N];
int n,m,ans,sz,f;
char S[10];
queue<int> q;
int topo(){
sz=0,f=0;
while(!q.empty()) q.pop();//清空q队列
for(int i=1;i<=n;i++)
if(TMP[i]==0){//入度为0，放入队列
q.push(i);
TMP[i]--;//入度变为-1
}
while(!q.empty()){
if(q.size()>1) f=-1;//如果q队列包含多个入度为0的，方案不唯一
int i=q.front();
q.pop();
ANS[++sz]=i;
for(int j=1;j<=n;j++){
if(MAP[i][j]) TMP[j]--;//邻接点，入度都--
if(TMP[j]==0){//为空则放入队列
q.push(j);
TMP[j]--;
}
}
}
for(int i=1;i<=n;i++)
if(TMP[i]!=-1)//存在点未取到
return -1;
if(f==-1) return 0;//q数组不为空
return 1;
}
int main(){
while(scanf("%d%d",&n,&m)&&n&&m){
memset(IN,0,sizeof(IN));
memset(MAP,0,sizeof(MAP));
ans=0;//三种状态
for(int i=1;i<=m;i++){
scanf("%s",S);
if(ans!=0) continue;//状态确定，只输入
int a=S[0]-'A'+1,b=S[2]-'A'+1;
if(!MAP[b][a]) IN[a]++;//a的入度++
MAP[b][a]=1;//从b到a有关联
for(int j=1;j<=n;j++) TMP[j]=IN[j];//将入度复制，只修改TMP
ans=topo();
if(ans==1){
printf("Sorted sequence determined after %d relations: ", i);
for(int j=n;j>=1;j--)//从后往前输出
printf("%c",ANS[j]+'A'-1);
printf(".\n");
}
if(ans==-1) printf("Inconsistency found after %d relations.\n", i);
}
if(ans==0) printf("Sorted sequence cannot be determined.\n");
}
return 0;
}
#include<bits/stdc++.h>
using namespace std;
const int N=10010;
int n;
int a[N],f[N];//a单独每个事情时间,f完成这个事情最少时间
vector<int> edge[N];
int dfs(int x){
if(f[x]) return f[x];
for(int i=0;i<edge[x].size();i++){
f[x]=max(f[x],dfs(edge[x][i]));//第x件事最少时间
}
f[x]+=a[x];
return f[x];
}
int main(){
cin>>n;
for(int i=1;i<=n;i++){
int x,y;
cin>>x>>a[i]>>y;
while(y!=0){
edge[y].push_back(x);cin>>y;
}
}
int ans=0;
for(int i=1;i<=n;i++) ans=max(ans,dfs(i));
cout<<ans<<"\n";
return 0;
}
//与上面poj 1094题意相同
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=5e4+10;
const ll mod=10000;
int n,m,s,t,ti,tot,h[N],in[N];//h,in入度
//h数组链式前向星
ll cnt[N],dis[N];//cnt次数,dis距离
struct nod{
int nex,to,dis;
}edge[N<<1];
void add(int u,int v,int w){
edge[++tot].nex=h[u];//记录兄弟
edge[tot].to=v;//终点
edge[tot].dis=w;//权值
h[u]=tot;//更新链式前向星数组
in[v]++;//入度
}
void dfs(int x){
for(int i=h[x];i!=0;i=edge[i].nex){//遍历x的所有邻接点
int xx=edge[i].to;//子节点
dis[xx]=(dis[xx]+dis[x]+cnt[x]*edge[i].dis)%mod;//更新子节点的距离
cnt[xx]=(cnt[xx]+cnt[x])%mod;
--in[xx];//拓扑排序
if(in[xx]==0) dfs(xx);
}
}
int main(){
cin>>n>>m>>s>>t>>ti;
for(int i=1,u,v,w;i<=m;i++){
cin>>u>>v>>w;
if(u!=v) add(u,v,w);
}
cnt[s]=1;
dfs(s);
cout<<((dis[t]+(cnt[t]-1)*ti)%mod);
return 0;
}
#include<bits/stdc++.h>
using namespace std;
const int N=1e5+10;
int t,n,m,x,y,cnt;
int in[N],ans[N];
vector<int> vec[N];
priority_queue<int> que;
void solve(){
cin>>n>>m;
cnt=0;
for(int i=1;i<=n;i++) ans[i]=in[i]=0;//初始化
for(int i=1;i<=n;i++) vec[i].clear();
for(int i=1;i<=m;i++){
cin>>x>>y;
in[x]++;
vec[y].push_back(x);//反向建边
}
for(int i=1;i<=n;i++)
if(in[i]==0) que.push(i);//入度为0
while(!que.empty()){
int u=que.top();
que.pop();
for(int i=0;i<vec[u].size();i++){
int x=vec[u][i];
in[x]--;
if(in[x]==0) que.push(x);
}
ans[++cnt]=u;
}
if(cnt<n) cout<<"Impossible! ";
else
for(int i=cnt;i>=1;i--) cout<<ans[i]<<" ";
cout<<"\n";
}
int main(){
ios::sync_with_stdio(0),cin.tie(0);
int t;cin>>t;
while(t--) solve();
return 0;
}
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=5e3+10;
const int M=5e5+10;
const ll mod=80112002;
int n,m,f[N],cnt,in[N];
ll ans,dp[N];
struct nod{
int nex,to;
}edge[M];
queue<int> q;
int main(){
ios::sync_with_stdio(0),cin.tie(0);
cin>>n>>m;
for(int i=1;i<=m;i++){
int x,y;cin>>x>>y;
edge[++cnt].to=y;
edge[cnt].nex=f[x];
f[x]=cnt;
in[y]++;
}
for(int i=1;i<=n;i++)
if(!in[i]){
q.push(i);
in[i]--;
dp[i]=1;
}
while(!q.empty()){
int x=q.front();q.pop();
if(f[x]==0){
ans=(ans+dp[x])%mod;
in[x]--;
continue;
}
for(int i=f[x];i!=0;i=edge[i].nex){
int y=edge[i].to;
dp[y]=(dp[y]+dp[x])%mod;
in[y]--;
if(!in[y]){
q.push(y);
in[y]--;
}
}
}
cout<<ans<<"\n";
return 0;
}
3.欧拉路
欧拉路：一笔画
欧拉回路：一笔画并且起点终点相同
无向图判断条件：
- 必须是联通图
- 所有点度数都为偶，则存在欧拉回路
- 只有两个度数为奇，则存在欧拉路
有向图判断条件：
- 必须是连通图
- 出度记为1，入度记为-1，度数为相加
- 所有点度数为0，则存在欧拉回路
- 只有一个度数为1和一个度数为-1，则存在欧拉路
The Necklace - UVA 10054 - Virtual Judge
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=60;
int n,m,in[N],G[N][N];
void euler(int u){//输出欧拉回路
for(int v=1;v<=50;v++){
if(G[u][v]){
G[u][v]--;
G[v][u]--;
euler(v);
cout<<v<<" "<<u<<"\n";
}
}
}
void solve(){
memset(in,0,sizeof(in));
memset(G,0,sizeof(G));
cin>>n;
for(int i=0;i<n;i++){
int u,v;cin>>u>>v;
m=u;
in[u]++,in[v]++;
G[u][v]++,G[v][u]++;
}
for(int i=1;i<=50;i++)
if(in[i]%2){
cout<<"some beads may be lost\n";
return;
}
euler(m);//从任意点开始
}
int main(){
ios::sync_with_stdio(0),cin.tie(0);
int t;cin>>t;
for(int i=1;i<=t;i++){
cout<<"Case #"<<i<<"\n";
solve();
cout<<"\n";
}
return 0;
}
#include<stdio.h>
const int N=60;
int num[N];//num[v]为点v后加的数字
int st_edge[10*N],top_s;//栈,用于存边,top_s栈顶
char st_ans[10*N];int top_a;//存序列结果,top_a栈顶
int m;
void nodfs(int v){//模拟递归,搜索v的10条边
int edge;
while(num[v]<10){
edge=10*v+num[v];
num[v]++;
st_edge[top_s++]=edge;
v=edge%m;
}
}
int main(){
int n,edge;
while(scanf("%d",&n)&&n!=0){
top_s=top_a=edge=0;
m=1;
for(int i=0;i<n-1;i++) m*=10;//m是点的数量
for(int i=0;i<m;i++) num[i]=0;
nodfs(0);//从起点0开始,递归点0的10条边
while(top_s){//继续走
edge=st_edge[--top_s];
st_ans[top_a++]=edge%10+'0';
nodfs(edge/10);
}
for(int i=1;i<n;i++) printf("0");
while(top_a) printf("%c",st_ans[--top_a]);
printf("\n");
}
return 0;
}
#include<bits/stdc++.h>
using namespace std;
const int N=257;
int G[N][N],depth[N],n,cnt,hen,f[N],sum[N];
char tmp[N],rb[N*N];
void dfs(int x){
for(int i=0;i<N;i++)
if(G[x][i]) G[x][i]=G[i][x]=0,dfs(i);
rb[n--]=x;
}
int find(int x){
if(f[x]!=x) f[x]=find(f[x]);
return f[x];
}
int main(){
cin>>n;
for(int i=0;i<N;i++) f[i]=i;
for(int i=1;i<=n;i++){
cin>>tmp;int a=tmp[0],b=tmp[1];
G[a][b]=G[b][a]=1;
int fx=find(a),fy=find(b);
f[fx]=fy;//并查集
depth[a]++,depth[b]++;//度数
}
int ans=0;
for(int i=0;i<N;i++)
if(f[i]==i&&depth[i]) ans++;
if(ans!=1){//不是整个连通块
cout<<"No Solution";return 0;
}
for(int i=0;i<N;i++)
if(depth[i]%2!=0){//奇数
cnt++;
if(!hen) hen=i;
}
if(hen==0)//任意点为起点，欧拉回路
for(int i=0;i<N;i++)
if(depth[i]){
hen=i;break;//记录第一个字母
}
if(cnt&&cnt!=2){//度数为奇的点大于两个
cout<<"No Solution";return 0;
}
dfs(hen);
cout<<rb;
return 0;
}
8.最短路径
最短路问题答案是可加的，网络流问题答案是不可加的，如权值最小的边等。
使用DFS查找所有路径，共有 \(n!\) 个排列。
没有边权的图可以使边权等于一。
| 算法 | 问题 | 边权要求 | 时间复杂度 |
|---|---|---|---|
| BFS | 一个起点到所有点 | 无边权或为1 | \(<O(m+n)\) |
| Dijkstra(优先队列) | 一个起点到所有点 | 非负数 | \(<O((m+n)\log_2n)\) |
| SPFA | 一个起点到所有点 | 允许有负数 | \(<O(mn)\) |
| Floyd-Warshall | 所有点到所有点 | 允许有负数 | \(<O(n^3)\) |
Dijkstra(优先队列)
边权必须非负。
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=1e5+10;
int n,m,s,inf=0x3f3f3f3f;
struct edge{//边
int v,w;
};
struct node{//点
int len,u;//len=起点到u的距离
friend bool operator >(node a,node b){
return a.len>b.len;
}
};
vector<edge> vt[N];//邻接表
int dis[N],vis[N];//距离，是否访问
priority_queue<node,vector<node>,greater<node> > q;
void dijkstra(){
memset(dis,inf,sizeof(dis));
memset(vis,0,sizeof(vis));
dis[s]=0;//起点
q.push({0,s});//放入起点
while(!q.empty()){
int u=q.top().u;q.pop();//取出顶点
if(vis[u]) continue;//如果已访问
vis[u]=1;//设置访问
for(int i=0;i<vt[u].size();i++){//遍历u的所有子节点
int v=vt[u][i].v,w=vt[u][i].w;
if(dis[v]>dis[u]+w){//更新子节点
dis[v]=dis[u]+w;
q.push({dis[v],v});
}
}
}
}
int main(){
ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
cin>>n>>m>>s;
int ansinf=(1<<31)-1;
while(m--){
int u,v,w;cin>>u>>v>>w;
vt[u].push_back({v,w});
}
dijkstra();
for(int i=1;i<=n;i++){
if(dis[i]==inf) cout<<ansinf<<" ";
else cout<<dis[i]<<" ";
}
return 0;
}
